На чердаке дома в Простоквашино Шарик нашел странный прибор. Дядя Фёдор быстро понял, что это — ручной механический счетчик, и, как написано в его любимой энциклопедии, это «ручной механизм, для подсчитывания повторяющихся событий нажатием кнопки на счётчике, чтобы не использовать ручку и бумагу для их записи или чтобы не держать эти числа в уме».
Внутри такой счетчик устроен следующим образом: в нем есть три диска с надписанными на ребре цифрами от 0 до 9. Диски надеты на ось, к которой подсоединена кнопка. Изначально на каждом из трёх дисков записана цифра 0. При нажатии на кнопку один или несколько дисков проворачиваются так, чтобы записанное в данный момент на счетчике число увеличилось на 1. Каждый диск при нажатии на кнопку проворачивается только на одно число вперед. Если за одно нажатие проворачивается несколько дисков, сначала проворачиваются диски, соответствующие более младшим разрядам числа, а потом — более старшим.
Например, пусть cейчас на счетчике написано число 18. Это значит, что на первом диске установлена цифра 0, на втором — 1, на третьем — 8. Следующее число после 18 — 19, поэтому при нажатии кнопки третий диск провернется на одно число, чтобы на нем оказалось установлена цифра 9, а остальные останутся неподвижными. Теперь на счетчике будет написано 19. После еще одного нажатия на счетчике должно будет оказаться число 20. Это значит, что третий диск должен про- вернуться на одно число, чтобы на нем оказалось установлена цифра 0, и что второй диск тоже должен провернуться, чтобы на нем оказалась установлена 2.
Чтобы испробовать свою находку в деле, Шарик не придумал ничего лучше, как посчитать ворон, пролетающих мимо окна. Поскольку счетчик, который нашёл Шарик, очень старый, при повороте каждого из дисков раздается щелчок. Дядя Фёдор, сидевший рядом, посчитал все щелчки, которые услышал. Теперь он хочет понять, сколько ворон пролетело мимо их окна, т.е. какое число записано на счетчике.
Вводится одно целое число n: сколько щелчков насчитал дядя Фёдор (\(0 \le n \le 1107\)).
Выведите одной целое число: количество пролетевших мимо окна ворон. Если же дядя Фёдор ошибся, и такое количество щелчков не могло прозвучать, выведите −1.
9
9
10
-1
Начались каникулы, и дядя Фёдор, изрядно соскучившись по своим школьным друзьям, пригласил их всех в гости к себе в Простоквашино. После некоторых раздумий \(n\) из них согласились приехать. Взяв с собой все необходимые для отдыха на природе вещи, они приехали на вокзал покупать билеты. Выяснилось, что в поездах, идущих до Простоквашино, есть только купейные вагоны. В каждом вагоне всего \(k_4\) четырехместных купе и \(k_2\) — новых двухместных купе. Кроме друзей дяди Фёдора, никто не хочет ехать в Простоквашино, поэтому все места в поезде пока свободны. Друзья решили, что они хотят поехать все в одном вагоне: вместе ведь веселее. Чтобы поездка запомнилась надолго, один из друзей дяди Фёдора, Женя, решил одолжить у папы фотоаппарат «Зенит» и сфотографировать всех участников поездки, сидящих каждый на своем месте в поезде, по одному снимку на купе. Но пленка дорогая, а проявка — это долго и нудно, поэтому Женя попросил купить билеты так, чтобы вся дружная компания занимала как можно меньше купе. Помогите Жене посчитать, сколько в лучшем случае ему понадобится кадров, чтобы сфотографировать всю компанию, то есть посчитайте, сколько минимально купе они должны занять.
В первой и единственной строке вводятся числа \(n\), \(k_4\) и \(k_2\) — количество друзей дяди Фёдора, едущих в Простоквашино, количество четырехместных купе в вагоне и количество двухместных купе в вагоне соответственно (\(1 \le n \le 10^{18} , 0 \le k_4 \le 10^{18} , 0 \le k_2 \le 10^{18}\)).
Выведите одно целое число — минимальное количество купе, в которых можно разместить всех друзей дяди Фёдора. Если же разместить всех друзей в одном вагоне не получится, выведите −1.
При решении этой задачи используйте тип long long в С++ и int64 в Pascal/Delphi.
10 5 3
3
Когда настала зима и дел в Простоквашино стало мало, Шарик и Матроскин все дни проводили за настольными играми. Но шахматы, шашки, крестики-нлоики и домино им быстро надоели, а других игр у них не было. Поэтому они придумали новую игру.
Они выписывают на печке угольком 100 чисел. Потом по очереди каждый из них выбирает число с правого или левого края, прибавляет его к своей сумме и стирает число. Начинает игру Матроскин. Он выигрывает, если сможет набрать сумму, не меньшую, чем Шарик. По заданным числам определите, кто выиграет при оптимальной игре.
В единственной строке записаны через пробел 100 чисел \(a_i\) (\(1 \le a_i \le 1000\))
В ответ выведите Matroskin, если выигрывает Матроскин, иначе выведите Sharik. Если выигрывает Матроскин, то на следующей строке выведите оптимальный первый ход Матроскина: если он должен взять самое левое число, то выведите «left», если он должен взять самое правое число — выведите «right». Если Матроскину не важно, какое из чисел взять, выведите любое из слов «left» и «right».
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2
Matroskin right
Теория относительности — штука сложная. Это Максим, семилетний сын одного известного физика, знает уже давно. Из отцовских объяснений Максим понял, что свет — это самая быстрая штуковина в мире. А если кажется, что что-то все-таки быстрее, чем свет, то на самом деле оно движется со скоростью, равной скорости света — 299 792 458 м/с.
Так что по пути на море, убегая по поезду Москва-Адлер от чем-то очень недовольного папы, Максим совершенно не думал над тем, за что именно он сейчас получит и можно ли это было как-то предотвратить. Волновало его одно: с какой скоростью его папа бежит относительно Земли, если учесть теорию относительности? Поезд едет из Москвы в Адлер со скоростью \(v\) м/c, а папа бежит за Максимом в сторону головы поезда со скоростью \(u\) м/с относительно поезда.
Даны два числа \(v\) и \(u\) — скорость поезда относительно Земли и скорость папы Максима относительно поезда соответственно. Обе скорости неотрицательны и не превышают скорости света (299 792 458 м/с).
Выведите одно число — скорость папы Максима относительно Земли, найденную с учетом представлений Максима о теории относительности.
120 35
155
149896229 149896230
299792458
В младшей группе детского сада «Телепузики» всего \(n\) детей. Каждый из них, как и любой четырехлетка, легко может начать плакать просто из-за того, что его одногруппники тоже плачут. Ну и что, что он не знает, в чем дело? Товарищи же не могут ошибаться.
Воспитательница работает в детском саду уже много лет, и отлично разбирается в детском настроении. Ей достаточно посмотреть на ребенка, чтобы понять, насколько он сегодня плаксив: заплачет ли он сегодня сам из-за того, что компот невкусный, разрыдается ли из-за того, что Катя и Ваня уже плачут, а он еще нет, или же будет сосредоточенно играть c кубиками, не обращая внимание на слезы и сопли товарищей.
Зная сегодняшнюю плаксивость каждого из детей, определите, будет ли сегодня рыдать вся группа одновременно, или обойдется без массовой истерики.
В первой строке дано целое число \(n\) (\(1 \le n \le 1000\)) — количество детей в группе. В следующей строке через пробел перечислены \(n\) чисел, причем \(i\)-е по счету число \(q_i\) (\(0 \le q_i \le n − 1\) ) обозначает плаксивость \(i\)-го ребенка. Число \(q_i\) обозначает количество детей, которые должны заплакать, чтобы этот ребенок тоже заплакал. Если \(q_i\) = 0, значит, этот ребенок точно сегодня заплачет просто так, вне зависимости от своих товарищей. Считается, что ребенок не может начать плакать, если вокруг него не плачет нужное количество детей. Если ребенок начал плакать, то он уже не успокоится до вечера.
Выведите «YES», если вся группа будет плакать одновременно, или «NO» иначе.
4 1 0 1 2
YES
3 1 1 1
NO