Автор: | Пётр Митричев (идея), Александр Калужин (текст) | Ограничение времени: | 2 сек | |
Входной файл: | room.in | Ограничение памяти: | 64 Мб | |
Выходной файл: | room.out | |||
Максимальный балл: | 100 |
В комнате находятся N рядов стульев. На них необходимо усадить девочек и мальчиков следующим образом: в первом ряду должно располагаться ровно N человек, во втором — N − 1 человек, \dots, в N-м ряду будет один человек. То есть:
В первом ряду на каждом стуле может сидеть либо мальчик, либо девочка. В последующих рядах вводятся некоторые ограничения, а именно: на i-м месте ряда будет сидеть девочка тогда и только тогда, когда на предыдущем ряду на i-м и (i + 1)-м местах сидят две девочки или два мальчика. В противном случае на i-м месте будет сидеть мальчик.
Ваша задача — для заданного N вычислить максимальное возможное количество мальчиков при таких ограничениях.
В первой и единственной строке входного файла находится единственное натуральное число N (1 ≤ N ≤ 10101).
Выходной файл должен содержать единственное число без ведущих нулей — ответ на поставленную задачу.
№ | Входной файл (room.in ) |
Выходной файл (room.out ) |
---|---|---|
1 |
|
|
2 |
|
|