Марш и Коп — всемирно известная пара враждующих археологов. В стремлении обогнать друг друга они собрали внушительные коллекции костей динозавров, представляющих собой отрезки целочисленной длины. И у Марша, и у Копа имеется ровно две кости длины 1, ровно две кости длины 2 и так до бесконечности (то есть, у каждого есть ровно две кости любой натуральной длины).
Однажды археологи решили примириться и в честь этого отдать в Смитсоновский музей прямоугольник периметра $$$P$$$. Для этого и Марш, и Коп хотят пожертвовать на строительство прямоугольника по одной паре одинаковых костей. Каким числом способов они могут это сделать, если ломать кости археологи категорически несогласны?
Программа получает на вход одно натуральное число $$$P$$$ — периметр требуемого прямоугольника ($$$1 \leqslant P \leqslant 2 \cdot 10^9$$$).
Программа должна вывести одно целое число — количество способов пожертвовать кости, чтобы из них можно было составить прямоугольник периметра $$$P$$$.
Решение, правильно работающее для $$$P \leqslant 1000$$$, наберёт не менее 60 баллов.
10
4
2
0
В первом примере Марш и Коп могут пожертвовать соответственно кости длины 1 и 4; 2 и 3; 3 и 2; 4 и 1 — всего 4 способа. Заметим, что из них сложатся прямоугольники $$$1 \times 4$$$, $$$2 \times 3$$$, $$$3 \times 2$$$ и $$$4 \times 1$$$ соответственно.
Во втором примере несложно понять, что невозможно составить даже один прямоугольник, удовлетворяющий условиям задачи, поэтому ответ ноль.
Тимофей выбрал натуральное число $$$n$$$, делящееся на 6, и записал на трёх разных карточках само число $$$n$$$, его половину и его треть. Однако, эти карточки перепутались между собой, а затем одна из них потерялась. Теперь у Тимофея есть только две карточки, на которых написаны числа $$$a$$$ и $$$b$$$. Помогите ему вспомнить, что за число было написано на третьей.
Программа получает на вход два натуральных числа $$$a$$$ и $$$b$$$ ($$$1 \leqslant a \lt b \leqslant 10^{9}$$$). Число $$$a$$$ находится в первой строке, $$$b$$$ — во второй.
Выведите одно натуральное число — ответ на вопрос задачи. Гарантируется, что входные данные таковы, что ответ cуществует, единственен и не превосходит $$$10^{9}$$$.
Решение, правильно работающее в случае, когда $$$b \leqslant 1000$$$, получит не менее 40 баллов.
4 12
6
2 3
6
В первом примере $$$n = 12$$$, его треть равна 4, а половина (потерянное число) равна 6. Можно доказать, что это единственный ответ.
Во втором примере потерялось задуманное Тимофеем число 6, на листочках остались его треть (число 2) и половина (число 3).
Студент Шурик в поисках дополнительного дохода устроился на работу — разгружать почтовые вагоны. В напарники ему дали Федю — опытного матёрого грузчика. И если щуплый Шурик с трудом поднимает бандероли весом $$$a$$$ килограммов, то могучий Федя способен перемещать посылки весом $$$b$$$ килограммов. Федя и Шурик заходят в вагон, выбирают по одной коробке, которые могут унести по отдельности, и переносят их на перрон. Если вес коробки превышает $$$b$$$, то они её переносят вдвоем. Сколько раз Федя и Шурик войдут и выйдут из вагона (ходят они только вместе и хотят закончить работу как можно раньше)?
Программа получает на вход три натуральных числа: $$$a$$$, $$$b$$$ ($$$1 \leqslant a \lt b \leqslant 100$$$) и $$$n$$$ ($$$1 \leqslant n \leqslant 10^{5}$$$) — грузоподъемности Шурика и Феди и количество коробок в вагоне, записанных в отдельных строках. В следующих $$$n$$$ строках записано по одному натуральному числу $$$x_i$$$ ($$$1 \leqslant x_i \leqslant a + b$$$) — вес очередной коробки.
Выведите одно натуральное число — ответ на вопрос задачи.
Решения, правильно работающее в случае, когда $$$1 \leqslant x_i \leqslant a$$$, получат не менее 20 баллов.
Решения, правильно работающее в случае, когда $$$1 \leqslant x_i \leqslant b$$$, получат не менее 40 баллов.
25 60 8 60 20 70 10 30 50 40 80
6
В примере дано: Шурик за один раз может перенести коробку весом не превышающим 25, а Федя — 60. Им необходимо переместить 8 коробок.
Первой ходкой Федя и Шурик вдвоём перенесут одну коробку весом 80, второй — 70.
Третьей ходкой Федя перенесет коробку весом 60, а Шурик — 20.
Четвёртой ходкой Федя перенесет коробку весом 50, а Шурик — 10.
Пятой ходкой Федя перенесет коробку весом 40, а Шурик будет просто идти рядом.
Последней ходкой Федя перенесет коробку весом 30. Всего 6 ходок, и можно показать, что быстрее они не управятся.
Коварный Джафар разделил Аладдина и Жасмин, заманив их в разные концы длинного коридора и заперев между ними $$$n$$$ дверей. Теперь, чтобы вновь увидеться, влюблённым необходимо открыть все эти двери по очереди.
Каждая из дверей является золотой или серебряной и открывается одним из двух ключей из соответствующего материала, причём может быть открыта этим ключом с любой стороны. Используя магию джинна, Аладдин может сделать так, чтобы у него и Жасмин появилось по одному ключу разного типа. Это значит, что если у Аладдина появится золотой ключ, то у Жасмин — серебряный, а если у Аладдина будет серебряный ключ, то у Жасмин — золотой.
Помимо этого, Аладдин может попросить джинна изменить материал любой из дверей (с золотого на серебряный или наоборот). Но каждую такую операцию джинн будет выполнять ровно одну минуту.
После того, как джинн закончит изменять двери, Аладдин и Жасмин начнут открывать их, двигаясь навстречу друг другу. Будем считать, что открытие дверей и перемещение между ними происходит мгновенно. Через какое наименьшее время они смогут наконец встретиться?
Первая строка входных данных содержит целое число $$$n$$$ ($$$1 \leqslant n \leqslant 10^5$$$) — количество дверей. Следующие $$$n$$$ строк содержат по одной цифре $$$1$$$ или $$$2$$$. Эти цифры определяют порядок следования дверей в коридоре. Единица значит, что соответствующая дверь золотая, а двойка — что серебряная.
Выведите одно число — наименьшее количество минут, через которое будут открыты все двери.
Решения, правильно работающие для случаев, в которых количество золотых дверей не превосходит трёх, а количество дверей не больше 10, получат не менее 12 баллов.
Решения, правильно работающие для случаев, в которых общее количество дверей не превосходит 100, получат не менее 32 баллов.
Решения, правильно работающие для случаев, в которых общее количество дверей не превосходит 1000, получат не менее 56 баллов.
8 1 2 2 1 2 1 1 1
2
4 2 1 1 1
0
9 1 1 1 1 2 1 1 1 1
1
В первом примере нужно выдать тому, кто находится у первой двери серебряный ключ, а тому, кто у последней — золотой. Далее нужно изменить тип первой и пятой двери, тогда последовательность дверей станет такой: 2, 2, 2, 1, 1, 1, 1, 1.. После этого ключами можно будет открыть все двери. Можно показать, что быстрее, чем за две операции, справится не выйдет.
Карл Гаусс известен тем, что в юные годы сумел быстро решить задачку своего учителя, которую тот предложил ученикам, чтобы занять их на продолжительное время: найти сумму всех натуральных чисел от 1 до 100.
Говорят, что сразу после этого Карл решил и вторую хитрую задачу, так и не дав своему преподавателю насладиться тишиной на уроке.
Дано натуральное число $$$n$$$. Из него вычитают число, равное длине числа $$$n$$$. Из результата опять вычитают число, равное его длине и так далее. Сколько потребуется операций, чтобы получилось число 0?
Попробуйте и вы справиться с этой задачей.
Программа получает на вход одно натуральное число $$$n$$$ ($$$1 \leqslant n \leqslant 10^{16}$$$).
Обратите внимание, что при заданных ограничениях для хранения ответа необходимо использовать $$$64$$$-битный тип данных, например long long в C++, int64 в Free Pascal, long в Java.
Выведите одно натуральное число — ответ на вопрос задачи.
Решения, верно работающие при $$$1 \leqslant n \leqslant 99$$$, получат не менее 20 баллов.
Решения, верно работающие при $$$1 \leqslant n \leqslant 10^{5}$$$, получат не менее 60 баллов.
13
11
В примере дано $$$n = 13$$$. Это двузначное число, поэтому после первой операции результат будет равен $$$13 - 2 = 11$$$.
Число 11 тоже двузначное. После второй операции результат будет равен $$$11 - 2 = 9$$$.
Число 9 однозначное. Будем вычитать из чисел по 1, после ещё девяти операций получим ноль.
Всего 11 операций.