PROBLEMA 13:          GHISEE
DEADLINE:             Luni, 29 martie 1999
TIMP DE IMPLEMENTARE: Dupa ce va vine ideea, 10 minute
DOMENIU:              Liste (?). Interactiunea cu un modul al Onor. Comisii
PUNCTAJ:              50 dexteri

In Romania exista multe ghisee de reclamatii (oricum, nu mai mult de
1,000,000), a caror treaba este de obicei sa plimbe oamenii de la un
ghiseu la altul. Principiul de functionare al acestui sistem diabolic
de ghisee este urmatorul: Un ghiseu poate fie sa rezolve problema
celui care vine la el, fie sa il trimita la un alt ghiseu. Un ghiseu
isi redirecteaza mereu reclamantii la acelasi ghiseu.

Ghiseele au numere distincte, nenule, cuprinse intre 1 si
2,000,000,000. Un om necajit merge la un prim ghiseu pentru a depune
reclamatia "Pierdut speranta unei vieti mai bune. O declar nula". El
intra astfel intr-un du-te-vino de la un ghiseu la altul. Omul doreste
sa stie daca plimbarile sale au vreun sfarsit. Daca da, vrea sa afle
numarul total de ghisee pe la care a fost plimbat, ca sa se poata
lauda la prieteni. Daca nu (adica daca ghiseele incep sa il "paseze"
ciclic de la unul la altul), el doreste sa stie cate ghisee se afla pe
acest ciclu, pentru a anunta mass-media.

Fie N numarul total de ghisee distincte pe la care poate fi plimbat
omul. El nu cunoaste valoarea acestui numar N, dar mai are si alte
treburi pe acasa si intentioneaza sa se lase pagubas dupa ce
efectueaza 4*N plimbari de la un ghiseu la altul.

Iata un exemplu: Fie 7 ghisee cu numerele 7, 11, 3, 9, 1, 8 si 13. Modul
in care ele isi redirecteaza reclamantii este figurat mai jos:

     7 ----> 11 ----> 3 ----> 9 ----> 1                 8 ----> 13
              ^                       |                 ^        |
              ------------------------+                 ---------+

In acest caz, N=5 (pentru ca omul poate fi plimbat pe la 5 ghisee,
celelalte doua fiindu-i inaccesibile). El are la dispozitie 4*5=20 de
deplasari de la un ghiseu la altul pentru a-si da seama ca ghiseele il
plimba ciclic si ca in acest cerc vicios intra 4 ghisee (11, 3, 9, si 1).

Programul vostru va trebui sa interactioneze cu modulul GHISEU.H,
respectiv GHISEU.TPU, pe care vi-l furnizam noi, care va fi inclus in
codul sursa cu comanda:

   Pascal: uses Ghiseu;
   C:      #include "ghiseu.h"

Modulul furnizeaza doua functii:

1) Pascal: function GimmeFirst:Longint;
   C:      long GimmeFirst(void)

Aceasta functie indica numarul primului ghiseu la care trebuie sa
mearga omul. Puteti apela functia de cate ori doriti.

2) Pascal: function GimmeNext(X:Longint):Longint;
   C:      long GimmeNext(long X)

Aceasta functie indica la ce ghiseu este trimis omul cand ajunge la
ghiseul cu numarul X. Pentru exemplul de mai sus, GimmeNext(11) va
intoarce intotdeauna 3. Daca functia intoarce valoarea 0, inseamna ca
ghiseul X rezolva problema reclamantului. Aveti voie sa apelati
aceasta functie de maxim 4*N ori; repetam ca valoarea lui N nu se da,
ci trebuie dedusa.

Programul vostru va trebui sa tipareasca pe ecran:
a) Daca lantul de ghisee se inchide ciclic:
Ma dau batut. Ciclul are P ghisee.

b) Daca lantul de ghisee se termina la un moment dat:
Am rezolvat reclamatia. Am vizitat Q ghisee.

Pentru exemplul de mai sus, va trebui sa tipariti:
Ma dau batut. Ciclul are 4 ghisee.

Un test se considera picat in oricare din situatiile:
1) Da un raspuns gresit;
2) Apeleaza de mai mult de 4*N ori functia GimmeNext;
3) Apeleaza functia GimmeNext trimitandu-i ca parametru un numar
   inexistent de ghiseu (pentru exemplul de mai sus, un numar din
   afara multimii  {1, 3, 7, 8, 9, 11, 13}).
4) Depaseste un timp de rulare de 3 secunde. Se garanteaza ca 4*N
   apeluri ale functiei GimmeNext si (sa zicem) 10 apeluri ale
   functiei GimmeFirst nu depasesc o secunda.

Incheiem cu doua exemple simple de module pe care le puteti folosi, care
simuleaza urmatoarea structura de ghisee:

     1 ----> 2 ----> 3 ----> 4 ----> 5
             ^                       |
             ------------------------+

******************************* GHISEU.PAS *******************************
unit ghiseu;
interface

function GimmeFirst:Longint;
function GimmeNext(X:Longint):Longint;

implementation
var NCalls:Longint;

function GimmeFirst:Longint;
begin
  GimmeFirst:=1;
  NCalls:=0;
end;

function GimmeNext(X:Longint):Longint;
begin
  if (X<1) or (X>5)
    then begin
           WriteLn('S-a ajuns in balarii!');
           Halt; { Terminare cu succes }
         end;
  Inc(NCalls);
  if (NCalls>20)
    then begin
           WriteLn('Prea multa alergatura!');
           Halt; { Terminare glorioasa }
         end;
  if X=5 then GimmeNext:=2
         else GimmeNext:=X+1;
end;

end.

******************************** GHISEU.H ********************************
#include <stdio.h>
#include <process.h>

long NCalls=0;

long GimmeFirst(void)
{ return 1; }

long GimmeNext(long X)
{ if (X<1 || X>5) { puts("S-a ajuns in balarii!");
                    exit(0); } // Terminare cu succes
  if (++NCalls>20) { puts("Prea multa alergatura!");
                     exit(0); } // Terminare glorioasa
  return (X==5) ? 2 : X+1;
}