Rezolvari pentru Etapa 7

Problema 1: A fost odata...
Problema 2: Colonii pe Marte
Problema 3: Din nou zerouri...


Problema 1: A fost odata...

Iata ce-ar fi de spus despre "A fost odata...".

In primul rand, enuntul problemei nu imi apartine. Il puteti gasi in volumul
"Introduction to Algorithms" de Thomas H. Cormen, Charles E. Leiserson si
Ronald L. Rivest, editata de McGraw-Hill Company (problema nr. 4-7, pagina 85).
Acolo problema este numai propusa; iata metoda mea de rezolvare:

1. Ideea de baza este sa se efectueze cel mult N-1 teste pentru a determina un chip bun.
Apoi, folosind acest chip ca martor, putem afla adevarul despre toate celelalte
N-1 chip-uri. Maximul necesar este deci de 2N-2 teste (vedeti, am fost darnic :) ).
Sa vedem acum cum anume aflam care chip este sigur bun.
--------------------

2. Problema admite o rezolvare "divide et impera". Ne propunem ca, efectuand N/2 teste,
sa reducem problema la una echivalenta, dar de dimensiune mai mica (cel mult N/2 chip-uri).
Cu alte cuvinte, urmarim ca dupa N/2 teste sa putem selecta N/2 chip-uri din care mai
mult de jumatate sunt bune. Daca reusim acest lucru, putem reaplica procedeul pentru
chip-urile selectate: efectuam N/4 teste si selectam cel mult N/4 chip-uri din care mai
mult de jumatate sunt bune s.a.m.d. Cate teste vom efectua in final ?

N/2 + N/4 + N/8 + ... + 2 + 1 = N-1

(am presupus pentru inceput ca toate impartirile au valori intregi).

Ce am obtinut in urma acestor injumatatiri repetate ?
O multime cu un singur chip, din care "mai mult de jumatate sunt bune" :).
Cu alte cuvinte, am reusit sa izolam un chip bun.
--------------------

3. Ne apropiem de partea cea mai interesanta: cum putem ca dintr-o multime de N chip-uri
sa pastram cel mult N/2, astfel incat sa avem garantia ca peste jumatate din ceea ce
pastram sunt chip-uri bune ?

Incepem prin a grupa chip-urile doua cate doua: 1 cu 2, 3 cu 4 etc. (vom presupune in
continuare ca N este par si vom discuta mai tarziu ce se intampla cand N este impar).
Apoi testam cele N/2 cupluri formate. Dupa cum am spus, daca raspunsul primit este
"Bun-Bun" (il vom nota cu 11), inseamna ca fie ambele chip-uri sunt bune, fie ambele
sunt proaste. Ele sunt in orice caz IDENTICE. Daca raspunsul este "Bun-Prost"
(notat "10") sau "Prost-Prost" (notat cu "00"), atunci stim ca cel putin un chip din
cele doua este prost.

Cum triem chip-urile pe baza acestor informatii ?
Daca raspunsul primit pentru doua chip-uri este "10" sau "00", putem "arunca" ambele
chip-uri. De ce ? Pentru ca stim ca avem N chip-uri, intre care cele bune sunt
majoritare.
Dintre acestea, noi "aruncam":

- fie un chip prost si unul bun, caz in care chip-urile bune vor ramane majoritare,
- fie doua chip-uri proaste, caz in care cu atat mai mult cele bune vor fi majoritare si
in continuare.

In felul acesta, din cele N chip-uri vor mai ramane doar N'<=N, restul fiind aruncate.
Aceste N' chip-uri sunt grupate in perechi de chip-uri IDENTICE, mai mult de jumatate
din ele fiind bune. Un exemplu ar putea fi:

00 11 00 00 11 11 11 00 11 11 (1 = chip bun, 0 = chip prost)

Noi nu cunoastem de ce tip (bun/prost) este fiecare pereche de chip-uri. Dar daca
selectam cate un chip din fiecare pereche si il aruncam pe celalalt, in mod sigur mai
mult de jumatate din chip-urile alese vor fi bune. Pentru exemplul nostru, vom alege
chip-urile:

0 1 0 0 1 1 1 0 1 1

Daca din cele N' chip-uri, N1 erau bune si N0 erau proaste, cu N1>N0, atunci din cele
N'/2 chip-uri pastrate, N1 / 2 vor fi bune si N0 / 2 vor fi proaste si evident
N1 / 2 > N0 / 2. Astfel, am redus problema la o dimensiune

N'/2 <= N/2.
--------------------

4. In cazul in care imperecherea se poate face intotdeauna (N este mereu par), algoritmul
merge foarte simplu. Ce ne facem insa daca la un moment dat ramanem cu un numar impar
de chip-uri ? Iata un exemplu cu 7 chip-uri:

11 11 00 0

Daca selectam trei chip-uri din cele trei perechi si il pastram si pe al saptelea, atunci
vom obtine configuratia 1100, in care nu avem mai mult de jumatate din chip-uri bune
(si in cazul acesta se poate arata ca nu putem afla care sunt chip-urile bune). Iata
insa si un alt exemplu din care rezulta ca nici nu putem sa aruncam chip-ul fara sot:

11 11 00 00 1

Daca selectam pur si simplu cate un chip din cele patru perechi, ajungem la aceeasi
configuratie, 1100. Se pare ca este necesar sa retinem chip-ul fara pereche numai in
cazul in care el este un chip bun. Numai ca... noi nu stim daca el este sau nu un chip
bun ! :)

Rezolvarea corecta este urmatoarea: sa zicem ca exista P perechi care raspund "11" si
inca un chip fara pereche. Atunci:

a) Daca P este par, vom selecta cate un chip din fiecare pereche si vom pastra si chip-ul
nepereche;

b) Daca P este impar vom selecta cate un chip din fiecare pereche si vom arunca chip-ul
nepereche;

Demonstrati ca, indiferent daca ultimul chip este sau bun sau prost, procedand conform
alternativei de mai sus vom selecta mai multe chip-uri bune decat proaste.

Ca y est !
--------------------

5. Exemplu. Sa presupunem ca avem configuratia cu 25 de chip-uri:

1111111100001111001010011

(Sa mai presupunem ca orice pereche de chip-uri proaste va da raspunsul "11", incercand
sa ne pacaleasca)
Le impartim in perechi:

11 11 11 11 00 00 11 11 00 10 10 01 1 --> 12 teste efectuate
** ** **

Le aruncam pe cele marcate cu **, deoarece raspunsul primit e "00" sau "10":

11 11 11 11 00 00 11 11 00 1

Avem noua raspunsuri "11", deci putem arunca chip-ul nepereche:

111100110

Reluam:

11 11 00 11 0 --> 4 teste efectuate

Avem patru raspunsuri "11", deci pastram si chip-ul nepereche:

11010

Din nou:

11 01 0 --> 2 teste efectuate
**

Aruncam a doua pereche pentru ca ea nu raspunde cu "11":

110

Si ultimul pas:

11 0 --> 1 test efectuat

Avem o singura pereche care raspunde "11", deci aruncam chip-ul in plus:

1

In acest moment am identificat un chip bun folosind 19 teste. Pe acesta il
vom folosi drept "martor" pentru a le testa pe celelalte N-1.

Trimiteti orice intrebari pe adresa <fcatalin@sundy.cs.pub.ro>.
Succes mai departe !

Fisiere de intrare:1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

Fisiere de iesire: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

Deoarece nu s-a gasit o sursa care sa ia maximul de puncte se ataseaza sursa autorului.

Author: Catalin Andrei Francu

Solutia nr. 1 (Pascal) Solutia nr. 2 (C)


Problema 2: Colonii pe Marte

Dificultatea problemei a constat, poate, in algoritmul folosit.
Algoritmul Greedy nu conducea la solutia optima in acest caz.
Era un enunt simplu de aplicare a Algoritmului Ungar (denumire sub care
este foarte cunoscut la noi in tara).
Deoarece o sursa a realizat pas cu pas acest algoritm, ne-am permis
(fara sa cerem ingaduinta realizatorului programului), sa comentam sursa
primita. De fapt am fost foarte mult ajutati si de modul foarte ordonat
si clar in care a fost realizata aceasta sursa care apartine D-nului
George Stoianov.

Nici o sursa in C nu a realizat punctajul maxim.
Ne permitem sa mai dam un exemplu (tot in Pascal), deoarece sursa este
foarte scurta.

Fisiere de intrare: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

Fisiere de iesire : 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

Punctajul acordat, respectiv pe testele date, a fost:
1 1 1 1 1 1 1 2 2 2 2 2 2 3 3 = 25 puncte.


Va dorim mult succes in continuare.

Solutia nr. 1 (Pascal) Solutia nr. 2 (C++)


Problema 3: Vine Mos Craciun!...

Pentru un numar format din cifrele:
c c c ....c
1 2 3 n
algoritmul ar putea fi urmatorul:
- se citeste cifra cu cifra de la ultima cifra;
- daca c <> 0 atunci in Numar_zero := c c c ....c
n 1 2 3 n-1
- daca c <> 0 atunci Numar_zero := Numar_zero + c c c ...c 0
n-1 1 2 3 n-2
- la fel daca c <> 0,
i
Numar_zero := Numar_zero + c c c ...c 00000 ;
1 2 3 i-1 0 de n-i ori
- daca c = 0 atunci se considera pentru continuarea algoritmului
i
numarul b b b ....b ..... = c c c ... c - 1
1 2 3 i-1 1 2 3 i-1
iar la Numar_zero se adauga numarul:
c c .... c + 1
i+1 i+2 n

Exemplu:

pentru 123456
Numar_zero = 12345 + 12340 + 12300 + 12000 + 10000 = 58985
pentru 1001
Numar_zero = 100 + 2 + 90 = 192
----------------------------------------
Example:

for 123456
Number_zero = 12345 + 12340 + 12300 + 12000 + 10000 = 58985
for 1001
Number_zero = 100 + 2 + 90 = 192

Pentru corectarea problemei s-a folosit un program de verificare care a
comparat cifra cu cifra fisierele .OUT

Fisiere de intrare: 1 2 3 4 5 6 7 8 9 10
Fisiere de iesire: 1 2 3 4 5 6 7 8 9 10 

Solutia nr. 1 (Pascal) Solutia nr. 2 (C)

Va dorim mult succes in continuare.

Prof. Maria si Adrian Nita
Liceul "Emanuil Gojdu" - Oradea


[Enunturile] [Etapa 1] [Etapa anterioara] [Etapa urmatoare] [Etapa curenta] [English] [Inapoi!]

Inapoi!