Портал обучения информатике. Подготовка к ЕГЭ, ОГЭ, олимпиадам

Тройной Фибоначчи#38279

Пятиклассник Лёня недавно прочитал статью о числах Фибоначчи.

Числами Фибоначчи называется числовая последовательность F₁ , F₂ , ..., F_n , ... , которая устроена следующим образом: F₁ = 1 , F₂ = 2 , а каждое следующие число вычисляется как сумма двух предыдущих: если i ≥ 3 , то F_i = F_i - 1 + F_i - 2 . Последовательность чисел Фибоначчи, таким образом, начинается с чисел 1, 2, 3, 5, 8, 13, 21, ... .

Сегодня Лёня изучает числа Фибоначчи с номерами от L до R , включительно. Так как Лёня очень любит число 3, ему стало интересно, сколько чисел Фибоначчи среди тех, которые он изучает сегодня, делятся на 3. Например, если L = 3 и R = 7 , то Лёня будет изучать числа F₃ = 3 , F₄ = 5 , F₅ = 8 , F₆ = 13 и F₇ = 21 . Среди них на 3 делятся два числа: F₃ = 3 и F₇ = 21 .

Напишите программу, которая поможет Лёне найти ответ на волнующий его вопрос.

Входные данные
Первая строка входных данных содержит число L , а вторая — число R ( 1 ≤ L ≤ R ≤ 10⁵ ).

Выходные данные
Выведите единственное число — количество чисел Фибоначчи с номерами от L до R , включительно, которые делятся на 3.

№	Входные данные	Выходные данные
1	3 7	2

Остатки

✓ 12✗ 37800средняяВойти и решать

2011#38238

Представьте число 2011 в виду суммы K последовательных простых чисел (то есть простых чисел, между которыми нет других простых чисел). Например, число 31 можно представить в виде суммы трех посдедовательных простых чисел следующим образом: 7 + 11 + 13 = 31.

Входные данные
Вводится одно натуральное число K (от 1 до 2011).

Выходные данные
Выведите слагаемые в порядке возрастания, разделяя их пробелом.

Если разложить в сумму K слагаемых невозможно, выведите NO SOLUTION (заглавными буквами).

Примеры

№	Входные данные	Выходные данные
1	3	661 673 677
2	2	NO SOLUTION

Простые числа и разложение на множители Целые числа

✓ 8✗ 641 100средняяВойти и решать

Игра для Пети и Вани#37559

Некоторые уроки в школе для Вани и Пети очень скучны. На этих уроках Петя и Ваня придумали игру. Сначала мальчики записывают на листке два различных натуральных числа a и b .
Ход игры заключается в следующем: среди записанных чисел выбирают p и q такие, что модуля их разности $| p - q |$ еще нет на листке, и дописывают его.
Проигрывает тот, кто не может сделать ход.
Определите, кто из ребят окажется победителем при правильной игре обоих. Ваня вежливый мальчик, поэтому всегда ходит вторым.

Входные данные: В первой и единственной строке записано два различных натуральных числа 1 <= a , b <= 10^9 , разделенные пробелом - два исходных числа на листке.

Выходные данные: Выведите имя победителя в этой игре (Petya или Vanya)

Примечание: В первом примере Петя первым ходом допишет на листок число |6−2| = 4 . Больше ходов нет, поэтому выигрывает Петя. Во втором примере первым ходом на листок будет дописано число |4−1| = 3 . Затем Ваня может записать |3−1| = 2 , тогда у Пети ходов не останется. Побеждает Ваня.

Примеры

№	Входные данные	Выходные данные
1	6 2	Petya
2	4 1	Vanya

Вывод формулы игры НОД и алгоритм Евклида

✓ 239✗ 947800средняяВойти и решать

Задача для Пети и Вани#37555

Пятиклассники Петя и Ваня изучили на уроках математики следующий алгоритм Евклида:

Пусть a, b — числа, НОД которых надо найти.
Если b = 0, то число a — искомый НОД.
Если b > a, то необходимо поменять местами числа a и b.
Присвоить числу a значение a – b.
Вернуться к шагу 2.

Маша придумала для них задачу на закрепление. Она попросила мальчиков придумать такие числа a, b, c и d, что в процессе реализации алгоритма Евклида для заданной пары чисел (a, b) наступает такой момент, когда перед исполнением шага 2 число a будет равно c, а число b будет равно d.

Напишите для Маши программу, которая проверит, удовлетворяют ли числа a, b, c, d условиям Маши.

Входные данные: Первая строка входных данных содержит количество наборов входных данных K ($1 <= K <= 100$). Далее идут описания этих наборов. Каждое описание состоит из двух строк. Первая из них содержит два целых числа: a, b ($1 <= a,\ b <= 10^{18}$). Вторая строка – два целых числа: c, d ($1 <= c,\ d <= 10^{18}$).
Все числа в строках разделены пробелом.

Выходные данные: Для каждого набора входных данных выведите слово «YES», если в процессе применения алгоритма Евклида к паре чисел (a, b) в какой-то момент получается пара (c, d). В противном случае выведите слово «NO».

Примеры

№	Входные данные	Выходные данные
1	2 20 10 10 10 10 7 2 4	YES NO

Вывод формулы НОД и алгоритм Евклида

✓ 106✗ 1 7501 000средняяВойти и решать

Учитель математики Юрий Петрович#34916

Легендарный учитель математики Юрий Петрович придумал забавную игру с числами. А именно, взяв произвольное целое число, он переводит его в двоичную систему счисления, получая некоторую последовательность из нулей и единиц, начинающуюся с единицы. (Например, десятичное число $19_{10} = 1\cdot2^4+0\cdot2^3+0\cdot2^2+1\cdot2^1+1\cdot2^0 $ в двоичной системе запишется как 10011₂.) Затем учитель начинает сдвигать цифры полученного двоичного числа по циклу (так, что последняя цифра становится первой, а все остальные сдвигаются на одну позицию вправо), выписывая образующиеся при этом последовательности из нулей и единиц в столбик — он подметил, что независимо от выбора исходного числа получающиеся последовательности начинают с некоторого момента повторяться. И, наконец, Юрий Петрович отыскивает максимальное из выписанных чисел и переводит его обратно в десятичную систему счисления, считая это число результатом проделанных манипуляций. Так, для числа 19 список последовательностей будет таким:

...
и результатом игры, следовательно, окажется число $1\cdot2^4+1\cdot2^3+1\cdot2^2+0\cdot2^1+0\cdot2^0 = 28_{10} $

Поскольку придуманная игра с числами все больше занимает воображение учителя, отвлекая тем самым его от работы с ну очень одаренными школьниками, Вас просят написать программу, которая бы помогла Юрию Петровичу получать результат игры без утомительных ручных вычислений.

Решите эту задачу с использованием битовых операций!

Входные данные

Входной файл содержит одно целое число N (0<=N<=32767).

Выходные данные

Ваша программа должна вывести в выходной файл одно целое число, равное результату игры.

Примеры

№	Входные данные	Выходные данные
1	1	1

Битовые операции Двоичная система счисления

✓ 132✗ 276800средняяВойти и решать

Диофантовы уравнения#33656

Даны натуральные числа a, b, c. Если уравнение $ax+by=c$ имеет решения в целых числах, то выберите то решение, в котором число x имеет наименьшее неотрицательное значение и выведите это решение (два числа x и y через один пробел). Если решения не существует, то выведите слово Impossible.

Входные данные
Вводятся три натуральных числа.

Выходные данные
Выведите ответ на задачу.

Примечание
Сложность алгоритма должна быть равна сложности алгоритма Евклида + константа.

Примеры

№	Входные данные	Выходные данные
1	1 2 3	1 1
2	10 6 8	2 -2

Расширенный алгоритм Евклида

✓ 170✗ 1 153800средняяВойти и решать

Последовательность#33303

Последовательность 011212201220200112… строится следующим образом: сначала пишется 0, затем повторяется следующее действие: уже написанную часть приписывают справа с заменой 0 на 1, 1 на 2, 2 на 0, и т.д.

Требуется написать программу, которая по заданному натуральному числу N определяет, какое число стоит на N-ом месте.

Входные данные

Дано натурально число число N (1 ≤ N ≤ 10¹⁸).

Выходные данные

Выведите число, которое стоит на k-ом месте в последовательности.

Ввод	Вывод
1	0
10	2

Арифметические алгоритмы (Теория чисел)Рекурсия Целые числа

✓ 4✗ 301 000средняяВойти и решать

Лесопилка#33135

Недавно на лесопилку, где работает Вася, поступил новый заказ. Для постройки нового дома мэру соседнего города требуется a досок длины x футов и b досок длины y футов.

Поскольку на лесопилке имеется только неограниченный запас досок длины z футов, Васе поручили исполнить заказ клиента, распилив имеющиеся доски на меньшие. Вася хочет закончить работу как можно быстрее, поэтому он хочет выполнить заказ, сделав как можно меньше распилов. При этом количество использованных досок длины z роли не играет, кроме того, часть досок, образовавшихся в результате распила, может не требоваться для заказа и остаться на лесопилке.

Например, если на лесопилке имеются доски длины 80, а клиенту требуется две доски длины 30 и семь досок длины 20, то достаточно сделать семь распилов: одну доску распилить двумя распилами на доски длины 20, 30 и 30, одну тремя распилами на четыре доски длины 20 и одну двумя распилами на доски длины 20, 20 и 40. Доска длины 40 клиенту не нужна, она останется на лесопилке, остальные доски будут отправлены клиенту.

Входные данные

На вход программы поступают числа a, x, b, y и z. Все числа положительны и не превышают 300, x<=z, y<=z, x!=y.

Выходные данные

Выведите минимальное количество распилов, которые требуется сделать для того, чтобы выполнить заказ.

Ввод	Вывод
2 30 7 20 80	7

Динамическое программирование Остатки

✓ 7✗ 43900средняяВойти и решать

Квадраты и кубы#33122

В лаборатории теории чисел одного университета изучают связь между

распределением квадратов и кубов натуральных чисел.

Пусть задано целое неотрицательное число k. Рассмотрим множество натуральных

чисел от a до b, включительно. Будем называть k-плотностью этого множества количество

пар натуральных чисел x и y, таких, что a ≤ x² ≤ b, a ≤ y³ ≤ b, причем |x²– y³| ≤ k.

Например, 2-плотность множества натуральных чисел от 1 до 30 равна 3, так как

подходят следующие пары:

x = 1, y = 1, |x²– y³| = |1 – 1| = 0;

x = 3, y = 2, |x²– y³| = |9 – 8| = 1;

x = 5, y = 3, |x²– y³| = |25 – 27| = 2.

Требуется написать программу, которая по заданным натуральным числам a и b, а

также целому неотрицательному числу k, определяет k-плотность множества натуральных

чисел от a до b, включительно.

Формат входных данных

Входные данные содержат три строки. Первая строка содержит натуральное число a,

вторая строка содержит натуральное число b, третья строка содержит целое неотрицательное

число k (1 ≤ a ≤ b ≤ 10¹⁸, 0 ≤ k ≤ 10¹⁸).

Формат выходных данных

Выходные данные должны содержать одно целое число: искомую k-плотность

множества натуральных чисел от a до b, включительно.

Ввод	Вывод
1 30 2	3

Арифметические алгоритмы (Теория чисел)Вещественные числа Линейный поиск

✓ 6✗ 661 100средняяВойти и решать

Домашнее задание#33080

Маленькому Арсению на кружке по системам счисления задали следующую задачу: перевести число X в системе счисления s1 в систему счисления s2. Недолго думая, он позвал на помощь своего лучшего друга Добрыню, который славился тем, что замечательно умел считать до 10 на пальцах. После нескольких бессонных ночей ребята общими усилиями справились с задачей.

Однако, на следующем занятии Арсению задали похожую задачу, где X, к сожалению, превышало 10. Тогда ребята решили обратиться в Летнюю Компьютерную Школу с просьбой написать универсальную программу, которая решает задачу для любых X, s1 и s2. Ваша цель – выполнить просьбу Арсения и Добрыни.

Входные данные

Во входных данных вашей программе дается 3 числа: исходное число X, основания систем счисления s1 и s2 ($2 <= s1,\ s2 <= 10$). Число X в десятичной системе счисления не превышает $2 \cdot 10^9$.

Выходные данные

В выходных данных должно находиться одно число, равное числу X в системе счисления s2, или -1, если входные данные некорректны.

Примеры

№	Входные данные	Выходные данные
1	101 2 10	5
2	200 2 10	-1

Разные системы счисления

✓ 48✗ 146800средняяВойти и решать

Следующее число#32965

Дано натуральное число N. Необходимо определить следующее за ним число, в двоичном разложении которого столько же единиц, сколько в двоичном разложении числа N.

Входные данные

Входные данные содержит одно натуральное число N ($N <= 2^{30}$).

Выходные данные

Выведите ответ на задачу.

Примеры

№	Входные данные	Выходные данные
1	1	2
2	2	4
3	3	5

Двоичная система счисления

✓ 108✗ 1 012800средняяВойти и решать

Степень числа#32949

Для заданного натурального A найти минимальное натуральное N такое, что N в степени N (N, умноженное на себя N раз) делится на A.

Входные данные
На вход подается единственное число A ($1 <= A <= 10^9$).

Выходные данные
Необходимо вывести единственное число N.

Примеры

№	Входные данные	Выходные данные
1	8	4
2	13	13

Простые числа и разложение на множители

✓ 139✗ 1 086800средняяВойти и решать

Подпоследовательность#31927

Напишите программу, которая в некоторой последовательности целых чисел находит подпоследовательность наименьшей длины, сумма элементов в которой является числом, оканчивающимся на 6 или более нулей (делится без остатка на 1000000).

Первая строка ввода содержит одно целое число N (2 ≤ N ≤ 100000). Вторая строка ввода содержит N целых чисел в диапазоне от 1 до 10⁹, разделенных пробелами.

Вывести два целых числа – количество элементов в подпоследовательности и номер её первого элемента. Если существует несколько вариантов такой подпоследовательности с наименьшей длиной, выведите подпоследовательность с наименьшим номером первого элемента. Если такой подпоследовательности не существует – выведите одно число –1.

Ввод	Вывод
6 1 2 701000 299000 1000 999000	2 3
3 1 2 3	-1

Остатки

✓ 10✗ 671 000средняяВойти и решать

RSA. Зашифровать числовое сообщение#31919

Даный два простых числа p и q. Надо зашифровать сообщение длинной N с помощью алгоритма RSA.

Входные данные
В первой строке вводятся p и q (3<=p,q<10), далее вводится натуральное число, которое надо зашифровать, не превышающее 10⁹.

Ввод	Вывод
3 7 123456789	1 11 12 16 17 6 7 8 18

Быстрое возведение в степень МЦКО-10. RSA

✓ 8✗ 25900средняяВойти и решать

Упрощение номеров#30776

Как, вы не можете запомнить 6 или 7-значный номер телефона, появившийся на секунду на экране телевизора?! С помощью специальной методики, описываемой далее, Вы превратитесь в ходячий телефонный справочник!

Очевидно, что число 402 запомнить легче, чем число 110010010, а число 337377 запомнить легче, чем число 957472. Значит, нужно чтобы запоминаемое число, с одной стороны, содержало как можно меньше цифр, а с другой стороны, желательно, чтобы в числе было как можно больше повторяющихся цифр. В качестве критерия сложности запоминания примем сумму количества цифр в числе и количества различных цифр в числе. Запоминаемое число можно записать в другой системе счисления, возможно, тогда его окажется легче запомнить. Например, число 65535 в шестнадцатеричной системе исчисления выглядит как FFFF.
Напишите программу подбора основания системы счисления для минимизации критерия сложности. Основание системы счисления нужно выбирать в диапазоне от 2 до 36, тогда для представления числа можно использовать цифры 0-9 и английские буквы A-Z.

Входные данные

Первая строка содержит в первой строке целое число n ($1 <= n <= 100$). Далее следует n строк, каждая строка содержит целое число от 1 до 999999999.

Выходные данные

Ответ должен содержать n строк. Для каждого из n заданных чисел строка содержит: основание системы счисления (от 2 до 36), минимизирующее критерий сложности запоминания, и число в выбранной системе исчисления, разделенные одним пробелом. Если несколько оснований дают одинаковое значение критерия, то выбрать наименьшее среди них.

Пример

№	Входные данные	Выходные данные
1	2 2 65535	3 2 16 FFFF

Разные системы счисления

✓ 38✗ 73900средняяВойти и решать

Тройки чисел#30756

Напишите программу, находящую количество троек целых чисел a, c, p таких, что p — простое число, числа удовлетворяют равенству: $$ \sqrt{a} - \sqrt{c} = \sqrt{p}. $$ Каждое из чисел a, c и p лежит в промежутке от N до M (то есть $N<=a<= M,\ N<=c<= M,\ N<=p<= M$).

Входные данные
Вводятся два целых числа N и M ($0<=N<=M<=100000$).

Выходные данные
Выведите искомое количество троек чисел a, c, p.

Примеры

№	Входные данные	Выходные данные
1	1 8	1
2	5 20	1
3	1 7	0

Простые числа и разложение на множители

✓ 123✗ 785900средняяВойти и решать

Битая кодировка#27303

–Т—Л–≤–µ–і–Є—В–µ –і–≤–∞–і—Ж–∞—В—М –њ–µ—А–≤—Л—Е –њ—А–Њ—Б—В—Л—Е —З–Є—Б–µ–ї

Простые числа и разложение на множители реализация

✓ 37✗ 138800средняяВойти и решать

Перестановки#27214

Сколько существует трехразрядных шестнадцатеричных чисел, для которых будут одновременно выполняться следующие три условия:

1. Шестнадцатеричные цифры в записи числа упорядочены по невозрастанию.

2. Если перевести это число в двоичную систему счсиления, то запись будет содержать не менее 5-ти идущих подряд единиц.

3. Любое шестнадцатеричное число, образованное перестановкой цифр этого числа и переведенное в двоичную систему счисления, также будет содержать в двоичной записи не менее 5-ти единиц подряд.

Перебор Системы счисления

✓ 12✗ 321 000средняяВойти и решать

Огромное число#27070

Вася получил длинную последовательность из цифр следующим образом. Он брал подряд натуральные числа, начиная с 1, переводил их в четверичную систему счисления и записывал результаты перевода друг за другом. Вот начало этой последовательности:
123101112132021222330313233100…
Вася остановился только тогда, когда дописал в конец последовательности четверичную запись числа 1023₁₀. Затем он представил, что это одно большое число, записанное в четверичной системе счисления, и перевел его в шестнадцатеричную систему счисления.

Определите, какая шестнадцатеричная цифра стоит в этом числе на a-ой позиции, считая слева направо от начала числа. В ответе укажите эту шестнадцатеричную цифру.

Задача на реализацию Системы счисления

✓ 29✗ 137800средняяВойти и решать

Максимальное число делителей#26984

Напишите программу, которая по заданному числу n находит такое число от 1 до n, включительно, что оно имеет максимальное число положительных целых делителей. Например, если n = 15, то ответом на задачу будет число — 12, так как у него 6 делителей: 1, 2, 3, 4, 6 и 12.

Формат входных данных

Дано одно натуральное число n (1 ≤ n ≤ 100 000).

Формат входных данных

В первой строке выведите число из диапазона от 1 до n, включительно, которое имеет максимальное число делителей. Во второй строке выведите число его делителей. Если в диапазоне от 1 до n существует несколько чисел с максимальным числом делителей, то выведите любое из них.

Простые задачи на перебор Простые числа и разложение на множители

✓ 9✗ 133900средняяВойти и решать