Fișierul intrare/ieșire zaphod.in, zaphod.out Sursă ad-hoc
Autor Cătălin Frâncu Adăugată de avatar Catalin.Francu Cătălin Frâncu Catalin.Francu
Timp de execuție pe test 0.2 sec Limită de memorie 512 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 emptystea de rating de tip empty
open book Poți vedea testele pentru această problemă accesând atașamentele .

Zaphod

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 xkxk-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 zaphod.in conține un singur număr, N.

Date de ieșire

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

Restricții

  • 1 ≤ N ≤ 10.000.000
  • pentru 40% dintre teste, N ≤ 100.000

Exemplu

zaphod.in zaphod.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.

Trebuie să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 5 categorii