Revizia anterioară Revizia următoare
| Fișierul intrare/ieșire | zaphod2.in, zaphod2.out | Sursă | ad-hoc |
|---|---|---|---|
| Autor | Cătălin Frâncu | Adăugată de |
Cristian Frâncu
•
francu
|
| Timp de execuție pe test | 0.05 sec | Limită de memorie | 768 KB |
| Scorul tău | N/A | Dificultate |
  4.25
|
Poți vedea testele pentru această problemă accesând
atașamentele
.
Vezi soluțiile trimise | Statistici
Zaphod2 (clasa a 10-a)
Notă: aceasta este problema Zaphod1 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 zaphod2.in conține un singur număr, N.
Date de ieșire
În fișierul de ieșire zaphod2.out se va tipări coordonata xN.
Restricții
- 1 ≤ N ≤ 2.000.000.000
- pentru 20% dintre teste, N ≤ 100.000
- pentru 40% dintre teste, N ≤ 10.000.000
- pentru 60% dintre teste, N ≤ 20.000.000
Exemplu
| zaphod2.in | zaphod2.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!
