Fişierul intrare/ieşire:supersf.in, supersf.outSursăStelele Informaticii 2005, clasele 11-12
AutorAlexandru Mosoi, Silviu-Ionut GanceanuAdăugată de
Timp execuţie pe test0.6 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

Supersf

Era o zi torida de vara pe Marte... si la umbra unui Apeme se intalnesc Algostorm, Max Damage si Voodoo Child si se uita cu mirare la o bucata de hartie pe care era scrisa secventa de numere 1, 2, 3, 3, 4, 5, 5, 6, 6 si cam atat ca hartia era rupta... Imediat Algostorm a zis: "Evident! Fiecare numar W apare de X ori, unde X este numarul de biti cu valoare 1 din exprimarea lui W in baza 2, iar W parcurge sirul numerelor naturale, de la 1 catre infinit". Voodoo Child raspunde imediat: "Cred ca pot calcula foarte repede ce numar se afla la o pozitie anume in secventa asta...". Dupa cateva clipe de gandire Max Damage zice: "Eu zic sa o facem problema si sa o dam la Stelele Informaticii". Si,... uite unde am ajuns.

Cerinta

Pentru un numar K spuneti ce numar se afla pe pozitia K in sirul generat dupa cum a grait Algostorm.

Date de Intrare

In fisierul supersf.in se afla un singur numar intreg strict pozitiv K , scris in baza 16 fara spatii intre cifre, reprezentand pozitia elementului cautat in secventa.

Date de Iesire

Fisierul de iesire supersf.out contine un numar intreg pozitiv N , reprezentand numarul cautat (fara spatii intre cifre), evident tot in baza 16.

Restrictii si precizari

  • 1 ≤ K ≤ 16200.000
  • Pentru 65% din teste K ≤ 166.000
  • Cifrele in baza 16 sunt 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F (doar majuscule)

Exemplu

supersf.insupersf.out
43
17D
3D9618447
96D271F41F4

Explicatie

Primele elemente din secventa sunt: 1 2 3 3 4 5 5 6 6 7 7 7 8 9 9 A A B B B C C D D D E E E ... pentru restul nu mai avem hartie.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content