Masala #0251

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

  

Fraktal

Asadullo fraktal shakllarga qiziqadi. U yangi fraktal shakl o’ylab topdi va uni quyidagi tartibda to’ldira boshladi:

  • 1-qadamda Asadullo RR radiusli aylana chizib oldi.
  • 2-qadamda 1-qadamda chizilgan aylananing atrofida 3 ta kvadrat chizdi
  • 3-qadamda 2-qadamda chizilgan kvadratlarning to’rttala qirrasida ham aylana chizdi
  • 2k2*k – qadamda 2k12*k-1 – qadamda chizilgan aylanalarning atrofida 3 tadan kvadrat chizdi
  • 2k+12*k+1 – qadamda 2k2*k – qadamda chizilgan kvadratlarning to’rttala qirrasida ham aylana chizdi

1-bosqich

2-bosqich

3-bosqich

 

Asadullo ushbu fraktal shaklning NN-qadamigacha chizib chiqish murakkab ekanligini, lekin, NN-qadamgacha jami nechta shakl chizilganini (aylana va kvadratlar) aniqlash mumkinligini  tushunib yetdi. Asadulloga NN-qadamgacha chizilgan shakllar sonini aniqlashda yordam bering.


Kiruvchi ma'lumotlar:

Kirish faylida yagona butun son, N(1N1018)N(1 ≤ N ≤ 10^{18)} soni kiritiladi.


Chiquvchi ma'lumotlar:

Chiqish faylida yagona son, NN-qadamigacha chizilgan shakllar umumiy sonini 1000000007(109+7)1000000007(10^9+7) ga bo’lgandagi qoldiqni chop eting!


Misollar
# input.txt output.txt
1
1
1
2
2
4
3
3
16
Yechimini yuborish
Bu amalni bajarish uchun tizimga kiring, agar profilingiz bo'lmasa istalgan payt ro'yxatdan o'tishingiz mumkin