Încercați-vă puterile!

PROBLEME propuse pentru rezolvare

Între 26 iulie - 9 august, la Constanța s-a desfășurat a doua tabără de antrenament a lotului olimpic național de informatică. La sfârșitul celei de a doua săptămâni concurenții au primit șapte probleme. Adresându-ne tuturor celor care iubesc algoritmica, vă propunem să vă încercați puterile!

P079801: Coloane

Problemă propusă de conf. dr. Henri Luchian, Universitatea "Al. I. Cuza", Iași

Se dă o matrice având elemente din mulțimea {0,1}. Să se selecteze un număr minim de coloane din această matrice astfel încât suma elementelor pe fiecare linie, luând doar elementele din coloanele selectate, să fie cel puțin 1.

Date de intrare

Pe prima linie a fișierului de intrare COLOANE.IN se află două numere naturale m și n (1Łm, nŁ200), despărțite printr-un singur spațiu, reprezentând numărul de linii și de coloane ale matricei.

Pe următoarele m linii se află elementele matricei; două elemente de pe aceeași linie sunt despărțite printr-un singur spațiu.

Date de ieșire

În fișierul de ieșire COLOANE.OUT se vor scrie datele de ieșire sub forma următoare:

Pe prima linie se va scrie numărul minim de coloane selectate.

Pe următoarea linie se vor scrie numerele de ordine ale coloanelor selectate, despărțite printr-un singur spațiu.

Dacă nu există soluție, atunci prima linie va conține un singur număr 0.

Exemplu:

COLOANE.IN COLOANE.OUT

6 5 2

1 0 1 0 0 1 3

0 1 1 1 0

1 1 1 0 1

0 0 1 0 0

1 0 0 1 1

1 0 0 0 1

P079802: Cuburi

Problemă propusă de profesorii Maria și Adrian Niță, Liceul Emanoil Gojdu, Oradea

Vom considera un mod de desfășurare a unui cub, în care fiecare față a cubului este numerotată cu o cifră de la 1 la 6. Desfășurarea cubului se poate realiza în mai multe moduri. Avem, de exemplu următoarele două moduri de desfășu-rare diferite ale aceluiași cub:

O desfășurare se descrie printr-o secvență de șase cifre, citite de sus în jos și pe fiecare linie, de la stânga la dreapta. Deci pentru exemplele date vom avea succesiunea de cifre 512346 respectiv 154623.

Cele două desfășurări de mai jos nu provin de la același cub deoarece imaginile desfășurărilor sunt "oglindite".

Scrieți un program care să distingă între două perechi de succesiuni de cifre date dacă sunt sau nu identice, în sensul că reprezintă desfășurarea aceluiași cub sau nu.

Date de intrare

Fișierul CUB.IN conține mai multe linii. Pe fiecare linie sunt scrise câte două perechi de succesiuni de cifre, forma-te din câte șase cifre distincte; succesiunile de șase cifre sunt despărțite printr-un singur spațiu.

Date de ieșire

Fișierul de ieșire CUB.OUT va conține atâtea linii câte perechi de numere au fost în fișierul de intrare. Pe fiecare linie se va scrie cuvântul 'DA', respectiv 'NU' în funcție de constata-rea că cele două desfășurări corespund sau nu aceluiași cub.

Exemplu:

CUB.IN CUB.OUT

512346 154623 DA

512346 612345 NU

P079803: Eschimoși

Problemă propusă de lect. Clara Ionescu, Universitatea "Babeș-Bolyai", Cluj

Eschimoșii au așezări în care își petrec viața, locuind în igluuri. În unele sate toate igluurile sunt așezate pe aceeași linie și astfel este suficient să existe cărare doar între oricare două igluuri vecine (spre stânga și/sau spre dreapta).

După ce Marele Eskimo a devenit regele tuturor eschimoșilor el a cerut poporului său să construiască în fiecare sat un Mare Iglu care să nu se afle pe aceeași linie de-a lungul căreia sunt așezate igluurile sătenilor. De la acesta trebuia să se croiască potecă la fiecare iglu din sat. Marele Eskimo și-a dat seama că este prea greu să-și refacă potecile după fiecare furtună de zăpadă. A ales un număr minim de poteci astfel încât:

  • să fie posibil să se ajungă de la un iglu la oricare altul (incluzând și Marele Iglu) folosind numai potecile alese;
  • între oricare două igluuri să existe un singur drum.

Scrieți un program care pentru un număr dat N de igluuri din sat, determină numărul tuturor posibilităților de alegere a potecilor, respectând cerințele problemei.

Date de intrare

În fișierul de intrare ESC.IN este scris un singur număr natural N (2ŁNŁ35), reprezentând numărul igluurilor din sat (construite de-a lungul unei linii).

Date de ieșire

În fișierul de ieșire ESC.OUT se va scrie un singur număr natural M, reprezentând numărul de posibilități în care potecile din sat pot fi construite, respectând cerințele problemei.

Exemplu:

ESC.IN ESC.OUT

3 8

P079804: Rezistențe

Problemă propusă de Valentin Gheorghiță, student, Universitatea Politehnică, București

Rezistoarele sunt componente electrice cu două capete (noduri de rețea). Un rezistor este simbolizat de obicei în felul următor:

Nu există noțiunea de capăt de intrare sau ieșire; totul depinde de modul în care circulă curentul electric. Deci un rezistor este simetric și bidirecțional.

Legarea în serie a două rezistoare este realizată astfel:

Rezultatul acestei legări în serie este echivalentul unui rezistor Re a cărui valoare este suma rezistențelor celor două componente (pentru exemplu Re=R1 + R2).

Între cele două rezistoare se consideră un singur nod, comun. În desen, nodurile sunt reprezentate astfel: ·

Rezultatul legării în paralel a două rezistoare este echivalentul unui rezistor al cărui valoare este calculată după formula (dacă cele două rezistoare componente au valorile R1 respectiv R2) :

Legarea în paralel a două rezistoare este realizată astfel:

În circuitele pe care le veți studia veți avea nevoie și de transformări de tip triunghi-stea. Aceasta este următoarea:

Problema constă în a găsi rezistențele echivalente pentru diverse rețele de rezistoare, știind că sunt necesare doar cele trei transformări prezentate (serie, paralel, triunghi-stea) și combinații ale acestora.

Scrieți un program care calculează rezistența echivalentă între două noduri ale unui circuit dat.

Date de intrare

Fișierul de intrare REZ.IN are următoarea structură:

  • pe prima linie este scris numărul N, reprezentând nu-mărul de noduri ale rețelei;
  • pe a doua linie se află o pereche de numere, reprezentând nodurile între care trebuie calculată rezistența echivalentă;
  • pe următoarele linii (mai puține decât 5001) sunt scrise triplete de forma i j k având semnificația: între nodurile i și j se află un rezistor de valoare k; cele trei numere sunt despărțite prin câte un spațiu.

Observații:

1. Toate numerele primite din fișierul de intrare sunt naturale, mai mici decât 5001.

2. Dacă între nodurile i și j sunt mai multe rezistențe atunci ele sunt legate în paralel.

Date de ieșire

Valoarea rezistenței echivalente se va scrie în REZ.OUT, cu 3 zecimale exacte.

Exemplu:

REZ.IN

5

1 5

1 2 1

1 3 1

2 3 1

3 4 1

3 4 2

4 5 1

2 5 1

REZ.OUT

1.133

P079805: Seiful

Problemă propusă de prof. Dana Lica, Liceul "I. L. Caragiale", Ploiești

Se consideră o comisie formată din n persoane (nume-rotate de la 1 la n) care trebuie să păstreze într-un seif su-biectele de la examenul de admitere.

Să se determine numărul minim de lacăte lmin necesar închiderii seifului astfel încât să existe o distribuție a cheilor lor care să îndeplinească următoarele condiții:

  • oricare două persoane dețin același număr de chei;
  • fiecare persoană deține chei de la lacăte diferite;
  • toate lacătele seifului se vor putea deschide numai în prezența oricărui grup format din cel puțin n-1 persoane.

Observații:

1. Pentru un lacăt pot exista mai multe chei care să-l deschidă.

2. Nici o cheie nu poate deschide două lacăte diferite.

3. Lacătele sunt numerotate de la 1 la lmin.

Să se determine numărul minim de lacăte, numărul total de chei distribuite și o repartizare a cheilor care respectă condițiile problemei.

Date de intrare

În fișierul de intrare SEIF.IN se va găsi numărul n (nŁ500) al membrilor comisiei.

Date de ieșire

În fișierul de ieșire SEIF.OUT se vor scrie datele de ieșire sub forma următoare:

- pe prima linie se vor scrie două numere naturale separate printr-un singur spațiu:

lmin chei

unde:

lmin reprezintă numărul minim de lacăte;

chei reprezintă numărul total de chei (de la toate cele lmin lacăte);

- pe fiecare din următoarele lmin linii se va scrie câte o secvență de numere naturale, separate printr-un singur spațiu. Pe linia i+1 se va afla șirul numerelor de ordine a membrilor care primesc câte o cheie de la lacătul i.

În cazul în care există mai multe soluții, se cere una singură.

Obsevație:

Dacă programul furnizează numărul corect pentru lmin și chei se va acorda aproximativ 25% din punctajul pentru testul respectiv.

Exemplu:

SEIF.IN SEIF.OUT

3 3 6

3 2

1 2

3 1

P07986: Piramida lui Keops

Problemă propusă de Marius Vlad, student, Universitatea Politehnică, București

În piramida lui Keops trebuie săpat un canal de la bază și până în vârful piramidei.

Piramida este construită din blocuri de piatră cubice de durități diferite. Baza sa (nivelul 0) este un pătrat și este alcătuită din N*N blocuri de piatră unde N este un număr natural impar (0<N<30). Fiecare nivel este perfect centrat peste nivelul inferior și are o lungime cu 2 blocuri de piatră mai mică decât lungimea blocului inferior. Ultimul nivel este format dintr-un singur bloc de piatră.

Duritatea fiecărui bloc de piatră este un număr natural din intervalul 0..200.

Pentru săparea canalului trebuie respectate mai multe condiții:

  • În primul rând munca depusă la săparea acestui canal trebuie să fie minimă. Înțelegem prin munca depusă suma durităților blocurilor prin care trece canalul.
  • Canalul trebuie început de pe oricare latură exterioară a bazei.
  • Canalul trebuie terminat în vârf (pe blocul de piatră de pe cel mai înalt nivel al piramidei).
  • Canalul nu poate coborî (pe un nivel inferior).
  • Între oricare două puncte de pe același nivel lungimea canalului trebuie să fie minimă. Înțelegem prin lungimea canalului între două puncte de pe același nivel numărul de blocuri de piatră prin care trece canalul (între cele două puncte specificate de pe același nivel).
  • La trecerea dintr-un bloc de piatră în altul canalul trece prin fața comună celor două blocuri.

Datele de intrare

Fișierul text PIRAMIDA.IN cu următoarea structură:

N - lungimea bazei

D0,1,1 D0,1,2 ? D0,1,n - duritatea liniei 1 din bază

D0,2,1 D0,2,2 ? D0,2,n - duritatea liniei 2 din bază

?

D0,n,1 D0,n,2 ? D0,n,n - duritatea liniei n din bază

(baza (nivelul 0) are n linii și n coloane)

D1,1,1 D1,1,2 ? D1,1,n.2 - duritatea liniei 1, nivelul 1

D1,2,1 D1,2,2 ? D1,2,n-2 - duritatea liniei 2, nivelul 1

?

D1,n-2,1 D1,n-2,2 ? D1,n-2,n-2 - duritatea liniei (n-2), nivelul 1

?

(primul nivel are n-2 linii și n-2 coloane)

?

Dk,1,1 - duritatea singurului bloc de pe ultimul nivel

ultimul nivel are o linie și o coloană

Datele de ieșire

Fișierul text PIRAMIDA.OUT care are următoarea structură:

S L - munca depusă și lungimea totală a drumului

h1 l1 c1 - coordonata primului bloc în care se sapă canalul (nivel, linie, coloană)

h2 l2 c2 - coordonata celui de-al doilea bloc în care se sapă canalul (nivel, linie, coloană)

?

hL lL cL - coordonata ultimului bloc în care se sapă canalul (nivel, linie, coloană)

Exemplu:

PIRAMIDA.IN PIRAMIDA.OUT

5

1 2 3 4 5 18 6

6 7 8 9 10 0 1 2

11 12 13 14 15 0 2 2

16 17 18 19 20 1 1 1

21 22 23 24 25 1 1 2

1 2 3 1 2 2

4 5 6 2 1 1

7 8 9

1

P079807: Rigle Golomb

Problemă propusă de conf. dr. Henri Luchian, Universitatea "Al. I. Cuza", Iași

O riglă cu n marcaje se numește riglă Golomb dacă sunt îndeplinite următoarele condiții:

1. cele n marcaje delimitează segmente de lungimi exprimate prin numere naturale; marcajul 0 (originea riglei) nu este inclus între cele n;

2. nu există pe riglă segmente de aceeași lungime (o riglă cu n marcaje are evident n segmente);

3. distanțele ce se măsoară pe riglă, și anume prin unul sau mai multe segmente consecutive, sunt diferite între ele; cu alte cuvinte, nici o distanță nu poate fi măsurată în două moduri diferite.

Dacă se adaugă condiției 3) cerința ca toate distanțele cuprinse între 1 și m (lungimea riglei) să poată fi măsurate (evident, în mod unic), atunci avem definiția unei rigle Golomb perfecte.

Exemple de rigle Golomb perfecte:

Singurele rigle Golomb perfecte sunt cele trei de mai sus. De aceea, definiția riglei Golomb perfecte trebuie relaxată pentru a o adapta la valori mai mari ale lui n. Anume, condiția 3) plus cerința suplimentară devin: orice distanță cuprinsă între 1 și m poate fi măsurată în cel mult un mod (adică, unele distanțe pot să nu fie măsurabile). Se obține astfel definiția riglei Golomb bune. Orice riglă Golomb perfectă este și riglă Golomb bună.

Exemplu de riglă Golomb bună:

Evident, avem o infinitate de rigle Golomb bune cu n marcaje, oricare ar fi n. Analoaga riglei Golomb perfecte cu n marcaje ar fi o riglă Golomb bună cu n marcaje care are lungime minimă.

Dându-se n - numărul de marcaje, să se găsească m - lungimea minimă a unei rigle Golomb bune cu n marcaje.

Date de intrare:

Fișierul GOL.IN conține un număr natural n (1ŁnŁ16).

Date de ieșire

Fișierul GOL.OUT va conține n numere naturale repre-zentând distanțele față de origine la care trebuie aplicate cele n marcaje pe o riglă Golomb bună de lungime mini-mă. Ultimul număr va reprezenta deci m, lungimea riglei.

Exemplu:

GOL.IN GOL.OUT

3 1 4 6

[cuprins]