B. Товчлуурууд

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

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

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

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

Манао нэлээд чадвар шаардсан цоож онгойлгохыг оролдож байна. Цоож $n$ товчлууртай ба онгойлгохын тулд тогтмол дарааллаар товчлуурыг дарах хэрэгтэй. Товч дарах үед хэрэв зөв товчлуураа дарсан бол дараастай чигээр үлддэг (энэ нь зөв таасан гэсэн үг ба дарагдсан товчлуурын дараачийн товчлуур луу шилжих боломжтой гэсэн үг) ба эсрэг тохиолдолд бүх дарагдсан товчлуурууд анхны төлөвтөө ордог байна. Бүх товчлуурууд зөв дарааллаар дарагдсан тохиолдолд цоож онгойдог байна.

Жишээ болгож гурван товчлуур дээр харуулъя. Онгойлгох дараалал нь ${2, 3, 1}$ байг. Хэрэв эхлээд $1, 3$ дээр дарвал товчлуурууд буцаад дарагдаагүй болно. Хэрэв $2$ дээр эхлээд дарвал энэ товчлуур дарагдсан чигээр үлдэнэ. Хэрэв $2$-ын дараа $1$-г дарвал бүх товчлуурууд анхны дарагдаагүй төлөвтөө орно. Хэрэв $2$-ын дараа $3$-ыг дарвал $2, 3$ хоёр товчлуур дарагдаастай үлдэнэ. Ингээд хоёр товчлуур дарсан учир цоожийг онгойлгохын тулд $1$ дээр дарахад л хангалттай.

Манао онгойлгох дарааллыг нь мэдэхгүй байгаа. Гэвч тэрээр их ухаантай учир оновчтой аргаар онгойлгохоор шийджээ. Хамгийн муудаа хичнээн удаа товчлуур дарж байж цоожийг онгойлгохыг тооцоолно уу.

Оролт

Ганц мөрөнд цоожны товчлуурын тоог илэрхийлэх $n$ $(1 ≤ n ≤ 2000)$ төө өгөгдөнө.

Гаралт

Ганц мөрөнд хамгийн муудаа хэдэн удаа Манао товчлуур дарах ёстойг илэрхийлэх тоог хэвлэнэ.

Орчуулсан: Э.Шүрэнчулуун

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

Оролт
2
Гаралт
3
Оролт
3
Гаралт
7

Тэмдэглэл

Consider the first test sample. Manao can fail his first push and push the wrong button. In this case he will already be able to guess the right one with his second push. And his third push will push the second right button. Thus, in the worst-case scenario he will only need 3 pushes.

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