Fișierul intrare/ieșire reginald.in, reginald.out Sursă Cerc informatică Vianu
Autor Cristian Frâncu | Victor Manz Adăugată de avatar francu Cristian Frâncu francu
Timp de execuție pe test 2.3 sec Limită de memorie 36864 KB
Scorul tău N/A Dificultate stea de rating de tip fullstea de rating de tip fullstea de rating de tip fullstea de rating de tip fullstea de rating de tip empty
open book Poți vedea testele pentru această problemă accesând atașamentele .

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.in reginald.out Explicaț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 să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 4 categorii