Lista de probleme 954

Ash este un antrenor Pokemon ambițios, setându-și scopul să devină cel mai bun. Din păcate, rivalul său, Gary, a furat startul și are Pokemoni mai puternici decât cei ai lui Ash.

Totuși, Ash nu se va da bătut chiar așa ușor! Are un plan de bătaie: în aventurile sale a găsit o clădire misterioasă care poate fi reprezentată ca o matrice de N x M, fiecare celulă reprezentând conținutul unei camere. În această clădire se află:

• Ash (codificat cu A): Ash se află inițial în această cameră
• Mewtwo (codificat cu M): cel mai puternic Pokemon cunoscut de om. Ash are deja un Master Ball, așa că îl va poate prinde pe Mewtwo cu ușurință.
• Gary (codificat cu G): a fost provocat de Ash la o bătălie de Pokemoni și îl așteaptă într-o anumită cameră
• cameră liberă (codificată cu _): Ash poate accesa această cameră
• cameră ocupată (codificată cu #): Ash nu poate accesa această cameră

Planul său constă în a-l prinde pe Mewtwo, după aceea în a-l confrunta pe Gary. Ash se poate deplasa în cele patru direcții cardinale (N, E, S, V). Știind că o deplasare se face într-o secundă, determinați numărul minim de secunde în care Ash poate ajunge la Mewtwo, apoi la Gary.

Se consideră un cerc. Pe cerc se desemnează N puncte oarecare. Dacă tragem linii între toate perechile de puncte, care este numărul maxim de bucăți în care poate fi descompus cercul? Să se răspundă la Q astfel de scenarii.

Cunoscând numărul de zile în care se desfășoară activitatea, producția zilnică inițială, respectiv lista cu cele N comenzi, să se rezolve următoarele cerințe:

• dacă T = 1, atunci Gimi vrea să afle numărul maxim de culegeri pe care le poate avea în stoc la finalul ultimei zile (a N-a zi).
• dacă T = 2, atunci Gimi vrea să afle numărul maxim de culegeri pe care le poate avea în stoc la finalul celei de-a i-a zi, pentru fiecare i de la 1 la N.

Să se scrie o funcție C++ care va căuta, în caz că există, un nod care memorează valoarea val. Dacă există un asemenea nod, atunci va insera înainte de acest nod un nou nod ce va memora pe x, și de asemenea va insera după acest nod un nou nod ce va memora pe y.

Un număr natural se numește extrapar dacă poate fi scris ca sumă de puteri distincte ale lui 2, puteri care au exponent par. Numărul 0 este considerat, de asemenea, extrapar. Considerând reprezentarea în baza 2 pentru un număr natural, se numerotează pozițiile cifrelor din reprezentare, de la dreapta către stânga, începând cu 0. Asupra reprezentării în baza 2 trebuie să se efectueze o singură operație. Operația constă din eliminarea a exact K cifre situate pe poziții consecutive. Fiind date reprezentările în baza 2 pentru N numere naturale, să se determine pentru fiecare dintre ele dacă se poate obține un număr extrapar în condițiile de mai sus.

Kida și El Bandito Inofensivo au N display-uri digitale care pot afișa litere mici din alfabetul englez. Fiecare dintre cele N display-uri are câte M celule. Pentru fiecare display i, cunoaștem literele care pot fi afișate în fiecare celulă j a sa. El Bandito Inofensivo consideră că un cuvânt de lungime M este comun dacă acesta se poate forma pe cel puțin K dintre cele N display-uri. Auzind asta, Kida vă roagă să o ajutați să calculeze numărul de cuvinte comune distincte. Ajutați-o pe Kida să calculeze numărul de cuvinte comune distincte. De vreme ce acest număr poate să fie foarte mare, se cere restul său la împărțirea prin 1.000.000.009.

Ernest a găsit în garajul familiei sale un joc Pacman. Labirintul din joc poate fi reprezentat ca o matrice cu N linii și N coloane. Pe fiecare linie și fiecare coloană există exact un obstacol. Vom nota cu (L, C) poziția de pe linia L și coloana C. Matricea este circulară: dacă Pacman se deplasează la dreapta din poziția (L, N), ajunge în (L, 1), iar dacă se deplasează la stanga din poziția (L, 1), ajunge în (L, N), pentru orice linie L din matrice. Similar, dacă se deplasează în sus din (1, C), ajunge în (N, C), respectiv dacă se deplasează în jos din (N, C), ajunge în (1, C), pentru orice coloană C. Inițial Pacman se află în (1, 1) și vrea sa ajungă în (N, N) unde se găsește un punct galben care îl va ajuta să învingă fantomele colorate. Problema este formată din doua cerințe:

• Cerința 1. Se citește un șir de mișcări format din literele U, D, L, R, ce descriu în ordine mișcările lui Pacman. Deplasându-se conform acestui șir, va ajunge Pacman din (1, 1) la punctul galben de coordonate (N, N)?
• Cerința 2. Care este numărul minim de mișcări U, D, L, R prin care Pacman poate ajunge din (1, 1) la punctul galben de coordonate (N, N)?

După ce a scăpat de Spân și a devenit împărat, Harap-Alb a decis să își construiască un nou castel în împărăția sa ce poate fi reprezentată cu ajutorul sistemului de coordonate carteziene. El știe că Roș-Împărat a construit N+1 garduri dreptunghiulare, însă știe și că acesta este cam zgârcit și nu a folosit cele mai bune materiale. Harap-Alb a învățat din greșeli, iar acum încearcă să se ferească de pericole cât de mult poate. De aceea, el vrea să își amplaseze castelul într-un punct din sistemul cartezian care să se afle în interiorul a cel puțin N dintre cele N+1 garduri. Fiind date numărul natural nenul N și coordonatele celor N+1 garduri (perechi de colțuri stânga-sus și dreapta-jos), să se determine (în cazul în care există) punctul cel mai apropiat de originea sistemului de coordonate unde Harap-Alb își poate amplasa castelul astfel încât acesta să se afle în interiorul a cel puțin N garduri.

A fost odată ca niciodată un regat aflat în paragină din cauza conducătorului său trândav. Încolțit de reclamațiile localnicilor, regele decide să angajeze un servitor, numit Phil, în speranța că acesta îi va face treaba și va rezolva nemulțumirile cetățenilor legate de numărul de spații verzi și proprietăți. Cum sarcinile sunt destul de dificile pentru perseverentul Phil, acesta apelează la voi pentru ajutor. El vă roagă să scrieți un program care să citească numerele naturale n, m și matricea ce reprezintă harta și care să determine: 1) partea întreagă r a raportului dintre suprafața palatului regal și cea a casei lui Phil; 2) valoarea absolută d a diferenței dintre numărul de zone verzi și numărul de case de vacanță ale regelui.

Date fiind numărul N de parcele, K – numărul maxim de parcele pe care le poate parcurge planorul ce pornește de la înălțime zero, precum și diferențele de nivel corespunzătoare fiecăreia dintre cele N parcele să se rezolve următoarele 3 cerințe:
1) înălțimea maximă la care ajunge planorul dacă pleacă din prima parcelă și parcurge cel mult K parcele (dar cel puțin una);
2) înălțimea maximă la care ajunge planorul, dacă alege convenabil o parcelă X de lansare și după ce parcurge exact K parcele;
3) înălțimea maximă la care ajunge planorul, dacă alege convenabil o parcelă X de lansare și parcurge cel mult K parcele (dar cel puțin una).