Lista de probleme 31

La un concurs de informatică participă 2∙N elevi împărțiți în N echipe de câte 2. Echipa poate lucra în comun la problemele propuse doar dacă au calculatoarele în rețea. Laboratorul de informatică este unul special: are 2∙N calculatoare, distribuite pe două rânduri la distanță de un metru între ele (vertical și orizontal) și N cabluri de rețea de lungime un metru. Concursul se desfășoară pe mai multe zile și nu există două zile de concurs cu aceeași configurație a rețelei.

Exemplu: pentru N=3, cei 6 elevi au fost împărțiți în 3 echipe, iar aranjarea rețelei în cele 3 zile de concurs este cea din figura de mai jos.

Administratorul laboratorului vrea să memoreze în ordine lexicografică toate configurațiile folosite în zilele de concurs. Cablul orizontal se notează prin 0, iar cel vertical prin 1. Lucrând ordonat și eficient, pentru cele trei zile el își va nota valorile: 001, 100, respectiv 111. Se observă că o reprezentare de genul 000, 010, 011, 101 nu poate fi realizată.

Cunoscând N, să se determine:

1. Numărul de zile modulo 1000000007 în care se desfășoară concursul.
2. Configurațiile laboratorului în ziua X-1 și ziua X+1, cunoscând configurația zilei X.

Pentru că s-a calificat la Olimpiada Națională de Informatică de la Craiova, NN îi pregătește lui XORin un tort. Tortul este dreptunghiular, format din linii și coloane numerotate de la 1 la N pentru linii și de la 1 la M pentru coloane. Tortul este format din bucăți de dimensiune 1x1, fiecare fiind acoperită cu un alt tip de glazură. În fiecare zi NN îi taie lui XORin câte o felie, alegând cel mai mare pătrat care conține bucăți acoperite cu același tip de glazură. În cazul în care există mai multe astfel de felii, NN o alege pe cea care are colțul din dreapta jos situat pe linia cu indicele cel mai mic. Dacă și în acest caz există mai multe posibilități, el o va alege pe cea cu colțul din dreapta jos situat în coloana cu indicele cel mai mic.

Precizați latura și coordonatele colțului din dreapta jos pentru fiecare felie de tort primită, în ordinea specificată mai sus.

Se consideră două șiruri de caractere A și B, ambele șiruri având același număr de caractere.

Asupra șirurilor se aplică următorul algoritm:

• șirul A se permută circular cu ki poziții spre stânga
• din cele două șiruri se elimină caracterele care coincid din punct de vedere al poziției și valorilor

Algoritmul se oprește când fie ambele șiruri devin vide, fie șirurile nu mai au caractere comune. Valoarea ki pentru fiecare pas i reprezintă al i-lea număr prim din mulțimea numerelor prime.

Dându-se N și M, să se genereze șirurile A și B, ambele având lungimea N, astfel încât numărul de repetări ale algoritmului aplicat celor două șiruri să fie M.

Meseria de parchetar a devenit mai uşoară de când a apărut parchetul laminat. Acesta se livrează în plăci pătratice de câte 1 m² şi montarea lui este destul de uşoară. Gigel este convins că este suficient de priceput să facă această operaţie în propria locuinţă. El dispune de planul locuinţei şi a cumpărat o anumită cantitate reprezentând X m² de parchet laminat. Planul locuinţei este descris printr-un tablou bidimensional de dimensiuni N x M, fiecare element al tabloului reprezentând exact 1 m². Pereţii sunt reprezentaţi prin caracterul ‘P’ iar suprafeţele camerelor prin caracterul ‘S’ (spaţiu). În planul din figura următoare este descrisă o locuinţă cu 5 camere acestea având respectiv, suprafeţele de 10, 2, 1, 3, 5 m².

PPPPPPPPP
PSSSPSPSP
PSSSPSPPP
PSSPPPPSP
PSPPSSPSP
PSPSSSPSP
PPPPPPPPP

Gigel nu este sigur de faptul că parchetul cumpărat îi ajunge. Din această cauză a hotărât iniţial să pună parchetul începând cu camera cea mai mare, apoi în următoarea, în ordinea descrescătoare a suprafeţei şi aşa mai departe, până în momentul în care parchetul rămas nu mai este suficient pentru acoperirea suprafeţei următoarei camere. Nu va lăsa neparchetată o cameră pentru a parcheta una cu o suprafaţă mai mică.

Gigel se mai gândeşte şi la posibilitatea de a acoperi complet un număr maxim de camere folosind întreaga cantitate de parchet.

Fiind date N, M, X şi planul locuinţei să se determine:

1. numărul C de camere pe care a reuşit să le acopere Gigel şi numărul R de m² de parchet care îi rămân, procedând aşa cum a hotărât iniţial;
2. numărul de posibilităţi de parchetare a unui număr maxim de camere, folosind întreaga cantitate de parchet.

Noile reguli din sistemul sanitar cer ca medicii să nu prescrie pe reţete un anumit medicament, ci să menţioneze substanţa activă. Reţeta este formată din n prescripţii, câte una pentru fiecare substanţă activă prescrisă.

Farmacista de la care cumpăr medicamentele mi-a făcut o listă în care pentru fiecare substanţă activă de pe reţetă sunt trecute medicamentele care conţin substanţa activă respectivă, precum şi preţul pastilelor prescrise din medicamentul respectiv, sub forma următoare:

• substanţa activă : medicament1 preţ1, medicament2 preţ2, ..., medicamentk preţk

Din păcate, între anumite medicamente există incompatibilităţi şi ca urmare ele nu pot fi administrate simultan, deoarece ar produce reacţii adverse. De aceea, farmacista mea mi-a dat şi o listă de incompatibilităţi, în listă fiind specificate perechi de medicamente incompatibile, sub forma:

• medicament1/medicament2

Când cumpăr reţeta, eu trebuie să iau câte un medicament pentru fiecare substanţă activă prescrisă de medic şi să am grijă să nu cumpăr medicamente care sunt incompatibile. Desigur, voi cumpăra pastilele prescrise pentru tratamentul complet.

Cunoscând lista pe care mi-a dat-o farmacista, precum şi incompatibilităţile dintre medicamente, scrieţi un program care să determine:

1. câte medicamente am la dispoziţie pentru fiecare substanţă activă;
2. suma minimă pe care trebuie să o cheltui pentru a cumpăra reţeta.

Se dă un șir format din N numere naturale. Pentru fiecare valoare distinctă dintr-o subsecvență cuprinsă între doi indici st si dr considerăm distanța dintre indicii primei și ultimei apariții ale acesteia în cadrul subsecvenței. Dându-se M subsecvențe de forma [st,dr], se cere să se calculeze suma distanțelor corespunzătoare tuturor valorilor distincte din subsecvență.

O matrice pătratică de dimensiuni N x N cu liniile și coloanele indexate de la 1 la N se numește matrice șmecheră de Calafat dacă pe fiecare linie și fiecare coloană există exact două valori de 1, restul elementelor fiind 0.

Având două matrice șmechere de Calafat notate cu A și B, se cere ca prin interschimbări de linii și coloane să se transforme matricea B în matricea A.

Se consideră o matrice cu un număr infinit de linii și coloane indexate începând cu 0.
Pe prima linie matricea conține șirul numerelor naturale (0, 1, 2, 3 …).
Pe fiecare linie începând cu linia a doua pe poziția j matricea conține suma xor a elementelor situate pe linia anterioara de la poziția 0 până la poziția j.

Se cere să se răspundă la q întrebări de forma “Pentru i și j date, să se determine numărul situat pe linia i coloana j a matricei”. Pentru a genera cele q întrebări vor fi cunoscute următoarele valori: \( i_1, j_1, a, b, m \).
\( i_1, j_1\) reprezintă valorile pentru prima întrebare. Următoarele întrebări \( i_k, j_k \) vor fi generate una din alta folosind următoarea regulă:

\( {i}_{k} = \left (a* {i}_{k-1} +b \right) \text{ mod } m \)
\( {j}_{k} = \left (a* {j}_{k-1} +b \right) \text{ mod } m \)

După o zi productivă de făcut curățenie, Henry și Hetty au ieșit în oraș la un restaurant de sushi. În acest restaurant există N mese unite între ele prin N-1 benzi rulante cu dublu sens, astfel încât oricare două mese sunt conectate direct sau indirect prin benzi rulante. Pentru fiecare masă i, 1 ≤ i ≤ N, cunoaștem atât numărul K[i] de mese cu care este conectată direct, cât și lista ordonată de mese vecine acesteia: V[i,1], V[i,2] … V[i,K[i]].

Benzile rulante au rolul de a transporta preparatele la clienți. Acestea urmează un traseu unic, definit după următoarea regulă: pentru orice masă i, un preparat aflat la masa i care tocmai a venit dinspre masa V[i,j], va pleca de la masa i spre masa:

• V[i,j+1], dacă 1 ≤ j < K[i]
• V[i,1], dacă j = K[i].

În plus, dacă un preparat nou este trimis de la masa 1 spre masa V[1,1], știm că acesta va ajunge la masa i pentru prima oară venind dinspre masa V[i,1], pentru orice i, 1 ≤ i ≤ N.

Henry și Hetty au intrat în restaurant la momentul de timp 0. Ei știu că pe parcursul vizitei lor pe benzile rulante vor fi așezate M preparate. Pentru fiecare din cele M preparate ei cunosc tripletul (x, y, t), semnificând faptul că la momentul de timp t preparatul va fi așezat pe bandă în dreptul mesei x pentru a pleca spre spre masa V[x,y]. Ei mai știu și că timpul necesar unui preparat de a parcurge distanța dintre două mese vecine este de o unitate. Cei doi se vor așeza la o masă și vor lua de pe bandă toate preparatele care trec prin dreptul mesei respective. Henry și Hetty se întreabă: pentru fiecare masă i, care este timpul minim după care culeg toate cele M preparate ce vor fi puse pe bandă?

Se dă un arbore (graf conex aciclic) cu N noduri. Vrem să eliminăm noduri (împreună cu muchiile adiacente) din arborele dat, astfel încât numărul de componente conexe ale grafului rămas să fie maxim. Aflați care este numărul maxim de componente conexe pe care le putem obține și câte submulțimi distincte de noduri se pot elimina din arbore astfel încât să rămână la final acest număr maxim de componente conexe.