C. Меншиков, Услада, Хорас ба хөзрөн байшин

хугацааны хязгаарлалт 1 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Санкт-Петербургийн амьтны хүрээлэнгийн Меншиков, Услада гэх хоёр баавгай, Киев хотын амьтны хүрээлэнгийн Хорас заан гурав хөзрүүдээр байшин барихаар шийдсэн. Үүний тулд тэд $n$ хөзрүүдээр тоглох нэлээд том тавцан аль хэдийнээ олсон. Тэдний хийхийг хүссэн байшинг тайлбарлая:

  1. Байшин нь ямар нэг хоосон биш тооны давхруудааас бүрдэнэ.
  2. Давхар бүр нь нэг хоосон биш тооны өрөөнүүд болон таазнаас бүрдэнэ. Өрөө гэдэг нь бие биелүүгээ налсан хоёр хөзөр юм. Өрөөнүүдийг дараалан хийх бөгөөд зэргэлдээ хоёр өрөө бүр нь өөр нэг хөзрөөр хийсэн таазыг хуваалцана.
  3. Үүнээс гадна давхар бүр нь доод давхраасаа дор хаяж нэгээр цөөн тооны өрөө агуулах ёстой.

Байшин нэгээс илүү өрөөтэй давхраар дуусна гэдгийг анхаарах хэрэгтэй бөгөөд энэ тохиолдолд тааз ч бас хамрагдсан байх ёстой. Мөн зэргэлдээ давхруудын өрөөнүүдийн тоо нь заавал нэгээр зөрүүтэй байх албагүй, ба нэгээс илүү зөрүүтэй байж болно.

Байвгайнууд хөзрүүдийг тавиж байх хооронд Хорас байшин хэдэн давхраас бүтэхийг мэдэхээр оролцдог. Байшингийн өндөр нь давхруудын тоо байна. Та $n$ хөзрүүдээр өөр өндрүүдтэй өөр өөр олон байшин хийх боломжтой юм. Заан энэ асуудлыг шийдэж чадахгүй юм шиг харагдаж байгаа учраас танаас хэдэн ширхэг ялгаатай өндөртэй байшин барьж болохыг асууж байна. Тэд байшин барихад яг $n$ хөзрүүд ашиглаж байгаа.

Оролт

Нэг мөрөнд хөзрүүдийн тоо болох $n$ ($1 ≤ n ≤ 10^{12}$) бүхэл тоог оруулна.

Гаралт

$n$ хөзрүүдээр барьж чадах ялгаатай өндөртэй байшингуудын тоог хэвлэ.

Орчуулсан: Даариймаа

Жишээ тэстүүд

Оролт
13
Гаралт
1
Оролт
6
Гаралт
0

Тэмдэглэл

Эхний жишээнд та хоёр байшин барьж чадна (та бүх хөзрийг ашиглах ёстойг санаарай):

13 хөзрөөр зөвхөн хоёр давхар байшин л барихад хангалттай, тиймээс хариулт 1 байна.

Хоёр дахь жишээнд 6 хөзөр нь байшин барихад хангалттай биш юм.

Сэтгэгдлүүдийг ачааллаж байна...