სუპერკენგურუ

დროის ლიმიტი: 1 წმ

მეხსიერების ლიმიტი: 1 მეგაბაიტი

შემავალი მონაცემები: stdin

გამომავალი მონაცემები: stdout

წყარო: GEOI, 2007-08, რეგიონული


ხელოვნური ინტელექტის პრობლემებზე მომუშავე მეცნიერებმა შექმნეს კენგურუს ინტელექტის დონის მქონე რობოტი, რომელსაც სახელად “სუპერკენგურუ” დაარქვეს. კენგურუს ანალოგიით მისი მოძრაობის ალგორითმი აგებულია ნახტომებზე. ამასთან, მიზნისაკენ მიმავალ გზას იგი განიხილავს რიცხვით ღერძად, რომლის ნულოვან წერტილში თავად დგას, ხოლო მიზანი განთავსებულია N-ურ წერტილში. 

სუპერკენგურუ მიზნისაკენ მოძრაობს წრფივად, წარმოსახვითი რიცხვითი ღერძის გასწვრივ. პირველი ნახტომის სიგრძე 1 ერთეულია, ხოლო ყოველი მომდევნო ნახტომის სიგრძე წინაზე ორჯერ მეტია. თუკი მორიგი ნახტომის დროს სუპერკენგურუ გადაახტა მიზანს, მაშინ ის იცვლის მიმართულებას 180 გრადუსით და თავიდან იწყებს ნახტომების კეთებას, ანუ ჯერ ხტება 1 ერთეულზე, მერე 2, 4, 8 და ა.შ. 

მიზანი მიღწეულად ითვლება მხოლოდ მაშინ, როდესაც სუპერკენგურუ მოხვდება N-ურ წერტილში.

დაწერეთ პროგრამა, რომელიც მოცემული N რიცხვისათვის (0<N<1,000,000,000), გამოთვლის მიზნამდე მისასვლელ ნახტომების რაოდენობას.

შესატანი მონაცემები:  ერთადერთ სტრიქონში წერია ერთი მთელი N რიცხვი – მანძილი სუპერკენგურუსა და მიზანს შორის. 

გამოსატანი მონაცემები:  ერთადერთ სტრიქონში იწერება ერთადერთი რიცხვი – ნახტომების რაოდენობა. 

 




მაგალითები

შესატანი მონაცემები
13 დაკოპირება
გამოსატანი მონაცემები
7 დაკოპირება

შენიშვნა

რიცხვით ღერძზე სუპერკენგურუს მიერ განვლილი წერტილებია:

0, 1, 3, 7, 15, 14, 12, 13 – სულ 7 ნახტომი.