Lista de probleme 5

După zile întregi de muncă, vrăjitorul Arpsod a terminat de confecționat noua sa baghetă magică, cea mai puternică de până acum. Ca să o testeze, el s-a gândit la următorul antrenament: își va lua K ținte miscătoare și se va apuca să tragă în ele cu cea mai puternică vrajă a lui, “Blatus Blast”. Fiind o magie foarte solicitantă, vrăjitorul a hotărat că va trage doar de N ori. Arpsod este un trăgător extraordinar, astfel fiecare din cele N lovituri va nimeri exact una din cele K ținte. Într-o sesiune de N lovituri, unele ținte pot fi lovite de mai multe ori iar altele niciodată. Vrăjitorul consideră că sesiunea de antrenament este reușită numai dacă fiecare țintă a fost lovită CEL PUȚIN O DATĂ.

În timp ce se odihnește pentru următoarea sesiune de antrenament, ca să mai treacă timpul, a început să numere în câte moduri ar fi putut lovi țintele astfel încât sesiunea de antrenament să fie una reușită.

Curioși din fire, v-ați apucat și voi să numărați dar, văzând că numărul modalităților devine prea mare, ați decis să vă mulțumiți cu restul împărțirii acestui număr la 666013.

Renumitul nostru brutar a avut azi noapte un vis tare ciudat: acesta trăia într-un univers paralel în care nu omul îl mănâncă pe blat ci blatul îl mănâncă pe om… (eh, poate nu chiar atât de paralel). Astfel, brutarul nostru a fost atacat de blatul pe care tocmai îl pregătise (pentru prăjituri, evident) și a încercat să scape. Acesta a ieșit din brutărie și a ajuns în fața unui câmp de formă dreptunghiulară, cu dimensiunile cunoscute, ce poate fi împărțit în celule elementare cu latura de o unitate (exact ca o matrice!). Acesta poate intra pe câmp prin orice celulă a primei linii și trebuie să ajungă în orice celulă a ultimei linii (blatul se va întări până va ajunge acolo). Unele celule îi sunt inaccesibile din cauza diverselor obstacole (pietre, pomi, gropi,etc.)

Brutarul nostru se poate deplasa în 6 moduri:

• Din căsuța curentă în cele adiacente ( Nord, Vest, Sud, Est )
• Două mișcări speciale ce pot varia.

Mutările speciale vor fi citite din fișier și o mutare se va codifica astfel: xA yB, unde x și y sunt numere naturale nenule iar A și B sunt două caractere ce codifică direcția (A poate fi 'N' sau 'S' de la Nord respectiv Sud iar B poate fi ‘E’ sau ‘V’ de la Est respectiv Vest)

O mutare specială se poate face dacă celula destinație nu este ocupată de un obstacol și dacă nu implică ieșirea brutarului din matrice.

Brutarul vă roagă să îi specificați un traseu cu număr minim de celule parcurse, ce pornește de pe prima linie și se termină pe ultima linie, pentru a nu fi blătuit (mâncat de blat).

În clasa a 10-a Alina, Bogdan şi Clara se întâlneau în fiecare săptămână să se joace BlitzCatan. Ei aveau la dispoziţie o repriză de 2 ore pe care o foloseau din plin, fiecare joc durând cel puţin 30 de minute. Cei trei prieteni, dornici să reţină cine a câştigat fiecare joc au vrut sa noteze într-un carneţel. Ei s-au temut ca cineva le va citi carneţelul, aşa că au procedat astfel:

• la finalul unui joc i, câştigătorul c, alege un număr secret \(m_i\) > 0 astfel încât \(m_i\) % 3 = c (Alina alege un multiplu de 3 când câştigă, Bogdan un multiplu de 3+1, Clara un multiplu de 3+2)
• la finalul celor 2 ore, ei calculează unde J este numărul de jocuri, şi notează T în carneţel

Cunoscându-se numărul N de tipuri de produse și cantitățile din fiecare produs, în ordinea în care sosesc de la magazie, să se stabilească numărul maxim de pachete care se pot obține prin alegerea convenabilă a perechilor de produse consecutive și programarea corespunzătoare a automatului, pentru fiecare pereche aleasă.

În Regatul din Sud nu e niciodată prea devreme să te pregăteşti de război. De aceea, în fiecare an Regele organizează un concurs în care premiaţi sunt cei mai buni strategi. Mai întâi, Strategul Şef alege configuraţia ideală de razboi, în care armata va fi dispusă. O trupă într-o configurație e reprezentată de o literă mica din mulțimea {'a'..'z'}. De exemplu, configuraţia “ffscaam" descrie o armată formată din doi fermieri, un soldat, un cavaler, doi arcaşi şi un mag. Bineînţeles, în timpul unei lupte, trupele nu îşi vor menţine neapărat poziiţile inţiale. Cu toate acestea, orice tip de trupă poate schimba poziţia cu maxim un alt tip de trupă, ştiut de dinainte de toţi locuitorii regatului. De asemenea se ştie că arcaşii nu schimbă poziţii decât între ei. Pentru exemplul anterior, dacă un fermier sau un soldat nu schimbă poziţii decât cu un alt fermier sau soldat, configuraţii echivalente cu “ffscaam" sunt “fsfcaam" şi “sffcaam".

Fiecare strateg concurent alege o configuraţie, iar câştigătorii sunt cei care aleg configuraţii echivalente cu cea a Strategului Şef.