Lista de probleme 3

Fie un număr natural nenul n, cunoscut. RAU-Gigel alege un număr oarecare între 1 și n, fie acesta x. Apoi calculează “suma XOR” S = 1 ^ 2 ^ ... ^ (x-2) ^ (x-1) ^ (x+1) ^ (x+2) ^ ... ^ n pe care v-o comunică. Puteți să-l ghiciți pe x ? RAU-Gigel nu prea are răbdare, el vrea repede un răspuns de la voi.

RAU-Gigel și-a descoperit o nouă pasiune: graffiti-ul. El simte o nevoie din ce în ce mai puternică de a-și manifesta spiritul artistic, de a exersa, de a explora, și de a încerca noi și noi tehnici … și pentru asta are nevoie de spațiu.

Făcând o incursiune prin cartier, RAU-Gigel descoperă un depou părăsit împrejmuit de un gard format din plăci de beton de lățimi și înălțimi diferite, dispuse în linie continuă. „O pânză imaculată” se gândește el. Și începe să măsoare plăcile de beton, una câte una, cu gândul ca odată ajuns acasă, să schițeze următoarea sa creație artistică.

El vrea să aleagă câteva plăci de beton alăturate și pe dreptunghiul maximal delimitat de acestea, să își făurească creația. Care este suprafața maximă de desenare ? Ajutați-l pe RAU-Gigel să facă mai multe simulări.

RAU-Gigel se joacă cu noul său set de cale ferată, primit cadou de ziua lui anul acesta. Setul conține N gări distincte din diverse orașe reprezentative ale României (București, Iași, Sebeș, …), numerotate în continuare, pentru simplitate, cu numere de la 1 la N și N – 1 bucăți de șină care pot conecta între ele câte două gări distincte date (conexiunea este bidirecțională) astfel încât folosind aceste șine există un drum unic alcătuit din șine între oricare două gări distincte. Ca orice jucărie, fiecare din cele N – 1 bucăți de șină are un grad de periculozitate asociat acesteia, o valoare exprimată printr-un număr natural nenul (nimeni nu este perfect până la urmă, nici jucăriile), pentru a ști de la ce vârsta ar fi bine să poată fi folosite de copii, de exemplu. De asemenea, toate bucățile de șină au aceeași lungime constantă, de o unitate.

RAU-Gigel își desfășoară joaca pe parcursul a Q zile și în fiecare zi este supravegheat de câte un membru al familiei pentru a fi în siguranță. Din nefericire pentru el, în fiecare din cele Q zile persoana care îl supraveghează îi încurcă puțin planurile, permițându-i să folosească doar șinele care au gradul de periculozitate cel mult M (inclusiv M), o valoare naturală nenulă aleasă de aceasta (de remarcat că poate mereu folosi toate gările). Astfel, folosind toate șinele pe care le are la dispoziție pentru a conecta între ele gările corespunzătoare, va obține una sau mai multe așezări conexe maximale de gări (există un drum unic alcătuit din șine între oricare două gări distincte dintr-o așezare) pe care le va numi în continuare orașe. În fiecare astfel de zi, personajul nostru principal primește de la persoana care îl supraveghează un număr natural nenul K de bucăți de șină considerate perfect sigure pentru joaca copilului de către respectivul supraveghetor, cu care poate conecta oricare două gări distincte dorește. De asemenea, șinele primite îi sunt luate la finalul zilei (poate că persoana respectivă mai supraveghează și alți copii în următoarele zile și mai are nevoie de ele).

RAU-Gigel consideră că un lanț este un șir de una sau mai multe gări distincte astfel încât oricare două gări adiacente din acesta sunt conectate de exact o șină, iar lanțul de lungime maximă este cel format dintr-un număr maxim de bucăți de șină (astfel, lungimea unui lanț este dată de numărul de bucăți de șină din care este alcătuit). Scopul acestuia este ca în fiecare zi să formeze un singur lanț cât mai lung având la dispoziție șinele primite de la supraveghetor și cel mult câte un lanț din fiecare oraș creat de acesta, la alegere (adică pentru fiecare oraș poate să aleagă exact un lanț din el (oricare dorește) sau să nu folosească niciun lanț din acel oraș).