Информатика

2 621 задачавместе с подтемами
Число у задачи — рейтинг сложности, слово рядом — насколько она трудна по сравнению с другими задачами такого же типа. Шкалы задач с ответом и задач с кодом между собой не сравниваются. Рядом — счётчики попыток: ✓ успешные, ✗ неуспешные.
РейтингЛюбойдо 800800–11991200–15991600+Без рейтинга
СначалаПодходящиеНовыеПопулярныеПростыеСложные
Расширенный алгоритм Евклида#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 <= 1018).
 
Выходные данные
Выведите 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


(c) К.Ю. Поляков
Рекурсия
✓ 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

(c)  К.Ю. Поляков
Рекурсия
✓ 627✗ 1 150600лёгкаяВойти и решать
Единицы числа#31890
Кролик Клевер вместе с друзьями стали изучать математику. Первое что они узнали - это то, что все числа состоят из цифр. Напишите программу, которая поможет Кролику Клеверу определить цифру, обозначающую единицы в данном числе. 
Напомним, что единицы - это последняя цифра числа.
 
Входные данные
Вводится натуральное число.
 
Выходные данные
Выведите ответ на задачу.

 

Примеры
№ Входные данные Выходные данные
1 2007 7
2 90 0
Целые числа
✓ 14 414✗ 12 288100лёгкаяВойти и решать
Целочисленное деление и остаток#31885
Напишите программу, которая по заданным двум числам a и b, выводит на экран результат целочисленного деления и остаток, в заданном формате (смотри примеры).

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

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

 

Примеры
№ Входные данные Выходные данные
1 15 6 15/6=2
15%6=3
Целые числа
✓ 3 127✗ 16 778200лёгкаяВойти и решать
Возведение a в степень b по модулю c#31881
Зная a, b, c (целые неотрицательные числа, не превосходят \(2\cdot10^9\) ). Вычислите a в степени b по модулю c  (\(a^b mod \ c\)).

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

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

 

Примеры
№ Входные данные Выходные данные
1 2 10 1000 24
Быстрое возведение в степень
✓ 348✗ 843600лёгкаяВойти и решать
Анти-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 117✗ 1 718400лёгкаяВойти и решать
Применение Малой Теоремы Ферма#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 662✗ 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лёгкаяВойти и решать
Двоичные последовательности#31843
Вводится число N (1<=N<=9). Сгенерируйте в лексикографическом порядке все последовательности длины N, состоящие из чисел 2, 4, 5, в которых количество двоек не больше двух.
 
В "лексикографическом порядке" обозначает, что если на первых X местах две последовательности совпадают, а на месте X+1 - различаются, то раньше должна идти та из них, в которой число на месте X+1 меньше.
 
 
Рекурсия
✓ 354✗ 694700средняяВойти и решать
Звездочки#31842
Дана строка, содержащая только английские буквы (большие и маленькие). Добавить символ ‘*’ (звездочка) между буквами (перед первой буквой и после последней символ ‘*’ добавлять не нужно).
 
Входные данные
Вводится строка ненулевой длины. Известно также, что длина строки не превышает 1000 знаков.
Выходные данные
Вывести строку, которая получится после добавления символов '*'.

Примеры
№ Входные данные Выходные данные
1 LItBeoFLcSGBOFQxMHoIuDDWcqcVgkcRoAeocXO L*I*t*B*e*o*F*L*c*S*G*B*O*F*Q*x*M*H*o*I*u*D*D*W*c*q*c*V*g*k*c*R*o*A*e*o*c*X*O
Рекурсия
✓ 632✗ 445400лёгкаяВойти и решать
Количество цифр#31841
Дана строка, содержащая цифры и английские буквы (большие и маленькие). Найти и вывести количество цифр.
 
Входные данные
Вводится строка ненулевой длины. Известно также, что длина строки не превышает 1000 знаков.
 
Выходные данные
Выведите количество цифр, которые присутствуют в строке.

Примеры
№ Входные данные Выходные данные
1 74kz31n8pn26f2iv10c7u8x356gl73jlka67i929z08i5mnn35h0n 28
Рекурсия
✓ 553✗ 402400лёгкаяВойти и решать
Наибольшая строка#31840
Дана строка, содержащая только десятичные цифры. Напишите программу с использованием рекурсии для нахождения наибольшей цифры.
При решении этой задачи запрещено использовать циклы и слово max.
 
Входные данные
Вводится строка ненулевой длины. Известно также, что длина строки не превышает 1000 знаков и строка содержит только десятичные цифры.
 
Выходные данные
Выведите максимальную цифру, которая встречается во введенной строке.
 
Примеры
№ Входные данные Выходные данные
1 11111111 1
Рекурсия
✓ 646✗ 751400лёгкаяВойти и решать
Вычисление факториала#31839
Составить программу с рекурсивной функцией для расчета факториала.

Входные данные
В первой строке вводится натуральное число N (  N<=12 ).

Выходные данные
Выведите факториал числа.
Примеры
№ Входные данные Выходные данные
1 1 1
2 2 2
Рекурсия
✓ 737✗ 550200лёгкаяВойти и решать
Поделиться
Класснуть