Fişierul intrare/ieşire:reginald.in, reginald.outSursăCerc informatică Vianu
AutorCristian Francu, Victor ManzAdăugată defrancuCristian Francu francu
Timp execuţie pe test2.3 secLimită de memorie36000 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

Reginald

Lui Reginald Barclay îi este frică de transportorul cuantic. Atît de frică încît de fiecare dată cînd poate preferă să ia naveta spaţială spre planetă şi înapoi spre Enterprise. Într-o zi, în drum spre Bajor, naveta s-a defectat, prăbuşindu-se undeva în Kendra. Reginald este acum nevoit să ia antigravul pînă în Rakantha, destinaţia sa. Este o călătorie lungă, iar şoselele pe Bajor sînt în stare jalnică după lunga ocupaţie Cardassiană. Reginald îşi umple timpul în vreme ce pilotul automat îl anunţă monoton cîte ore mai sînt pînă la destinaţie.

El atribuie numerelor de pe bornele kilometrice o putere, astfel: mai întîi găseşte cel mai mic divizor diferit de 1. Apoi împarte numărul la acest divizor de cîte ori poate. Apoi caută următorul divizor şi împarte numărul rămas de cîte ori poate. El continuă această procedură pînă ce numărul nu mai are divizori mai mari ca 1. Pentru fiecare divizor găsit puterea numărului creşte cu 1. De exemplu, pentru numărul 12 Reginald găseşte ca cel mai mic divizor pe 2. Puterea numărului creşte cu 1. Împarţind la doi de cîte ori putem obţinem noul număr 3. Următorul divizor este chiar 3 şi puterea creşte cu 1. Împărţim numărul la 3 şi procedeul se termină. Astfel, puterea lui 12 este 2.

Cînd intră pe o nouă autostradă i, Reginald îşi alege o putere pi. El notează kilometrul de intrare xi, şi apoi calculează pentru fiecare kilometru, începînd cu xi, puterea sa. La ieşire îşi notează kilometrul de ieşire yi şi puterea pi. Astfel, cînd ajunge in Rakantha, el se trezeşte cu o listă de n tripleţi de forma (xi, yi, pi). Din nefericire el a uitat să îşi noteze numărul de kilometri calculaţi cu puterea pi. Puteţi să îl ajutaţi să-l recalculeze?

Cerinţă

Date n segmente de autostradă de forma (xi, yi, pi) să se calculeze pentru fiecare segment cîţi kilometri au puterea pi.

Date de intrare

Pe prima linie a fişierului de intrare reginald.in se găseşte n, numărul de segmente de autostradă prin care a trecut Reginald. Pe următoarele n linii vom avea cîte trei numere, reprezentînd xi, kilometrul de intrare pe acel segment, yi, kilometrul de ieşire de pe autostradă, precum şi puterea pi a kilometrilor urmăriţi.

Date de ieşire

În fişierul de ieşire reginald.out pentru fiecare segment de autostrada i se cere să se afişeze numărul de kilometri calculaţi de Reginald ca avînd puterea pi.

Restricţii

  • 1 ≤ n ≤ 1000000
  • 0 ≤ pi ≤ 2500
  • 1 ≤ xi ≤ yi ≤ 4000000
  • pentru 30% din teste 1 ≤ xi ≤ yi ≤ 100000
  • pentru 50% din teste 1 ≤ xi ≤ yi ≤ 1000000

Exemple

reginald.inreginald.outExplicaţie
3
1 6 2
5 10 3
3 8 1
1
0
5
Există doar un număr cu putere 2 între 1 şi 6 şi anume 6.
Nu există nici un număr cu putere 3 între 5 şi 10.
Există 5 numere cu putere 1 între 3 şi 8 şi anume 3, 4, 5, 7, 8.
5
9 15 2
1 10 0
23 32 3
1 30 4
3 31 1
4
1
1
0
16
Există 4 numere cu putere 2 între 9 şi 15 şi anume 10, 12, 14, 15.
Există doar un număr cu putere 0 între 1 şi 10 şi anume 1.
Există doar un număr cu putere 3 între 23 şi 32 şi anume 30.
Nu există nici un număr cu putere 4 între 1 şi 30.
Există 16 numere între 3 şi 31 cu putere 1 şi anume 2, 3, 4, 5, 7, 8,
9, 11, 13, 16, 17, 19, 23, 25, 27, 29, 31
Trebuie sa te autentifici pentru a trimite solutii. Click aici