.campion
conectare | înregistrare | căutare
Pagina principală » Probleme » barfa

ultima problemă
grupă: mică
sursă: OMI 2016
ultimul articol
autor: Prof. Radu Vişinescu
ultimul software
autor: Prof. Emanuela Cerchez
 .campion
bârfa


Timp maxim de execuţie/test:
0.6 secunde
Memorie totala disponibilă/stivă:
16 MB/1 MB

Miruna tocmai s-a angajat intr-o firmă în care există 2N - 1 angajaţi. Aceştia sunt organizaţi pe N niveluri ierarhice, astfel: pe primul nivel ierarhic există un manager principal, care are exact doi subalterni direcţi, aceştia aflându-se pe al doilea nivel ierarhic. Cei doi subalterni au şi ei câte doi suboronaţi direcţi, care se află pe cel de-al treilea nivel ierarhic. Toţi ceilalţi angajaţi au la rândul lor câte doi subordonaţi, mai puţin cei de pe ultimul nivel ierarhic, care nu sunt şefii nimănui.

Cei 2N - 1 angajaţi au numere unice de identificare de la 1 la 2N - 1. Un lucru foarte interesant pe care l-a observat Miruna este urmatoarea regulă: pentru un anumit angajat cu numărul de identificare X, unul din cei doi subalterni direcţi are numărul de identificare mai mic decât X, iar celălalt subaltern mai mare decât X. Deasemena, subordonaţii direcţi ai subalternului cu numărul de identificare mai mic decât X, au la rândul lor numere de identificare mai mici decât X. Subordonaţii direcţi ai celuilalt subaltern au numere de identificare mai mari decât X. Acelaşi raţionament se aplică în continuare, până la angajaţii de pe ultimul nivel ierarhic. Pentru mai multe detalii despre organizarea internă a firmei puteţi consulta imaginea alăturată.

De curând, un anumit angajat cu numărul de identificare A a aflat o bârfă importantă despre Miruna. El vrea sa îi spună această bârfă angajatului cu numărul de identificare B. Din păcate, un anumit angajat nu poate să comunice decât cu şeful direct, sau cu subordonaţii direcţi. Pentru a transmite bârfa este necesar exact un minut.

Cerinţă

Ştiind că traseul de transmitere a bârfei este minim şi că un angajat transmite bârfa mai departe imediat cum o află, se cere sa determinaţi câte minute trec până când angajatul cu numărul de identificare B aude la rândul său veştile.

Date de intrare

Fişierul de intrare barfa.in conţine pe prima linie un număr natural T reprezentând numărul de teste ce vor urma. Urmatoarea linie contine două numere naturale A1 şi B1 - valorile pentru primul test. Pentru toate celelalte teste va veţi folosi de următoarea recurenţă: Ai = (Ai-1 * i) % 1000003 şi Bi = (Bi-1 * i) % 1000003 (veţi avea nevoie de numere întregi pe 64 de biţi pentru recurenţă).

Date de ieşire

Fişierul de ieşire barfa.out va conţine T linii, pe ficare linie aflându-se un număr natural reprezentând numărul de minute necesar pentru transmiterea bârfei pentru fiecare test in parte.

Restricţii şi precizări

  • 1 <= T <= 106
  • 1 <= A, B < 1000003
  • Numărul total de angajaţi este destul de mare încât să existe angajaţii cu numerele de ordine A şi B
  • Pentru 70% din teste 1 <= T <= 105

Exemple

barfa.in barfa.out
5
1 2
1
1
3
3
7

Andrei Grigorean
Facultatea de Matematică şi Informatică, Universitatea din Bucureşti
andrei.grigorean@gmail.com
propunător: Prof. Emanuela Cerchez
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
De la .campion 2008: celule, premii, cai, scp, forum, vedete, film, finala, ab, nice, supertri, mod3, degrade, fractii, balanta, inginer, camp, ozn, hora, trei, rebus, sl, detinut, fbr, noroc, simetric, egal, manevre, connect3, gropi, nrcuv, ruleta, carti, pod, bonuri, tgv, fib, uscat, 2sir, atac, matrice2, zeratul, afise, an, dezbateri, test, miniasm, platforma, lac, vopsea, harta, nrbun2, nrbun, bunici, opmat, acop, tren, cub, picnic, cursa, rv, compus, comun, magic, votare, onu, tramvai, bipal, nspecial, retea, secvop
De acelaşi autor: fbr, 2sir, platforma, sumdif, cartonase, desen, seif, kinder, shgraf, pikachu, dist1, subgeom, submatrix1, teroristi, parpal, bubblesort
Despre arbori: bonuri, tgv, votare, arce, balaur, trains, bile2, vmem, plopi, caravane, mese, strict, tree, sub, kinder, firma1, albinuta, rlcs, masina, omizi, concurs1, latime, piloti, barca1, arbnr, sirag1, pikachu, arb, logn, maxq, arbore, bcast, mesaj1, traseu, asmax, salvare, tramvai1, omida, sediu, string, tv, izo, zoo, ratina, vitale, camion1, arbfind, cezar1, tcast, dep, curent, spp, frunze, sea2, culori, color, urgenta, nori, treegame, antipatie, scanduri, minuni, arb1, activ, regat, kdtree, autostrazi, carray, trenuri1, arbgraf, war, mess, secvnumber, subs, posta, radare, arbore1, hacker, lista, codarb, subsecvente, confuzie, transform, arbsum, copaci3, arbvalmax
Despre arbore binar de căutare: acolor
Despre LCA: casute, hacker, wg
Despre operaţii pe biţi: cod, gray, cartonase, plimbare, excursie, xor, vector, ro, nrbinar, radio, chimie2, dans, metro, caini, newcomp, viteza, bcast, aritma, pereti, morse, paritate, gradina, xor2, game1, efect, gxor, lgdrum, qtri, patrate7, panda, cript
surse trimise | ajutor