Информатика

4 314 задачвместе с подтемами
Число у задачи — рейтинг сложности, слово рядом — насколько она трудна по сравнению с другими задачами такого же типа. Шкалы задач с ответом и задач с кодом между собой не сравниваются. Рядом — счётчики попыток: ✓ успешные, ✗ неуспешные.
РейтингЛюбойдо 800800–11991200–15991600+Без рейтинга
СначалаПодходящиеНовыеПопулярныеПростыеСложные
ПТИЦЫ#27173
Всеволод Юрьевич устроился работать охранником на склад. Работа монотонная, и от скуки Всеволод Юрьевич считает ворон и других птиц, пролетающих мимо будки охраны. За годы работы он обнаружил следующую закономерность. Вороны летают поодиночке, начиная с 8:00 утра с периодичностью P1 минут, а после 8:00 вечера летать перестают. Утки пролетают стайками по N штук, начиная с 10:00 утра, с периодичностью P2 минут и перестают летать после 5:00 вечера. Голуби летают поодиночке с 7:00 утра до 8:00 вечера с периодичностью P3 минут. Три раза в день Всеволоду Юрьевичу приходится отвлечься от своего занятия ровно на полтора часа, чтобы принять на склад товар. Приемка начинается ровно в 11:00, 15:00 и 17:00. Сколько птиц (M) Всеволод Юрьевич насчитает за смену, если смена начинается в 6:00 утра и заканчивается в 6:00 утра на следующий день?

Во всех временных интервалах левый конец входит в него, а правый - нет. Например, одна из приемок начинается в 11:00 и Всеволод Юрьевич не считает птиц пролетающих в моменты с 11:00 до 12:29 включительно, а птиц, пролетающих в 12:30 - считает.

Формат входных данных
В строке указываются 4 целых положительных числа не превышающих 10000 каждое: P1, P2, N, P3, разделенные пробелом.
Формат выходных данных
В единственной строке указывается целое число M – количество птиц, которых Всеволод Юрьевич насчитает за смену при указанных условиях входа.
 
Ввод Вывод
P1 P2 N P3 M
23 57 5 7 123
Разбор случаев
✓ 2✗ 51 000средняяВойти и решать
Intelligence in Perpendicularia#27118
There are only two directions in Perpendicularia: vertical and horizontal. Perpendicularia government are going to build a new secret service facility. They have some proposed facility plans and want to calculate total secured perimeter for each of them.
The total secured perimeter is calculated as the total length of the facility walls invisible for the perpendicularly-looking outside observer. The figure below shows one of the proposed plans and corresponding secured perimeter. 
Write a program that calculates the total secured perimeter for the given plan of the secret service facility.

Input
The plan of the secret service facility is specified as a polygon. The first line of the input contains one integer n — the number of vertices of the polygon (4 ≤ n ≤ 1000). Each of the following n lines contains two integers xi and yi – the coordinates of the i-th vertex (−106 ≤ xi , yi ≤ 106 ). Vertices are listed in the consecutive order. All polygon vertices are distinct and none of them lie at the polygon’s edge. All polygon edges are either vertical (xi = xi+1) or horizontal (yi = yi+1) and none of them intersect each other.

Output
Output a single integer — the total secured perimeter of the secret service facility.
 
Input Output
10
1 1
6 1
6 4
3 4
3 3
5 3
5 2
2 2
2 3
1 3		 6
Вывод формулы
✓ 5✗ 01 000средняяВойти и решать
Автомобильные номера#27092

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

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

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

Напомним, что автомобильные номера в России состоят из трех букв и трех цифр, упорядоченных следующим образом: буква, три цифры, затем две буквы. Фрагмент номера, который идентифицирует регион, в котором зарегистрирован автомобиль, мы будем игнорировать.

В номере могут использоваться следующие буквы: «A», «B», «C», «E», «H», «K», «M», «O», «P», «T», «X», «Y» (эти буквы имеют схожие по написанию аналоги как в русском, так и в латинском алфавите). В этой задаче во входных данных будут использоваться буквы латинского алфавита.

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

На вход программы поступает  одна строка, которая представляет собой корректный автомобильный номер.

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

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

В последующих k строках выведите все такие номера в произвольном порядке.

Ввод Вывод 
X772KX
 
9
X277XK
X277KX
X727XK
X727KX
X772XK
X772KX
K277XX
K727XX
K772XX
 

Перестановки
✓ 8✗ 12800средняяВойти и решать
Гладкие числа#27087

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

Входные данные
На вход программы поступает номер N (\(1 <= N <= 2147483647\)).

Выходные данные
Выведите соответствующее номеру N гладкое число.



Примеры
№ Входные данные Выходные данные
1 3 3
2 11 12
Перестановки
✓ 19✗ 711 000средняяВойти и решать
КОЛОНИЗАЦИЯ МАРСА#27072
Ученым удалось отправить на планету Марс мини-фабрику, которая может за одни сутки произвести мини-фабрику или дрона для сбора воды (мини-фабрика или дрон для сбора воды могут начать работу только со следующих суток). Дрон собирает одну единицу воды за одни сутки. Определите, за какое минимальное количество суток удастся собрать не менее N единиц воды.

Формат входных данных
Задается одно число N ( 1<= N <= 109 ) – необходимое количество воды.

Формат выходных данных
Одно целое число M – минимально необходимое количество суток.
 
Ввод Вывод
2 3


Замечание
Одна из правильных последовательностей действий выглядит так:
? В первые сутки мини-фабрика производит дрона для сбора воды;
? За вторые сутки мини-фабрика производит еще одного дрона, а первый дрон собирает одну единицу воды;
? За третьи сутки мини-фабрика может произвести еще одного дрона или мини- фабрику, при этом первый дрон собирает еще одну единицу воды (итого он собрал 2 единицы воды), а второй дрон собирает единицу воды. Таким образом, накоплено 3 единицы воды за трое суток.

Другая последовательность действий состоит в том, чтобы за первые сутки построить еще одну мини-фабрику, а за вторые сутки произвести двух дронов, которые на третьи сутки соберут 2 единицы воды.
Задача на реализацию
✓ 11✗ 151900средняяВойти и решать
Время полета#27040
При  полутах  на  самолетах  в  качестве  времени  вылета  и  прилета  используется  местное  время аэропортов вылета и прилета.
Часовые пояса характеризуются разницей во времени с меридианом, на котором расположена Гринвичская обсерватория. Для каждого часового пояса вводится отклонение от UTC (Всемирного координированного времени).
Например, Москва расположена в часовом поясе UTC+3, а Новосибирск в часовом поясе UTC+7.  Если  вылететь  из  Москвы  рейсом  в  11:15  и  временем  полјта  ровно  в  4  часа,  то  прилет будет в Новосибирск будет в 19:15 (4 часа полёта и 4 часа разницы во времени).
Например, Москва расположена в часовом поясе UTC+3, а Новосибирск  в часовом поясе UTC+7. Если вылететь из Москвы рейсом в 11:15 и временем полјта ровно в 4 часа, то прилјт будет в Новосибирск будет в 19:15 (4 часа полёта и 4 часа разницы во времени).
Часовые пояса могут изменяться от UTC-11 (Американское Самоа) до UTC+14 (острова Лайн, Кирибати).
По заданному времени вылета и времени полёта, а также по часовым поясам аэропортов вылета и прилёта, вам необходимо определить местное время прилёта и количество дней, прошедших в
пути.

Формат входных данных
В первой строке записаны целые числа HD , MD (0 <= HD <=  23, 0 <= MD <= 59)  время вылета.
Во второй строке записаны целые числа HF , MF (0 <= HF <= 109, 0 <= MF <= 59)  время полёта.
В третьей строке записаны целые числа D, A (-11 6 D, A <= 14)  часовые пояса аэропорта вылета и прилёта.
 
Формат выходных данных
Выведите три числа HA;MA; Days  время прилёта в часах и минутах, а также разницу в датах между датой вылета и датой прилёта.

Система оценки
Решения, верно работающие для рейсов, дата вылета и прилјта которых не отличаются, будут набирать не менее половины баллов.
Ввод Вывод
11 15
4 0
3 7
 19 15 0
12 0
1 0
-10 13
 12 0 1
 
Замечание
Первый тест соответствуте разобранному в условии примеру с Москвой и Новосибирском.
Второй тест соответствует, например, часовому перелету из Американского Самоа на Самоа.
Самолет вылетает в 12:00, летит в течение часа и приземляется в 12:00 местного времени. Т.к. он пересёк линию перемены даты, то на Самоа уже наступил следующий день.
В реальности существуют часовые пояса, которые отличаются от UTC на нецелое число часов, однако в задаче они не рассматриваются.
Вывод формулы
✓ 28✗ 114800средняяВойти и решать
Обход по графу. Построение дерева решений#27035
Разработан шифр, при использовании которого каждой цифре ставится в
соответствие определенная буквенная последовательность как приведено в таблице.
1 2 3 4 5 6 7
AB CB CBA ABC BC BBC CCB
С клавиатуры дана буквенная последовательность, содержащая символы только из шифра.
 
Сколько существует вариантов расшифровки приведенной буквенной последовательности, если каждая цифра может встречаться в результате расшифровки любое количество раз. В ответе не нужно приводить все варианты получившихся последовательностей цифр.
Напишите целое число, соответствующее количеству вариантов расшифровки.
Ввод Вывод
ABCCBABBCCBABC 6

Динамическое программирование: один параметр
✓ 15✗ 8900средняяВойти и решать
Алгоритмизация и программирование#27033
Дан фрагмент программы: 

 

Операции MOD, mod и функция ост_дел вычисляют остаток от деления первого аргумента на второй. Операции \, div и функция цел_дел осуществляют целочисленное деление. Какое минимальное значение целочисленной переменной X должно было быть перед началом выполнения этого фрагмента, если после его выполнения получилось значение R=A?, где А - вводится с клавиатуры. 
В ответе укажите целое число. 
Задача на реализацию
✓ 16✗ 34900средняяВойти и решать
Матвей и замок#27025
Всемирно известному взломщику Матвею поступил заказ на инновационный сейф, выпущенный компанией "British Scientists, Inc". Этот сейф почти целиком сделан из адамантита, не поддающемуся ни одной из дрелей Матвея. Поэтому его единственным уязвимым местом является патентованный кодовый замок. К счастью, Матвей похитил чертежи сейфа ещё во время его разработки, поэтому точно знает принцип работы замка.

Код вводится с помощью клавиатуры с числами от нуля до девяти. Как только введено необходимое количество цифр, код проверяется по следующему алгоритму. К нулю прибавляется первая введённая цифра, затем отнимается вторая, потом эта разность умножается на третью, и наконец, результат нацело делится на четвёртую. Потом этот алгоритм повторяется для следующих четырёх цифр, и так, пока они не кончатся. Если количество цифр не делится на четыре, то лишние действия просто отбрасываются.  Если при выполнении алгоритма встречается деление на ноль, то он тут же аварийно завершает работу, блокируя сейф. Если в результате получилось число X - секретная константа, которую Матвей тоже знает - замок открывается. 
Матвей внимательно изучил клавиатуру и понял, что по отпечаткам пальцев на кнопкам он может определить, какие цифры используются в коде, и сколько раз. Тут ему стало интересно - а сколько всего комбинаций, подходящих под эти данные, открывают замок? Комбинации считаются различными, если в них отличается порядок следования цифр. 
Но увы, с математикой у Матвея не очень, поэтому, без труда выполнив заказ, он задал этот вопрос всемирно известному хакеру - Вам. Помогите Матвею. 
 
Входные данные
В первой строке на вход подаются два числа N (1 <= n <= 8) и Х (1 <= X <= 10^9) - количество цифр в коде и секретная константа. Во второй находится n цифр, разделённых пробелами. Разумеется, цифры могут повторяться. 
 
Выходные данные
Вывести необходимо единственное число - ответ на вопрос Матвея.
 
Ввод Вывод
4 0
2 2 3 6
 4
2 1
1 1		 0

 
Перестановки
✓ 6✗ 28900средняяВойти и решать
Вывод паролей#27024
Однажды, на уроке информатики Леше Васильеву дали придумать специальную задачу с перестановками для Дамира.  Леше очень понравилась эта затея, поэтому он взял ноутбук с полки, включил и заметил, что Антон Витальевич сменил пароли. Леше известно, что пароль содержит в себе все символы лексикографически максимальной подстроки в строке S, однако у него не так много времени на перебор, задачи необходимо сдать через 40 минут!
Помогите Леше и напишите программу, которая способна вывести все варианты паролей для строки S.
Пароли выводятся в алфавитном порядке.
Подстрокой называется некоторая непустая подпоследовательность подряд идущих символов строки. Лексикографически максимальная подстрока это подстрока, стоящая на последнем месте в отсортированном по алфавиту списке всех подстрок исходной строки.
 

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

Программа получает на вход строку S. Длина S не более 15 символов. Строка записана строчными английскими буквами.
 

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

Выведите в алфавитном порядке все варианты паролей для строки S. Каждый пароль выводится в отдельной строке.
Перестановки
✓ 34✗ 47800средняяВойти и решать
Алгоритм#27013
Реализуйте на одном из языков программирования алгоритм, представленный на схеме.
В первой строке ввода содержится два целых числа, разделенных пробелом - S (0 ≤ S ≤ 20000 ≤ S ≤ 2000) и P (0 ≤ P ≤ 10000000 ≤ P ≤ 1000000).
Вывести два целых числа I и J через пробел.
 
Ввод Вывод
22 120 10 12
Простые задачи на перебор
✓ 34✗ 70800средняяВойти и решать
Сумма ряда - 7#27009
Дан числовой ряд и малая величина eps=0.001. С точностью eps (то есть, если сумма при очередном добавлении слагаемого будет отличаться на величину меньшую чем 0.001 от предыдущей, то это слагаемое считается последним) найти сумму ряда, общий член которого задан формулой (n>0):
\(a_n = {2^n \cdot n! \over{n^n}}\)
 
Выведите на экран сумму такого ряда.
Циклы
✓ 23✗ 186800средняяВойти и решать
Сумма ряда - 4#27006
Дан числовой ряд и малая величина eps=0.001. С точностью eps (то есть, если сумма при очередном добавлении слагаемого будет отличаться на величину меньшую чем 0.001 от предыдущей, то это слагаемое считается последним) найти сумму ряда, общий член которого задан формулой (n>0):
\(a_n = {1 \over{(3 \cdot n - 2)\cdot(3\cdot n+1)}}\)
 
Выведите на экран сумму такого ряда.
Циклы
✓ 25✗ 85800средняяВойти и решать
Сумма ряда - 1#27003
Дан числовой ряд и малая величина eps=0.001. С точностью eps (то есть, если сумма при очередном добавлении слагаемого будет отличаться на величину меньшую чем 0.001 от предыдущей, то это слагаемое считается последним) найти сумму ряда, общий член которого задан формулой (n>0):
\(a_n = {(-1)^{n-1} \over{n^n}}\)
 
Выведите на экран сумму такого ряда.
Циклы
✓ 33✗ 154800средняяВойти и решать
Школьные наборы#27000
В школьный набор из N предметов могут входить ручки, карандаши, ластики и тетрадки. Предметы одного типа друг от друга не отличаются. Сколько способов составить школьный набор так, чтобы ручек было больше, чем карандашей?
Порядок предметов в наборе не важен, т.е. наборы “ручка, ластик, ластик” и “ластик, ручка, ластик” считаются одинаковыми.

Формат входных данных
В первой строке входного файла записано натуральное число N> (1<=N<<=100).

Формат выходных данных
Вывести искомое количество наборов.
 
Ввод Вывод
2 3
 
 
Комбинаторика
✓ 21✗ 53800средняяВойти и решать
Палиндромы#26998
Вам дана строка символов, состоящая из заглавных букв латинского алфавита. Подсчитайте сколько различных палиндромов можно составить, меняя местами буквы этой строки. Палиндромом называется строка, которая одинаково читается как справа налево, так и слева направо. Например, “ABCBA” - палиндром, а “ABCDA” - нет.

Формат входных данных
В первой строке входного файла содержится непустая строка, состоящая из заглавных букв латинского алфавита. Её длина не превосходит 35 символов.

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

Ввод Вывод
ABCBA 2
 
Комбинаторика
✓ 5✗ 511 000средняяВойти и решать
Одуванчики#26996
У Ани есть поле размером N×M клеток. На этом поле Аня разводит одуванчики. Аня заметила, что если в некоторой клетке поля растёт одуванчик, то на следующий день в четырёх клетках рядом с ним (севернее, восточнее, южнее и западнее) вырастает по одуванчику. Однако за пределами поля одуванчики не вырастают.

Сейчас на поле растёт несколько одуванчиков (не меньше одного). Определите, через сколько дней всё поле будет в одуванчиках. Известно, что Аня хорошо заботится о выросших одуванчиках, поэтому ни один из них не погибнет.
 
Формат входных данных
На первой строке находятся числа N и M (1<=N, M <= 100)  размеры поля. Далее идут N строк, каждая из которых по M элементов. Эти строки обозначают поле. Символ «.» в строке означает, что данная клетка поля пуста, а символ «*» что в клетке находится одуванчик. Других символов в строках быть не может.

Формат выходных данных
Выведите единственное число - количество дней, которое должно пройти, чтобы всё поле оказалось засеянным одуванчиками.
Частичные решения, работающие при случаях, когда N = 1 или M = 1, получат не менее 30 баллов.

Ввод Вывод
3 3
...
.*.
...
 2
4 3
...
...
...
*..
 5

 

Обход в ширину
✓ 13✗ 54800средняяВойти и решать
Массив#26995
У Пети есть массив отсортированных в порядке неубывания натуральных чисел. Известно, что чисел N. Петя  пытливый мальчик, поэтому хочет найти в массиве три числа x, y и z (x <= y <= z), такие, что сумма (x - y)2 + (x - z)2 + (z - y)2 была бы максимальна. Помогите ему в этом.

Формат входных данных
В первой строке входного файла находится число N> (3<=N <= 100000). На следующей строке находятся N натуральных чисел, каждое из которых не превышает 10000.

Формат выходных данных
Нужно вывести три числа x, y и z в порядке возрастания. Если вариантов такой тройки несколько, вывести любой.
 
Ввод Вывод
4
1 2 3 5		 1 2 5
Одномерные массивы
✓ 12✗ 65800средняяВойти и решать
Разбиения на сумму нечетных#26985

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

Например, число 6 можно разложить на слагаемые следующими способами: 1+1+1+1+1+1, 1+1+1+3, 3+3, 1+5.

 

Формат ввода

На вход подается число n (1 ≤ n ≤ 1000).

 

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

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

 

Пример

Ввод Вывод 
6

4

Примечания

Разбиение, состоящее из одного слагаемого, также считается разбиением.


Динамическое программирование: один параметр
✓ 2✗ 371 100средняяВойти и решать
2048#26981

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

Напомним правила игры 2048. На поле 4 × 4 разбросаны числа, являющиеся степенями двойки от 2 до 1024, некоторые клетки могут быть пустыми. Каждый ход игрок может сдвинуть все плитки игрового поля в одну сторону. Если при сдвиге две плитки одного номинала «налетают» одна на другую, то они слипаются в одну, номинал которой равен сумме соединившихся плиток. За каждое соединение игровые очки увеличиваются на номинал получившейся плитки. Плитка, получившаяся при слипании двух других, не может больше участвовать в слипании.


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

Программа получает на вход четыре строки, в каждой из которых записано четыре числа. Числа являются степенями двойки от 2 до 1024. В некоторых клетках записано число 0, означающий, что данная клетка пуста.
 

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

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

 
Примеры
№ Входные данные Выходные данные
1 
2 0 0 0
2 0 0 0
2 0 0 0
0 0 0 0
 
4
2 
2 0 0 0
2 0 0 0
2 0 0 0
2 0 0 0

8
3 
2 2 4 0
0 0 0 0
0 0 0 0
0 0 0 0

4
4 
2 2 4 0
0 2 2 2
0 2 4 0
2 4 4 0

16

 

Примечания

Внимательно прочитайте этот раздел для лучшего понимания правил игры.

Наилучший ответ на первый тест достигается движением вниз. 
0 0 0 0
0 0 0 0
2 0 0 0
4 0 0 0

Наилучший ответ на второй тест достигается движением вниз. 
0 0 0 0
0 0 0 0
4 0 0 0
4 0 0 0

Наилучший ответ на третий тест достигается движением влево. 
4 4 0 0
0 0 0 0
0 0 0 0
0 0 0 0

Наилучший ответ на четвертый тест достигается движением вниз. 
0 0 0 0
0 2 4 0
0 4 2 0
4 4 8 2

Двумерные массивы
✓ 5✗ 161 000средняяВойти и решать
Поделиться
Класснуть