Fişierul intrare/ieşire:zaphod1.in, zaphod1.outSursăad-hoc
AutorCatalin FrancuAdăugată defrancuCristian Francu francu
Timp execuţie pe test0.35 secLimită de memorie512 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

Zaphod1 (clasa a 7-a)

Notă: aceasta este problema Zaphod cu limite mărite.

Preşedintele galaxiei, Zaphod Beeblebrox, doreşte să construiască o nouă rută de explorare galactică, pe o axă pornind de la centrul galaxiei spre periferie. Pe această axă vor fi amplasate N avanposturi cu provizii la coordonatele întregi pozitive distincte x1, x2, ..., xN. Centrul galaxiei are coordonata 0. Al k-lea avanpost este conectat cu precedentele prin două autostrăzi: una către avanpostul k - 1 (de lungime xk - xk-1) şi o autostradă expres către centrul galaxiei (de lungime xk). Primul avanpost este conectat numai cu centrul galaxiei. Ministerul Ecologiei şi Ecopatiei îi impune două condiţii: toate autostrăzile să aibă lungimi diferite, iar alegerea coordonatelor să fie cea mai mică în ordine lexicografică.

Dându-se un număr N, să se determine coordonata xN.

Date de intrare

Fişierul de intrare zaphod1.in conţine un singur număr, N.

Date de ieşire

În fişierul de ieşire zaphod1.out se va tipări coordonata xN.

Restricţii

  • 1 ≤ N ≤ 35.000.000
  • pentru 20% dintre teste, N ≤ 100.000
  • pentru 50% dintre teste, N ≤ 10.000.000

Exemplu

zaphod1.inzaphod1.out
6
26

Explicaţie

Coordonatele avanposturilor sunt 1, 3, 7, 12, 18, 26. Autostrăzile către centrul galaxiei au lungimile 1, 3, 7, 12, 18, 26. Autostrăzile între avanposturi consecutive au lungimile 2, 4, 5, 6, 8.

Observaţii

  • Va fi nevoie să vă determinaţi singuri anumite limite.
  • Atenţie mare la tipurile de date folosite!
Trebuie sa te autentifici pentru a trimite solutii. Click aici