Информатика

15 724 задачивместе с подтемами
Число у задачи — рейтинг сложности, слово рядом — насколько она трудна по сравнению с другими задачами такого же типа. Шкалы задач с ответом и задач с кодом между собой не сравниваются. Рядом — счётчики попыток: ✓ успешные, ✗ неуспешные.
РейтингЛюбойдо 800800–11991200–15991600+Без рейтинга
СначалаПодходящиеНовыеПопулярныеПростыеСложные
Кратность 8#21829
Для делимости числа на 8, необходимо, чтобы число из трех последних цифр делилось на 8. 
Напишите функцию, работающую по данному алгоритму, для проверки делимости числа n, вводимого с клавиатуры, на 8. 

Используя данную функцию, напишите программу, которая запрашивает у пользователя число n (0<=n<=100000) и выводит на экран фразу multiple of  8,  если число кратно 8 и фразу not multiple of 8, если число не кратно 8

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

Пример

Ввод

Вывод
3 not multiple of 8
8 multiple of 8
Вычисление по заданной формулеЗадачи на процедуры и функции
✓ 154✗ 259500лёгкаяВойти и решать
Кратность 5#21828
Для делимости числа на 5, необходимо, чтобы последняя цифра числа было 0 или 5. 
Напишите функцию, работающую по данному алгоритму, для проверки делимости числа n, вводимого с клавиатуры, на 5. 

Используя данную функцию, напишите программу, которая запрашивает у пользователя число n (0<=n<=100000) и выводит на экран фразу multiple of  5,  если число кратно 5 и фразу not multiple of 5, если число не кратно 5

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

Пример

Ввод

Вывод
3 not multiple of 5
5 multiple of 5
 

Задачи на процедуры и функцииУсловный оператор
✓ 197✗ 246500лёгкаяВойти и решать
Кратность 4#21827
Для делимости числа на 4, необходимо, чтобы число из последних двух цифр делилось на 4. 
Напишите функцию, работающую по данному алгоритму, для проверки делимости числа n, вводимого с клавиатуры, на 4. 

Используя данную функцию, напишите программу, которая запрашивает у пользователя число n (0<=n<=100000) и выводит на экран фразу multiple of  4,  если число кратно 4 и фразу not multiple of 4, если число не кратно четырем

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

Пример

Ввод

Вывод
3 not multiple of 4
4 multiple of 4

Задачи на процедуры и функцииУсловный оператор
✓ 188✗ 335500лёгкаяВойти и решать
Кратность 3#21826
Для делимости числа на 3, требуется, чтобы сумма цифр числа делилась на 3. 
Напишите функцию, работающую по данному алгоритму, для проверки делимости числа n, вводимого с клавиатуры, на 3. 

Используя данную функцию, напишите программу, которая запрашивает у пользователя число n (0<=n<=100000) и выводит на экран фразу multiple of 3,  если число кратно 3 и фразу not multiple of 3, если число не кратно трем

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

Пример

Ввод

Вывод
3 multiple of 3
4 not multiple of 3

Задачи на процедуры и функцииУсловный оператор
✓ 189✗ 226400лёгкаяВойти и решать
Преобразование последовательности#21820
Учительница математики очень не любит Колю и всегда заставляет его отвечать у доски самые
сложные задачи.
Вот и сегодня она написала на доске последовательность из n целых неотрицательных чисел
чисел a1, a2, . . . , an и вызвала Колю к доске. За одно действие учительница разрешает Коле
стереть любое число и на его место записать число на единицу больше. Учительница требует от
Коли за минимальное число действий добиться того, чтобы где-нибудь в этой последовательности
встречались подряд в возрастающем порядке числа от 1 до h.
Помогите Коле понять, за какое минимальное число действий ему удастся добиться того, что для
некоторого i будет выполнено ai = 1, ai+1 = 2, . . . , ai+h−1 = h, или выясните, что это невозможно и
учительница опять безнаказанно издевается над бедным Колей.

Формат входных данных
Первая строка входного файла содержит два натуральных числа: n и h (1 ≤ h ≤ n ≤ 200 000).
Вторая строка содержит n чисел ai — исходные значения элементов выписанной последовательности
(0 ≤ ai ≤ n).
Формат выходных данных
В единственной строке выходного файла выведите минимальное количество действий, за которое
Коля сможет выполнить задание, или −1 в случае, если выполнить его невозможно.

Примеры
Ввод
4 3
1 1 0 2
Вывод
3

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

В первом примере Коле надо дважды увеличить на 1 третье число и один раз — четвертое. Тогда
последовательность примет вид 1, 1, 2, 3, для i = 2 выполнено искомое условие.
Во втором примере получить в последовательности подряд 1 и 2 невозможно.

Задача на реализациюЗадачи на моделирование
✓ 6✗ 231 000средняяВойти и решать
Регистрация на олимпиаду#21818
Петя и Вася проводят олимпиаду по программированию. На нее пришло так много участников,
что для того, чтобы их всех зарегистрировать, Пете и Васе пришлось работать вдвоем.
Для того, чтобы зарегистрироваться, каждый участник называет свои имя, фамилию и отчество,
а Петя и Вася заносят эту информацию в общую электронную таблицу. Так как участников много,
а времени на организацию так мало, Петя и Вася не успели договориться о формате записи данных
участника в таблицу и им пришлось импровизировать. Петя решил писать для каждого участника
сначала его фамилию, затем имя, а затем — отчество, а Вася — сначала имя, затем отчество, а
затем — фамилию.
По окончании регистрации стало понятно, что для подведения итогов олимпиады использовать
данную таблицу невозможно: участнику будет неудобно себя искать. Было решено привести таблицу
к следующему виду:
• для всех участников сначала написана фамилия, затем имя, а затем — отчество;
• участники в таблице упорядочены лексикографически по фамилии.
Петя и Вася заметили, что фамилии у всех участников различны, а вот каждое имя встречается
хотя бы два раза. При этом никакое имя не является ни фамилией, ни отчеством никакого из
участников, аналогично никакие фамилия и отчество не совпадают.
Пользуясь этой информацией, помогите им привести таблицу к желаемому виду.
Формат входных данных
В первой строке задано число n (2 ≤ n ≤ 1000) — общее число записей в электронной таблице.
Далее, в n строках записано по три слова s1,i, s2,i, s3,i. Каждое из слов содержит от 1 до 20 латинских
букв, первая буква является заглавной, а все остальные — строчными. Каждая строка соответствует
одной из записей, сделанных Петей или Васей. Слова разделены одним пробелом.
Формат выходных данных
Выведите n строк — электронную таблицу, в которой для каждого участника идет сначала
фамилия, потом имя, потом отчество, причем все записи отсортированы лексикографически.
Лексикографический порядок соответствует порядку в словарях: слова сначала сравниваются
по первой букве, затем по второй и т.д. Если очередная буква в одном из слов идет раньше в
алфавите, то это слово лексикографически меньше другого. Если же расхождение так и не найдено,
то есть одно из слов является префиксом другого, то считается, что слово, являющееся префиксом,
лексикографически меньше.

Пример
Ввод
4
Ivanov Ivan Ivanovich
Ivan Borisovich Petrov
Sergey Ivanovich Sidorov
Pavlov Sergey Borisovich

Вывод
 
Ivanov Ivan Ivanovich
Pavlov Sergey Borisovich
Petrov Ivan Borisovich
Sidorov Sergey Ivanovich
Использование сортировкиСтроки
✓ 10✗ 241 100средняяВойти и решать
Мерлин#21817
Однажды, вернувшись в свою башню, Мерлин обнаружил, что Моргана наложила проклятие на
все его сосуды с эликсиром мудрости.
Мерлин знает, как снять проклятие, но соответствующее заклинание требует, чтобы во всех
сосудах, к которым оно применяется, было равное количество эликсира.
Чтобы добиться этого, Мерлин решил действовать следующим образом. Он выбирает несколько
сосудов и переливает весь эликсир из выбранных сосудов в оставшиеся. Он может распределить
переливаемый эликсир между оставшимися сосудами произвольным образом. После того, как весь
эликсир из выбранных сосудов перелит, Мерлин разбивает опустошенные сосуды (с них проклятие
уже не снять), выбрасывает осколки и применяет заклинание снятия проклятия к оставшимся
сосудам.
Помогите волшебнику узнать, какое наименьшее количество сосудов ему придется разбить,
чтобы снять проклятие Морганы.
Формат входных данных
В первой строке входного файла находится число n (2 ≤ n ≤ 105) — количество сосудов. Во
второй строке содержатся n чисел a1, a2, . . . , an (1 ≤ ai ≤ 109) — количество литров эликсира
мудрости в каждом сосуде.
Формат выходных данных
Выведите в выходной файл минимальное количество сосудов, которые Мерлину придется
разбить.

Пример
Ввод
3
2 3 2
Вывод
1

Ввод:
4
4 4 4 4
Вывод
0

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

 
В первом примере можно, например, перелить 0.5 литра эликсира из первого сосуда во второй
и 1.5 литра в третий, после чего разбить первый сосуд.
Во втором сосуды исходно содержат равное количество эликсира, можно ничего не переливать.
В третьем примере можно, например, перелить 1 литр эликсира из первого сосуда во второй, по
2 литра из пятого во второй и третий, 1 литр из пятого в четвертый, после чего разбить первый и
пятый сосуды.
Использование сортировкиОтрезкиреализация
✓ 11✗ 191 000средняяВойти и решать
Саруман#21816
Как известно, Саруман Белый - маг очень занятой и каждый день ему приходится работать с огромным количеством древних свитков. Чтобы не запутаться, он дал каждому свитку номер и положил их все на длинную полку. Но последнее время к нему постоянно наведывался Гендальф, чтобы узнать что-нибудь из свитков, что доставляет удовольствие Гендальфу и очень бесит Сарумана. И чтобы не отвечать на огромное количество вопросов Гендальфа где что лежит, он пообещал подарить свой посох тому, кто напишет программу отвечающую на вопросы Гендальфа.
 
Входные данные:
В первой строке задаётся число N(0<=N<=105). На следующих N строках идет описание типа свитка и его номер L (-109<=L<=109). Потом вводится число Q(0<=N<=105) – количество запросов. А затем на еще Q строках вводится тип свитка и его номер (-105<=L<=105).
Типы свитков:
LEG - легендарные
FEW - редкие
STAND – обычные
 
Выходные данные:
На каждый запрос вывести позицию свитка если он есть (Нумерация с 1) и “Fatality error” если такого не имеется. Каждый ответ на новой строке. Так же Гендальфу интересен номер самого большого свитка и самого маленького (Тип свитка на это не влияет). Это необходимо вывести после основных запросов на новой строке по образцу в примере.
 
Пример:
Входные данные:
5
LEG -345
LEG 1
FEW 2452
STAND 4
FEW 334
3
LEG -353
LEG -345
STAND 4
Выходные данные:
Fatality error
1
4
Max 2452 Min -345

Автор: Аксенов Владимир
 
 
Задача на реализациюХеш
✓ 11✗ 10800средняяВойти и решать
Игра#21814
На уроке физкультуры первоклассники Петя и Вася играют в увлекательную игру. Перед ребятами в ряд стоит n столбиков разной высоты. У мальчиков есть m колец, которые они по очереди кидают на столбики, причем если на столбике уже есть кольцо, то кидать кольцо на этот столбик нельзя. Петя кидает первым.
Ребята выяснили, что Петя может закинуть кольцо на столбик только, если высота этого столбика не меньше l1 и не больше r1. На слишком высокий или слишком низкий столбик он закинуть кольцо не может. Зато, если столбик имеет подходящую высоту, бросок гарантированно заканчивается успехом. Аналогично, Вася может закинуть кольцо только на столбики с высотой не меньше l2 и не больше r2 и гарантированно закидывает кольцо на любой такой столбик.
Физрук Андрей Сергеевич обещал поставить пятерку тому из ребят, кто по итогам игры закинет больше колец на столбики. Помогите ребятам выяснить, кто из них выиграет при оптимальной игре.

Формат входных данных
В первой строке входного файла находятся два целых числа n и m — количество столбиков и колец, соответственно (1 ≤ m ≤ n ≤ 105). Следующие две строки содержат числа l1, r1 и l2, r2 — минимальную и максимальную высоту столбиков, на которые могут кидать колечки Петя и Вася, соответственно (1 ≤ l1 ≤ r1 ≤ 109, 1 ≤ l2 ≤ r2 ≤ 109). В последней строке содержится n чисел, описывающих высоту столбиков, высота каждого столбика является целым положительным числом и не превышает 109.
Формат выходных данных
В выходной файл выведите «Petya», если выиграет Петя, «Vasya», если выиграет Вася, или «Draw», если при оптимальной игре оба мальчика закинут на столбики равное число колец.

Задачи на моделированиеРазбор случаев
✓ 14✗ 1581 000средняяВойти и решать
Дюна#21813
Географ Григорий Георгиевич исследует образование песчаных дюн. Он выбрал очень длинную дюну и разбил его на огромное число участков, которые пронумеровал от 1 до 109.
Теория Григория Георгиевича гласит, что изначально высота песка относительно некоторой условной отметки на всех участках была равна нулю. После этого произошло n сильных порывов ветра, которые могли изменить ландшафт.
Порыв ветра номер i имел силу xi и действовал на участки с li-го по ri-й. В результате этого порыва высота участка номер li увеличилась на xi, высота участка номер li + 1 уменьшилась на xi, следующего — снова увеличилась на xi, и так далее до участка номер ri, включительно.
Зная всю информацию о всех n порывах ветра, Григорий Георгиевич хочет узнать установившуюся в итоге высоту некоторых интересующих его m участков. Помогите ему.

Формат входных данных
В первой строке входного файла содержатся два натуральных числа n и m (1 ≤ n,m ≤ 1000) — количество порывов ветра и количество участков, итоговая высота которых интересует Григория Георгиевича.
В каждой из следующих n строк содержится описание очередного порыва ветра — три целых числа li, ri, xi (1 ≤ li ≤ ri ≤ 109; 1 ≤ xi ≤ 1000).
В каждой из следующих m строк содержится целое число qi (1 ≤ qi ≤ 109) — номер участка, для которого требуется узнать его итоговую высоту. Номера участков приведены в возрастающем
порядке.
 
Формат выходных данных
Для каждого из m запросов выведите одно целое число — высоту соответствующего участка.

Пример
Ввод:
2 6
1 6 7
3 7 2
1
2
3
6
7
8
Вывод
7
-7
9
-9
2
0

Задача на реализациюЗадачи на моделирование
✓ 14✗ 39900средняяВойти и решать
Шахматы#21811
Кроме школы и математического кружка, Вася ходит на шахматный кружок. Но играть в шахматы на обычной доске 8 × 8 ему кажется не очень интересным. Недавно он придумал свою версию шахмат, в которой игра происходит на доске, имеющей другую форму. Васина доска состоит из n столбцов, i-й из которых содержит ai клеток. Нижние клетки всех столбцов образуют один  горизонтальный ряд, причем длины столбцов упорядочены слева направо по невозрастанию. На рисунке ниже приведен пример доски, в которой три столбца, содержащих 5, 2 и 1 клетку,  соответственно.

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

Формат входных данных
В первой строке входного файла задано целое число n — количество столбцов доски
(1 ≤ n ≤ 1000). Следущая строка содержит n чисел a1, a2, . . . , an — количество клеток в столбцах
(1 ≤ ai ≤ 1000, a1 ≥ a2 ≥ . . . ≥ an).

Формат выходных данных
В первой строке выведите число k — минимальное число ладей, которое можно расставить на доске так, чтобы каждую клетку доски била хотя бы одна ладья. Следующие k строк должны содержать описание позиций ладей, по одной на каждой строке. Позиция ладьи задается двумя числами: номером столбца, в котором стоит ладья, и номером клетки в столбце. Столбцы нумеруются, начиная с 1, слева направо, клетки в столбцах нумеруются снизу вверх, также начиная с 1.
Если подходящих расстановок несколько, можно вывести любую.

Примеры
Ввод
3
5 2 1

Вывод
2
1 5
2 1

ОтрезкиРазбор случаевреализация
✓ 24✗ 64900средняяВойти и решать
ABCD-код#21810
Вася часто ходит в гости к Пете. Для того, чтобы попасть к Пете во двор, надо ввести код,
состоящий из четырех цифр. Обычно друзья ходили вместе, но в этот раз Вася пришел один, а
Петя ждет его у себя.
Вася не помнит код, но у него есть несколько вариантов. Кроме того, Васе почему-то запомнился
факт, что квадрат числа, составленного из первых двух цифр кода, в сумме с квадратом числа,
состоящего из последних двух цифр кода, имеет при делении на семь остаток один. То есть, если код
представляет собой «ABCD», где «A», «B», «C», «D» — некоторые цифры, тогда AB2+CD2 имеет
остаток 1 при делении на 7. Например, код 2843, является одним из возможных кодов, поскольку
282 + 432 = 2633 = 376 · 7 + 1, а 8243 — нет, поскольку 822 + 432 = 8573 = 1224 · 7 + 5.
У Васи есть несколько вариантов того, каким может быть код. Помогите ему определить, какие
из вариантов могут быть кодом от входа в Петин двор.

Формат входных данных
В первой строке  находится число t (1 ≤ t ≤ 10 000) — число вариантов кода,
которые помнит Вася. В следующих t строках содержится по четыре цифры — варианты кода.
Формат выходных данных
В ответе выведите t строк. В i-й строке выведите «YES», если i-й код может быть кодом
для входа в Петин двор, иначе выведите «NO».
Вычисление по заданной формулеОстатки
✓ 149✗ 143500лёгкаяВойти и решать
MLG pro#21779
Bonkisilver очень хочет стать MLG pro и попасть в FaZe clan. Для этого он каждый день практикуется в стрельбе из снайперской винтовки. В качестве поощрения, за каждый noscope он получает 2 пачки doritos, а за каждый quickscope - одну. Сколько вариантов сделать выстрелы было у Bonkisilver, если в итоге у него была n-1 пачка.
 
Входные данные
На вход подается число n (1 <= n <= 50).
 
Выходные данные
Выведите одно число - количество вариантов сделать выстрелы. 
 
 
Примеры
№ Входные данные Выходные данные
1 3 2
 
Динамическое программированиеДинамическое программирование: один параметр
✓ 113✗ 304700средняяВойти и решать
Алгоритм Евклида#21722
Для быстрого вычисления наибольшего общего делителя двух чисел используют алгоритм Евклида. Он построен на следующем соотношении: НОД(a,b)=НОД(a % b,b). Реализуйте рекурсивный алгоритм Евклида в виде функции gcd(a, b).

Ввод
12 16
Вывод
4
НОД и алгоритм ЕвклидаРекурсия
✓ 71✗ 36500лёгкаяВойти и решать
Сложение без сложения#21721
Напишите рекурсивную функцию с двумя параметрами, возвращающую сумму двух целых неотрицательных чисел. Из всех арифметических операций допускаются только +1 и -1. Также нельзя использовать циклы.
Основная программа должна содержать ввод исходных данных (два целых неотрицательных числа), вызов функции и вывод результата.

Примеры
№ Входные данные Выходные данные
1 8 7 15
Линейные алгоритмыРекурсия
✓ 257✗ 216400лёгкаяВойти и решать
Поделиться
Класснуть