Lista de probleme 6

În regatul „Iluminia” există un laborator care conține o rețea de N camere, fiecare cameră are lungimea P și este reprezentată de o secvență de comutatoare, fiecare comutator având starea 0 (stins) sau 1 (aprins).

Regele dorește să construiască o cameră supremă pentru un experiment de mare anvergură. Această cameră supremă se obține prin aplicarea operației XOR (^) asupra tuturor secvențelor de comutatoare. Regele vrea ca această cameră rezultată să fie „supremă”, adică să conțină doar comutatoare în starea 1.

Deoarece acest lucru nu este garantat, regele are la dispoziție M operații de flip. Fiecare flip inversează starea anumitor comutatoare dintr-o subsecență de lungime cel mult L (0 devine 1, iar 1 devine 0). Comutatoarele care vor fi inversate sunt la discreția regelui.

Acest lucru înseamnă că regele are posibilitatea de a alege, dintr-o subsecență dată de comutatoare, care dintre acestea să fie inversate. El nu este obligat să inverseze toate comutatoarele din subsecența aleasă, ci poate alege doar anumite comutatoare, în funcție de cum consideră că este cel mai eficient pentru găsirea camerei supreme.

Sarcina ta este să găsești cea mai mică valoare L pentru care există o succesiune de cel mult M flip-uri (fiecare aplicată pe o subsecență de lungime cel mult L) care să construiască camera supremă.

Aflat pe plaja urbană din cartierul Cricozescu al orașului Jluc, Andrei participă la un concurs de construcții de castele de nisip. Fiecare concurent a construit deja un anumit număr de castele n, însă organizatorii concursului au schimbat regulile în ultimul moment, astfel că, pentru a fi eligibili în etapa de jurizare, toate castelele concurenților trebuie să aibă exact aceeași înălțime. Andrei ne cere să îl ajutăm să determine numărul minim de operații pe care el trebuie să le facă asupra castelelor sale astfel încât toate să aibă, în final, aceeași înălțime.

Fermierul Ion, cândva cunoscut pentru porumbul său de înaltă calitate, a intrat în faliment. Acum, el se mulțumește să crească roșii pe un câmp pătratic împărțit în N × N parcele. La început, câmpul era gol, dar de-a lungul timpului, Ion a efectuat mai multe plantări respectând o regulă specială, numită formula roșiilor gustoase:

• se alege un număr v;
• se alege o porțiune a câmpului definită de colțul stânga-sus (a, b) și colțul dreapta-jos (c, d. Cu alte cuvinte, pentru orice 1 ≤ i, j ≤ N, porțiunea câmpului conține parcela de pe linia i și coloana j dacă a ≤ i ≤ c și b ≤ j ≤ d.
• în fiecare parcelă din porțiune se plantează un număr de roșii egal cu suma modulo 1789 a numerelor mai mici decât v care sunt coprime cu v.

Te-ai decis să ieși la o plimbare cu Opelozaurul pe un traseu care conține, la fiecare kilometru, un indicator cu numerele naturale din intervalul [1, N], în ordine crescătoare. Îți începi traseul în dreptul indicatorului cu numărul 1 și îl termini la indicatorul cu numărul N.

În mod normal, reușești să parcurgi orice kilometru cu mașina în 100 de secunde, dar, înainte să începi cursa, drumul a fost afectat de precipitații.

Prima dată a fost afectat de ninsori, fiecare ninsoare fiind descrisă printr-un triplet L R k, care arată că ninsoarea a afectat drumul în intervalul delimitat de indicatoarele L și R, iar acum, în acel interval, numărul de secunde necesare pentru a parcurge un kilometru crește cu k, indiferent de valoarea lui precedentă.

După ninsori, drumul este afectat de ploi, care sunt descrise și ele prin triplete L R k și limitează timpul în care mașina poate să parcurgă un kilometru în intervalul delimitat de indicatoarele L și R la k secunde.

Se dau Q numere întregi p din intervalul [1, N], iar pentru fiecare trebuie să determini numărul de secunde necesare să ajungi în dreptul panoului p.

Andrei este managerul unei librării care dorește să mențină o evidență exactă a prețurilor cărților din inventar. Emanuel, administratorul librăriei, implementează planuri de marketing care implică modificări repetate ale prețurilor (operații de modificare de preț), iar deciziile sale se pot schimba ulterior. Pentru a maximiza profitul obținut în funcție de cerere, în fiecare zi, Emanuel efectuează o serie de operații (modificări, anulări și refaceri), iar la sfârșitul fiecărei zile, Andrei trebuie să vadă starea finală a prețurilor din librărie.

Andrei se află într-un labirint format dintr-o matrice de camere, fiecare având unul dintre următoarele tipuri: 0: cameră cu bec stins, 1: cameră cu bec aprins, 2: cameră fără bec (inaccesibilă), 3: cameră cu întrerupător.

Camerele de tip 3 pot aprinde/stinge becurile altor camere. Andrei poate alege să apese sau nu întrerupătoarele întâlnite. El pornește dintr-o cameră dată și trebuie să ajungă într-o cameră destinație, deplasându-se doar prin camere aprinse.

Se cere determinarea distanței minime pentru a ajunge la destinație.