Lista de probleme 184

Bulbuka a primit de curând cadou un infinit de tromino-uri în formă de L. După ce s-a jucat un timp cu ele, a ajuns la următoarea concluzie: poate să acopere cu tromino-uri o tablă de dimensiuni 2Kx2K aproape complet (mai puţin un pătrăţel de dimensiune 1x1). Deşteapta de Bulbuka are un algoritm pentru asta: porneşte de la o configuraţie 2K-1x2K-1, o copiază de încă 3 ori, apoi roteşte 2 dintre copii şi la sfârşit, adaugă un tromino la mijloc (v-a făcut un desen mai jos, ca să înţelegeţi mai bine, pentru K = 1, 2 şi 3). Pornind de la o configuraţie de acest tip, ea a observat că poate roti la 90o câte un tromino, în sensul acelor de ceasornic sau invers, doar dacă după rotire încape înapoi pe tablă. Folosind astfel de rotaţii, pătrăţelul lipsă poate ajunge pe orice poziţie de pe tablă.

Bulbuka vă pune acum Q întrebări de tipul: care este numărul minim de rotaţii necesare pentru ca pătrăţelul lipsă să ajungă de la coordonatele (SR,SC) la coordonatele (FR,FC)?

Un superstring este un şir infinit format din numere naturale nenule scrise fără spaţii între ele, începând cu 1: 1223334444...1010... (fiecare număr x apare de exact x ori).

Să se răspundă la T întrebări de forma: Ce cifră se află în superstring pe poziţia k?

GM are un şir de N numere naturale a1 , a2 ,…, aN , cu proprietatea ai ≤ ai+1 ≤ 2*ai pentru orice i, 1 ≤i < N. El doreşte să scrie în faţa fiecărei valori din şir un semn + sau - astfel încât valoarea S a expresiei obţinute să aibă proprietatea 0 ≤ S ≤ a1 .

Scrieţi un program care să-l ajute pe GM să determine un mod de a scrie cele N semne.

De Ziua Îndrăgostiţilor Vali a hotărât să organizeze o petrecere mare pe stadionul oraşului. La petrecere pot participa numai şi numai îndrăgostiţi care şi-au procurat biletele din timp. Biletele oricărui cuplu sunt aproape identice. Ele au proprietatea că numărul de serie are prima cifră 1 pentru băieţi şi *prima cifră 2 pentru fete, continuarea celor două numere este identică. De exemplu, dacă prietenul are biletul cu numărul 134, atunci prietena lui are biletul 234, iar dacă prietena are biletul 2234567890, atunci prietenul ei are biletul 1234567890.
Bineînțeles, că și Vali are bilet și speră să câștige un cadou. Biletul lui Vali are aceeași proprietate ca celelalte bilete, cu o singură excepție: Vali nu va participa cu pereche la acest eveniment.

Pe parcursul desfășurării petrecerii, biletele de intrare vor avea şi rolul de bilet de tombolă. Acestea vor fi introduse într-o urnă şi câteva dintre ele vor fi extrase, iar norocoşii proprietari ai biletelor vor primi cadouri valoroase. Se mai știe că există probabilitatea ca unii participanți să vină la petrecere cu bilete falsificate, având numere identice cu cele de pe un bilet original. Acest fapt se va depista cu ușurință în momentul extragerii.

De Ziua Îndrăgostiţilor Vali a hotărât să organizeze o petrecere mare pe stadionul oraşului. La petrecere pot participa numai şi numai îndrăgostiţi care şi-au procurat biletele din timp. Biletele oricărui cuplu sunt aproape identice. Ele au proprietatea că numărul de serie are prima cifră 1 pentru băieţi şi *prima cifră 2 pentru fete, continuarea celor două numere este identică. De exemplu, dacă prietenul are biletul cu numărul 134, atunci prietena lui are biletul 234, iar dacă prietena are biletul 2234567890, atunci prietenul ei are biletul 1234567890.
Bineînțeles, că și Vali are bilet și speră să câștige un cadou. Biletul lui Vali are aceeași proprietate ca celelalte bilete, cu o singură excepție: Vali nu va participa cu pereche la acest eveniment.

Pe parcursul desfășurării petrecerii, biletele de intrare vor avea şi rolul de bilet de tombolă. Acestea vor fi introduse într-o urnă şi câteva dintre ele vor fi extrase, iar norocoşii proprietari ai biletelor vor primi cadouri valoroase. Se mai știe că există probabilitatea ca unii participanți să vină la petrecere cu bilete falsificate, având numere identice cu cele de pe un bilet original. Acest fapt se va depista cu ușurință în momentul extragerii.

Cunoscând numerele de serie ale tuturor biletelor de intrare la acest eveniment, aflaţi:
a) dacă pe Vali o cheamă Valentina sau îl cheamă Valentin;
b) numărul biletului lui Vali.

Să se scrie un program care pentru un şir cunoscut determină pentru câte subsecvenţe ale şirului suma elementelor care le alcătuiesc are un anumit rest dat la împărţirea cu 3.

Astăzi e o zi specială. Împlinești 14 ani. Deja ți-ai luat buletinul. Ca să sărbătorești așa cum se cuvine acest eveniment, ți-ai invitat cei mai buni prieteni, la un concert rock, care are loc în după-amiaza aceasta. Pentru aceasta, părinții au cumpărat toate cele N locuri situate în primul rând. Din păcate, acum a început să plouă tare. S-a anunțat că ploaia durează maxim câteva ore. Organizatorii promit că vor încerca să șteargă o parte cât mai mare din scaune. După ce termini olimpiada, îți suni prietenii ca să îi întrebi câți dintre cei invitați mai vin. Afli că în total veți fi P care mergeți la concert și că, doar K dintre ei acceptă să stea și pe un scaun umed. Ceilalți P-K vor să stea doar pe scaune uscate. Vrei neapărat ca în timpul concertului să stați cât mai aproape unul de celălalt, astfel încât distanța dintre cel mai din stânga prieten și cel mai din dreapta prieten să fie cât mai mică posibil. Cum ești foarte emoționat, preferi să scrii un program prin care să calculezi această distanța minimă dintre primul scaun și ultimul scaun pe care să te așezi împrună cu prietenii tăi, ținând cont de dorințele lor.

Tânărul Pagnad își dorește foarte mult să se poată juca jocul lui preferat, dar pe mama lui a apucat-o curățenia prin casă. După ce s-au împărțit sarcinile el a rămas să facă curat la papuci. Acesta are papucii așezați pe două etajere, fiecare papuc are pereche. Acesta poate efectua două tipuri de operații asupra papucilor, poate să ridice un papuc și să-l pună într-un anumit loc sau să împingă un papuc.
Pagnad trebuie să aranjeze papucii astfel încât fiecare papuc să aibe perechea lângă el. Deoarece acesta este un leneș, își dorește să ridice greutăți cât mai mici, deoarece fiecare papuc este caracterizat printr-o greutate. Aflați care este greutatea maximă pe care trebuie să o ridice Pagdan. Se consideră că fiecare pereche are greutăți diferite și că nu există două perechi asemănătoare.

Ștefan a împlinit 15 ani. Fiind un pasionat membru al Clubului de Robotică, familia i-a dăruit de ziua lui foarte mulți roboți, fiecare dotat cu o armă de o anumită putere. El a așezat toți roboții în jurul său, pe circumferința unui cerc imaginar, în sensul acelor de ceasornic. Aceste dispozitive inteligente pot comunica între ele, unindu-și puterile armelor.

Cunoscând numărul de roboți, precum și puterea fiecăruia, să se scrie un program care determină:
1. Dimensiunea celei mai lungi secvențe de roboți pentru care puterile armelor lor formează un șir strict crescător.
2. O aranjare a roboților pe cerc, astfel încât suma produselor de câte două puteri vecine să fie maximă. Dacă există mai multe modalităţi de aranjare astfel încât să se obţină aceeaşi sumă maximă, se va determina cea minimă din punct de vedere lexicografic.

Să ne imaginăm faptul că la un anumit liceu există doar două clase per generație: una de Real și una de Uman. În prezent au loc înscrierile pentru clasa a IX-a. Cele două clase au fiecare câte M locuri disponibile, atât la Real, cât și la Uman. Dacă lista de elevi înscriși la o anumită clasă conține mai mult de M elevi, vor fi admiși acei M elevi care au notele cele mai mari. Ambele clase au deja M elevi înscriși, iar pentru fiecare se știe nota cu care a fost înscris la clasa respectivă.

Mai există însă N elevi, singurii încă neînscriși, care sunt privilegiați în acest proces (fiindcă au terminat gimnaziul la acest liceu). Privilegiul lor constă în următorul fapt: ei se pot înscrie acum, după ce înscrierile publice au fost încheiate, și se cunosc notele de înscriere la ambele clase. Fiecare din cei N elevi are câte două note: nota cu care ar fi înscris la Real și nota cu care ar fi înscris la Uman (acestea pot fi diferite, deoarece examenele de admitere de la cele două clase diferă). Fiecare din cei N elevi va alege să se înscrie în maxim o clasă. Ei își vor coordona alegerile astfel încât să maximizeze numărul de elevi admiși. Deoarece calculele devin destul de complicate, aceștia s-ar putea folosi de ajutorul vostru. Ei doresc răspunsul la două întrebări.

(1) Care este numărul maxim de elevi privilegiaţi care pot fi admiși dacă se pune restricția suplimentară ca toți elevii privilegiați admiși să fie admiși la aceeași clasă?
(2) Care este numărul maxim de elevi privilegiaţi care pot fi admiși dacă aceștia se pot înscrie la clase diferite?

Se consideră un tablou cu N linii şi N coloane (numerotate de la 1 la N) care conţine valoarea 1 în fiecare dintre cele NxN celule. Valorile din tablou pot fi modificate prin aplicarea a două operații codificate astfel:

• L nr, prin care se schimbă simultan toate semnele numerelor din linia cu numărul nr.
• C nr, prin care se schimbă simultan toate semnele numerelor din coloana cu numărul nr.

Cerințe:

1) Dându-se o succesiune de K operații (L nr sau C nr) asupra liniilor/coloanelor tabloului inițial (în care toate celulele conțin valoarea 1) să se determine numărul valorilor pozitive din tablou la finalul executării celor K operații.
2) Să se determine numărul minim de operații L nr sau C nr, care, aplicate tabloului inițial, îl modifică astfel încât tabloul obținut să conțină exact Z valori negative.