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

Сборка компьютера#31928

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

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

Первая строка ввода содержит одно целое число – количество типов компонентов T (1 ≤ T ≤ 5). Вторая строка ввода содержит одно целое число – количество компонентов в магазине N (1 ≤ N ≤ 1000). Далее следует N строк, содержащих по три целых числа, разделенных пробелами – стоимость i-го компонента C_i (1 ≤ C_i ≤ 3000), его рейтинг R_i (1 ≤ R_i ≤ 3000) и его тип t_i (1 ≤ t_i ≤ T). Далее следует строка, содержащая одно целое число – бюджет на покупку компьютера B (1 ≤ B ≤ 3000).

Вывести в первой строке одно целое число – максимальный суммарный рейтинг использованных компонент. Во второй строке вывести T целых чисел – i-е число означает номер компонента типа i, выбранного для сборки. Если существует несколько вариантов с максимальным суммарным рейтингом, то из них вывести вариант с минимальной стоимостью, а среди таких вариантов можно вывести любой. Если не существует варианта сборки компьютера в рамках указанного бюджета, то вывести в первой строке одно число –1

Ввод	Вывод
2 5 10 6 1 5 7 1 6 10 2 1 5 1 11 11 2 16	18 2 5

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

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

Подпоследовательность#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средняяВойти и решать

Классификация снежинок#31926

Стелла изучает снежинки, измеряя длину их шести лучей, и собрала уже много данных. Теперь Стелла собирается определить, сколько различных видов снежинок ей удалось обнаружить. Она считает снежинки одинаковыми, если снежинки можно совместить после поворота и/или переворачивания.

Напишите программу, которая поможет Стелле провести классификацию снежинок.

Первая строка ввода содержит одно целое число N (2 ≤ N ≤ 100000). Далее следует N строк, содержащих по 6 целых чисел a₁ a₂ a₃ a₄ a₅ a₆ от 1 до 10⁹, разделенных пробелами – длины лучей снежинок в порядке обхода по часовой стрелке.

Вывести одно целое число – количество различных снежинок, обнаруженных Стеллой.

Ввод	Вывод
5 1 2 3 4 5 6 3 4 5 6 1 2 3 2 1 4 5 6 6 5 4 3 2 1 2 3 6 5 4 1	2

Примечание
Совпадают снежинки 1 и 2 и 4 после поворота или после переворачивания и снежинки 3 и 5 после переворачивания и поворота.

Быстрая сортировка

✓ 0✗ 1—Войти и решать

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

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

Входные данные
Натуральные числа и не превышают по модулю 10000.

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

Примеры

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

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

✓ 402✗ 990600лёгкаяВойти и решать

Функция#31902

Функция f(n) с натуральными аргументами и значениями определена так:

f(0) = 0

f(1) = 1

f(2n) = f(n)

f(2n + 1) = f(n) + f(n + 1)

Составить программу вычисления f(n) по заданному n.

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

Дано одно число n (1 <= n <= 10¹⁸).

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

Выведите f(n).

Примеры

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

Рекурсия

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

Быстрое возведение в степень#31901

Возводить в степень можно гораздо быстрее, чем за n умножений! Для этого нужно воспользоваться следующими рекуррентными соотношениями:

\(a^n=(a^2)^{n/2}\) при четном n,
\(a^n=a \cdot a^{n-1}\) при нечетном n.

Реализуйте алгоритм быстрого возведения в степень. Если вы все сделаете правильно, то сложность вашего алгоритма будет O(logn) .

Входные данные
Вводится вещественное число a и целое число n.

Выходные данные
Выведите ответ на задачу, с точностью 6 знаков после запятой.

Нельзя использовать стандартное возведение в степень.

Примеры

№	Входные данные	Выходные данные
1	2 7	128
2	1.00001 100000	2.71827

Быстрое возведение в степень

✓ 371✗ 1 140600лёгкаяВойти и решать

Перебор строк №4#31900

В алфавите языке племени «тумба-юмба» четыре буквы: «K», «L», «M» и «N». Нужно вывести на экран все возможные слова, состоящие из n букв, в которых есть по крайней мере две одинаковые буквы, не обязательно стоящие рядом. Программа не должна строить другие слова, не соответствующие условию.

Ввод	Вывод
2	KK LL MM NN

Рекурсия

✓ 59✗ 94600лёгкаяВойти и решать

Перебор строк №3#31899

В алфавите языке племени «тумба-юмба» четыре буквы: «K», «L», «M» и «N». Нужно вывести на экран все возможные слова, состоящие из K букв (K<10), в которых есть по крайней мере две одинаковые буквы, стоящие рядом. Подсчитайте количество таких слов. Программа не должна строить другие слова, не соответствующие условию.

Автор задачи: К.Ю. Поляков

Рекурсия

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

Перебор строк №2#31898

В алфавите языке племени «Тумба-Юмба» четыре буквы: «K», «L», «M» и «N». Нужно вывести на экран все возможные слова, состоящие из n букв (n > 1), в которых вторая буква «K». Подсчитайте количество таких слов.

Примеры

№	Входные данные	Выходные данные
1	2	KK LK MK NK 4

Рекурсия

✓ 627✗ 1 150600лёгкаяВойти и решать

Единицы числа#31890

Кролик Клевер вместе с друзьями стали изучать математику. Первое что они узнали - это то, что все числа состоят из цифр. Напишите программу, которая поможет Кролику Клеверу определить цифру, обозначающую единицы в данном числе.
Напомним, что единицы - это последняя цифра числа.

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

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

Примеры

№	Входные данные	Выходные данные
1	2007	7
2	90	0

Целые числа

✓ 14 424✗ 12 288100лёгкаяВойти и решать

Целочисленное деление и остаток#31885

Напишите программу, которая по заданным двум числам a и b, выводит на экран результат целочисленного деления и остаток, в заданном формате (смотри примеры).

Входные данные
На вход программы подается два числа: a и b.

Выходные данные
Необходимо вывести две строки:
- в первой строке - арифметическое выражение и результат целочисленного деления a на b;
- во второй строке - арифметическое выражение вычисления остатка от деления a на b.
Формат вывода смотри в примере.

Примеры

№	Входные данные	Выходные данные
1	15 6	15/6=2 15%6=3

Целые числа

✓ 3 127✗ 16 778200лёгкаяВойти и решать

Яблоки#31883

У Даши есть n друзей, у каждого a_i яблок. Все друзья образуют непересекающиеся компании. В любой момент времени две компании могут объединиться. Даша тщательно запомнила все действия друзей. Теперь ей интересно узнать, сколько яблок было в каждой новообразовавшейся компании. Изначально все друзья тусят отдельно, т.е. нет компании, где больше одного человека. У Даши нет яблок и она не принимает участия в объединениях.

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

В первой строке - целые числа n и k ( 2 <= n <= 300000, 0 <= k <= n - 1 ) - количество друзей Даши и количество событий. Во второй строке n чисел - ai (0 <= ai <= 10^9) - количество яблок у i-того друга Даши. В следующих k строках по два числа u, v ( 1 <= u, v <= n). Событие (u, v) означает, что компания с u-тым другом Даши присоединилась к компании с v-тым другом.

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

На каждый из k запросов выведите количество яблок в новой компании.

Ввод	Вывод
3 2 1 2 3 1 2 1 3	3 6
2 1 999999999 0 1 2	999999999

(с) Ибрахим Ахмад, 2018

Система непересекающихся множеств

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

Возведение a в степень b по модулю c#31881

Зная a, b, c (целые неотрицательные числа, не превосходят \(2\cdot10^9\)). Вычислите a в степени b по модулю c (\(a^b mod \ c\)).

Входные данные
На вход подаются три целых неотрицательных числа, разделенных одним пробелом.

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

Примеры

№	Входные данные	Выходные данные
1	2 10 1000	24

Быстрое возведение в степень

✓ 348✗ 843600лёгкаяВойти и решать

Покраска забора#31880

Однажды, в наказание за шалости и обман, тетя Полли заставила Тома красить забор длиной L ярдов. Все вы прекрасно помните, что Том продавал (за различные ништячки) свою работу другим мальчишкам, которые хотели побелить забор.
К тому моменту, когда у Тома закончилась известка, забор успели покрасить N мальчишек. И так как за мальчишками Том не особо следил, то каждый красил ту часть забора, которая ему больше нравилась.
Каждый i-й мальчишка начинал красить забор с вертикальной дощечки с координатой Left_i и красил до дощечки с координатой Right_i(длину дощечки считать равной 1).
Определите длину забора, которую необходимо будет докрасить Тому самостоятельно.

Входные данные
В первой строке находится число L - длина забора тети Полли. Во второй строке находится число N, в следующих N строках - пары Left_i и Right_i. Все числа - целые
Ограничения:
\(0 <= L <= 2 \cdot 10^9\);
\(-10^9 <= Left_i <= Right_i <= 10^9\);
\(1 <= N <= 15 000\).

Выходные данные
Вывести одно число - длину забора, которую необходимо докрасить Тому.

Примеры

№	Входные данные	Выходные данные
1	20 1 10 20	10
2	10 1 10 10	10
3	100 2 10 30 20 40	70

Быстрая сортировка

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

Анти-QuickSort#31879

Дано число N (1<=N<=1000), а затем N натуральных чисел из диапазона от 1 до 100.
Вывести перестановку элементов массива, на которой быстрая сортировка выполнит максимальное число сравнений, при условии, что "опорным" будет элемент посередине.

Входные данные: в первой строке задаётся число N
Во второй строке идут N чисел - элементы массива
Выходные данные: выведите требуемую перестановку элементов исходного массива

Примеры

№	Входные данные	Выходные данные
1	5 3 10 1 20 7	3 20 7 1 10

Быстрая сортировка

✓ 60✗ 130600лёгкаяВойти и решать

Сложить две дроби#31872

Даны две рациональные дроби: \(a \over b\) и \(c \over d\). Сложите их и результат представьте в виде несократимой дроби \(m \over n\).

Входные данные
Программа получает на вход 4 натуральных числа a, b, c, d, не превосходящих 100.

Выходные данные
Программа должна вывести 2 натуральных числа m и n такие, что \({m \over n} = {a \over b}+ {c \over d}\) и дробь \(m \over n\) – несократима.

Примеры

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

НОД и алгоритм Евклида

✓ 1 118✗ 1 731400лёгкаяВойти и решать

Применение Малой Теоремы Ферма#31866

Дано число a и простое число p. Найти такое минимальное число x, что \((a * x) \% p = 1\).

Входные данные
На вход подаются два натуральное числа a, p (\(a,\ p <= 10^{18} \)).

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

Примеры

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

Малая теорема Ферма

✓ 263✗ 1 128600лёгкаяВойти и решать

Сумма элементов последовательности#31862

На вход программы поступает поток данных — последовательность целых чисел, которая заканчивается нулём (ноль не входит в последовательность). Требуется найти сумму элементов этой последовательности.

Входные данные
На вход программе подаются числа, по одному числу в строке.

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

Примеры

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

Цикл while

✓ 6 664✗ 6 562200лёгкаяВойти и решать

Сумма функции Эйлера#31850

Посчитать сумму функций Эйлера вида: \(\phi(1) + \phi(p) + \phi(p^2) + ... + \phi(p^\alpha)\), где \(p\) - простое число, \(\alpha\)- натуральное число.

Входные данные
В одной строке через пробел подаются два числа \(p\) и \(\alpha\) (\(p <=11, \alpha <=60 \)).

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

Пример

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

Функция Эйлера

✓ 199✗ 389400лёгкаяВойти и решать

Ханойские башни#31845

Головоломка “Ханойские башни” состоит из трех стержней, пронумерованных числами 1, 2, 3. На стержень 1 надета пирамидка из n дисков различного диаметра в порядке возрастания диаметра. Диски можно перекладывать с одного стержня на другой по одному, при этом диск нельзя класть на диск меньшего диаметра. Необходимо переложить всю пирамидку со стержня 1 на стержень 3 за минимальное число перекладываний.

Напишите программу, которая решает головоломку; для данного числа дисков n печатает последовательность перекладываний в формате a b c, где a — номер перекладываемого диска, b — номер стержня с которого снимается данный диск, c — номер стержня на который надевается данный диск.

Например, строка 1 2 3 означает перемещение диска номер 1 со стержня 2 на стержень 3. В одной строке печатается одна команда. Диски пронумерованы числами от 1 до n в порядке возрастания диаметров.

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

Вводится натуральное число n ( 0 < n < 11).

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

Программа должна вывести минимальный (по количеству произведенных операций) способ перекладывания пирамидки из данного числа дисков.

Примеры

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

Рекурсия

✓ 301✗ 276600лёгкаяВойти и решать