Rezolvari pentru Etapa 5

Problema 1: Legea si orasele
Problema 2: Jocul NIM
Problema 3: Vine Mos Craciun!...


Problema 1: Legea si orasele

O prima constatare este ca nimeni nu a reusit sa rezolve problema pana la capat, singurii care au fost pe aproape sunt Ioana Ileana (7 teste din 8), Dumitru Bogdan si Cadar Cristian (6 teste din 8).
Sa analizam complexitatea programului. Cum numarul de intersectii si de sosele este cel mult 5001, deducem ca aceasta - ca programul sa se poata incadra intr-o secunda - trebuia sa fie de forma n*log(n).
Inainte de a prezenta algoritmul precizez ca nu s-a cerut nici o ordine in ceea ce priveste ordinea centurilor (adica prima centura a orasului si apoi restul centurilor, sau orice alta ordine) pentru a nu complica programul prea mult.
Problema se rezuma la aflarea fetelor unui graf planar. Fie n numarul de varfuri si m numarul de muchii ale unui graf. Numarul de fete este dat de formula :
      m-n+numarul_de_componente_conexe+1
(1 se aduna pentru fata exterioara). Dar graful e conex, deci formula devine: m-n+2. O muchie apare in exact doua fete. Daca se imparte muchia in 2 arce orientate atunci se poate face in asa fel incat fiecare arc sa apara intr-o singura fata. Pentru a gasi centurile, se pleaca pe un arc oarecare dintr-un varf si se continua parcurgerea grafului pe arcul, ce formeaza unghiul cel mai mic cu arcul pe care s-a venit.
S-a realizat o centura atunci cand s-a ajuns in varful din care s-a plecat. Toate arcele prin care s-a trecut sunt sterse din lista. S-au realizat toate centurile atunci cand graful devine vid.
Au fost 8 teste date, fiecare punctat cu 3.75. Punctajul a fost dat rotunjit.

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

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

Solutia nr. 1 (Pascal)


Problema 2: Jocul NIM

Aceasta problema nu a fost dificila, ci prin ea s-a incercat o introducere in stilul Olimpiadei Internationale de Informatica din acest an de la Cape Town, Africa de Sud. Este surprinzator faptul ca atat de putini concurenti au reusit sa obtina maximul de puncte. Jocul este cunoscut, el poate fi gasit intr-o multime de carti de informatica si in gazete de informatica. In concluzie nu este necesara explicarea strategiei jocului.
Referitor la testele de evaluare: au fost in numar de 10, fiecare avand gramezi cuprinse intre 1000 si 4000. Testele au fost verificate in prealabil pentru a se controla timpul de executie. Fiecare test a fost punctat cu 2.5 puncte in caz de castig si 0.5 puncte in cazul in care programul dvs. are "joc pierdut". Punctajul final a fost suma punctajelor pe teste, suma pe care am truncat-o.

Iata bibliotecile folosite:

NimLib.pas (Pascal)
NimLib.h (C)

Teste: 1 2 3 4 5 6 7 8 9 10

Exemple de surse bune:

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


Problema 3: Vine Mos Craciun!...

Credem ca surpriza de Craciun a fost un adevarat dar din partea noastra. Se poate vedea acest lucru din numarul mare de punctaje maxime pe care dumneavoastra le-ati obtinut. Ne bucuram mult si va felicitam pentru aceasta!

Teste

Exemple de surse frumos realizate in Pascal si C:

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

In prag de An Nou va transmitem cele mai sincere urari de sanatate si implinirea dorintelor dvs. Dorim ca si in anul urmator sa avem o buna colaborare care sa ne aduca tuturor satisfactii. Cu cele mai sincere sentimente de prietenie:

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


[Enunturile] [Prima etapa] [Etapa anterioara] [Etapa urmatoare] [Ultima] [English] [Inapoi!]

Inapoi!