Lista de probleme 3

O familie de oposumi are o vizuină cu N niveluri și N * (N + 1) / 2 camere dispuse în formă de matrice triunghiulară cu N linii. În fiecare cameră poate locui un singur oposum. Vizuina a fost săpată în pământ de către oposumi, iar nivelul 1 (cel mai de sus) este cel mai apropiat de suprafața solului. Pe fiecare nivel I se află I camere. Dacă avem I < J, atunci nivelul I va fi poziționat mai sus decât nivelul J, adică nivelul I va fi mai aproape de suprafața solului decât nivelul J. În familia de oposumi se află exact N * (N + 1) / 2 membri cu vârste cuprinse între 1 și N * (N + 1) / 2, vârste distincte. Regula de bază în vizuina familiei de oposumi este următoarea: în camera de pe linia I și coloana J trebuie să locuiască un oposum mai tânăr decât în camerele de pe pozițiile (I + 1, J) respectiv (I + 1, J + 1). Un oposum de vârsta X se consideră mai tânăr decât un oposum de vârsta Y dacă X < Y. Fiecare oposum vrea să știe care e cel mai de sus nivel pe care se poate poziționa. Din păcate, ei nu au lăbuțele făcute să programeze, așa că membrii familiei de oposumi vă cer vouă ajutorul.
Dându-se numărul natural N ei vă cer să răspundeți la două întrebări:
1. Pentru fiecare oposum să se afle nivelul cel mai de sus (cel mai aproapiat de suprafața solului) pe care se
poate afla respectând regulile de vârstă.
2. Pentru un oposum dat de vârsta K să se afișeze matricea astfel încât oposumul să stea într-o cameră pe un nivel cât mai de sus respectând regulile de vârstă.

Ne aflăm înainte de începutul faimoasei curse de anduranță de la Le Mans. După cum bine stiți, într-o cursă de anduranță mașina care a parcurs cea mai mare distanță pe parcursul cursei este considerată câștigătoare. Anul acesta Federația Internațională de Automobilism (FIA) a făcut câteva schimbări majore cu privire la desfășurarea cursei. Anul acesta cursa va dura exact T secunde și vor participa N echipe, fiecare echipă având câte o mașină, iar fiecare mașină poate pleca de pe oricare dintre cele M poziții din grila de start. De asemenea, FIA a impus câteva reguli care au nemulțumit echipele participante:

• Fiecare mașină este obligată să se deplaseze cu o viteză constantă pe parcursul întregii curse. Astfel, a i-a mașină se va deplasa cu viteza de v[i] metri pe secundă.
• Dacă o mașină pleacă de pe o poziție j din grila de start, aceasta se află la o distanță de p[j] metri după linia de start, iar această distanță este luată în considerare ca o distanță deja parcursă în cadrul cursei.

Ca semn de protest asupra noului regulament, echipele au hotărât să se așeze în grila de start astfel încât diferența maximă dintre distanțele parcurse de oricare două mașini să fie cât mai mică posibil.

După șase ani de lucru, Charles a terminat de curățat instalațiile pentru producerea negrului de fum din Copșa Mică. Pentru a se ține departe de mesele de Blackjack, el s-a angajat la CERN, unde va lucra la noul accelerator de particule numit Even Larger Hadron Collider (ELHC). ELHC are forma unui tunel circular cu o circumferință de P kilometri, P fiind un număr prim. De-a lungul tunelului sunt plasați P senzori numerotați de la 0 la P - 1, distanța dintre doi senzori consecutivi fiind de exact 1 kilometru.

Un experiment efectuat în ELHC constă în studierea unei particule de tip G, 1 ≤ G < P. Dacă această particulă este ridicată la nivelul de energie k și este lansată din dreptul senzorului 0 în direcția senzorului 1, ea va parcurge exact Gk kilometri prin tunel și apoi se va dezintegra, declanșând în acel moment senzorul s în dreptul căruia are loc dezintegrarea particulei. Se consideră că experimentul are date complete dacă, lansând P - 1 particule de tip G ridicate la toate nivelurile de energie k de la 1 la P - 1, este posibil să declanșăm toți senzorii s numerotați cu valori între 1 și P - 1, adică toți senzorii din tunel mai puțin senzorul 0.

Dându-se T perechi de numere G și P, determinați dacă experimentul pentru studierea particulei de tip G într-un tunel de circumferință P produce date complete.