Masala #0172

Xotira 64 MB Vaqt 1000 ms Qiyinchiligi 30 %
3.6 (Baholar 11)
14
Muallif: Sirojiddin

  

Golomb ketma-ketligi

Golomb ketma-ketligi G1,G2,  ,GnG_1, G_2, \space \dots \space, G_nii - elementi i soni ketma-ketlikda necha marta uchragani soniga teng bo’lgan o'suvchi ketma-ketlikdir. Ketma-ketlikning bir nechta dastlabki qiymatlari:
[1,2,2,3,3,4,4,4,5,5,5,6,6,6,6,7, ][1, 2, 2, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 6, 7, \space \dots].

Misol uchun, G1=1G_1 = 1, sababi 1 soni ketma-ketlikda bir marta uchragan. Xuddi shu kabi G4=3G_4 = 3, chunki 4 soni ketma-ketlikda 3 marta uchragan.

Golomb ketma-ketligini quyidagi formula orqali topish mumkin:

G1=1G_1 = 1
Gi+1=1+Gi+1GGi  i1G_{i+1} = 1 +G_{i+1-G_{G_i}} \space\space i \ge1

Sizning vazifangiz Golomb ketma-ketligini dastlabki nn ta hadi yig’indisini (G1+G2++Gn)(G_1 + G_2 + \dots + G_n) topishdan iborat.


Kiruvchi ma'lumotlar:

Bitta butun nn soni (1n109)( 1 \le n \le 10^9).


Chiquvchi ma'lumotlar:

Bitta butun son – masalaning javobi.


Misollar
# input.txt output.txt
1
5
11
2
12
44
Izoh:

Ketma-ketlikning dastlabki 5 ta hadi: {1,2,2,3,3}{\{ 1, 2, 2, 3, 3}\}. Ularning yig'indisi esa 11.

Yechimini yuborish
Bu amalni bajarish uchun tizimga kiring, agar profilingiz bo'lmasa istalgan payt ro'yxatdan o'tishingiz mumkin