Системы счисления(36 задач)
"Длинная" арифметика(58 задач)
Простые числа и разложение на множители(45 задач)
Остатки(21 задач)
Быстрое возведение в степень(3 задач)
Быстрое преобразование Фурье(3 задач)
В настольном теннисе в результате каждой подачи разыгрывается одно очко. Подача переходит от игрока к игроку каждые 5 подач, т.е. первые пять раз подает первый игрок, затем 5 раз — второй, затем снова первый и т.д.
Партия играется до тех пор, пока кто-нибудь из игроков не наберет 21 очко. Тот, кто набрал 21 очко, признается победителем, и игра заканчивается.
Вася и Петя играли в игру, и забыли, кто должен подавать в данный момент. Однако они помнят, что первую подачу делал Вася, и счет в настоящий момент a:b (a очков у Васи и b очков у Пети). Напишите программу, которая по данным a и b будет определять, чья подача или устанавливать, что игра закончена.
Вводятся два числа a и b. Числа соответствуют реальному счету, т.е. оба числа целые, от 0 до 21 и не равны 21 одновременно.
Выведите одно из четырех сообщений:
· Vasya serves — если сейчас должен подавать Вася
· Petya serves — если сейчас должен подавать Петя
· Vasya wins — если игра завершена и выиграл Вася
· Petya wins — если игра завершена и выиграл Петя
4 1
Petya serves
15 0
Petya serves
21 12
Vasya wins
Вася, решая задачи демо-версии ЕГЭ, дошел до задачи B5, которая звучит так.
«У исполнителя Калькулятор две команды:
· прибавь 3
· умножь на 4
Выполняя первую из них, Калькулятор прибавляет к числу на экране 3, а выполняя вторую, умножает его на 4.»
Далее в задаче требовалось получить из числа 3 число 57 не более, чем за 6 команд. Однако Вася заинтересовался, как можно для произвольных чисел \(a\) и \(b\) построить программу наименьшей длины получения числа \(b\) из числа \(a\).
Напишите программу, которая по заданным числам \(a\) и \(b\) вычислит наименьшее количество команд Калькулятора, которое нужно, чтобы получить из \(a\) число \(b\).
Вводятся два натуральных числа, не превышающих 1000 — \(a\) и \(b\).
Выведите наименьшее число команд, которое нужно, чтобы получить из \(a\) число \(b\). Если число \(b\) получить нельзя, выведите –1 (минус 1).
3 57
5
43 57
-1
10 10
0
Из множества всех натуральных чисел от \(1\) до \(N\) требуется выделить такое подмножество, чтобы в нем не было бы никаких двух чисел, отличающихся ровно в два раза (то есть если некоторое число \(X\) входит в это подмножество, то число \(2X\) заведомо в него не входит).
Напишите программу, которая по введенному числу N определяет, какое наибольшее количество чисел от \(1\) до \(N\) может быть включено в такое подмножество.
Например, для \(N=8\) ответ \(5\), подмножество может быть таким: \(1, 3, 4, 5, 7\).
Вводится одно натуральное число \(N\) (\(1\) ≤ \(N\) ≤ \(10^9\)).
Выведите искомое максимальное количество чисел от \(1\) до \(N\), которые могут быть включены в подмножество так, чтобы в этом подмножестве не оказалось бы чисел, отличающихся ровно в два раза.
8
5
50
33
Вася увлекается изобретением новых последовательностей и их исследованием. В этот раз он выписал на доске последовательность:
1 2 3 2 3 4 3 4 5 4 5 6 5 6 7...После этого Вася задался вопросом, на каком месте в ней впервые встретится число \(k\)?
Напишите программу, которая ответит на его вопрос.
Вводится натуральное число \(k\) (\(1 ≤ k ≤ 100\)).
Выведите одно число – искомую позицию, на которой первый раз встретилось число \(k\). Члены последовательности нумеруются с единицы.
1
1
2
2
4
6
Помимо составления последовательностей, летом Вася очень любил смотреть в окно. Напротив его дома расположился офис некоторой строительной фирмы. В течение всего месяца Вася наблюдал за его служащими. Про каждый из 31 дня месяца он знает, сколько сотрудников пришло на работу. Ему также известно, что каждый из служащих берет ровно по 4 выходных в месяц.
Теперь он ломает голову над загадкой – сколько всего сотрудников работает в этом офисе. Напишите программу, которая ответит Васе на этот вопрос.
Вводится 31 целое неотрицательное число. Эти числа описывают количество работников, пришедших в офис в соответствующие дни месяца. Гарантируется, что входные данные корректны.
Выведите единственное число – общее количество работников офиса. Гарантируется, что ответ не превышает 100.
10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 0 0 0 0
10