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

Формальное исполнение алгоритма, заданного на естественном языке или для конкретного исполнителя с заданным набором команд#27036

Цепочки цифр (строки) создаются по следующему правилу:

Первая строка состоит из двух цифр «1».

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

Эта цифра вставляется в начало, в конец и между всеми цифрами предыдущей строки.

Вот первые 4 строки, созданные по этому правилу:

(1) 11

(2) 21212

(3) 32313231323

(4) 43424341434243414342434

Таким образом, было построено еще 5 строк и в результате получена строка, содержащая цифры от 1 до 9 и состоящая из 767 цифр.

Напишите через пробел сначала цифру, стоящую на a позиции от начала, а затем на b позиции от начала. a и b считываются с клавиатуры (записаны в одной строке через пробел, номер позиции от начала отсчитывается с 1).

Задача на реализацию Задачи на моделирование

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

Обход по графу. Построение дерева решений#27035

Разработан шифр, при использовании которого каждой цифре ставится в

соответствие определенная буквенная последовательность как приведено в таблице.

1	2	3	4	5	6	7
AB	CB	CBA	ABC	BC	BBC	CCB

С клавиатуры дана буквенная последовательность, содержащая символы только из шифра.

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

Ввод	Вывод
ABCCBABBCCBABC	6

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

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

Рекурсивный DFS#27034

Дана матрица N (1 <= N <= 100) на M (1 <= M <= 100). В матрице имеются ‘.’ – пустые клетки и ‘#’ – клетки, которые нельзя посетить. Ходить можно только вверх, вниз, влево и вправо. Дано q запросов: номер строки и номер столбца, если эта клетка – ‘#’, то она станет ‘.’, иначе – ‘#’. Для каждого из q запросов определить, достижима ли из клетки (S_x; S_y) клетка (t_x; t_y). Вывести на каждой строчке “Yes”, если достижима, и “No” - иначе.
Гарантируется, что клетка (S_x; S_y) и клетка (t_x; t_y)не являются ‘#’ клеткой в каждом запросе.

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

На первой строчке вводятся числа S_x (1 <= S_x <= 100), S_y (1 <= S_y <= 100), t_x (1 <= t_x <= 100), t_y (1 <= t_y <= 100), N (1 <= N <= 100), M(1 <= M <= 100) и q (1 <= q <= 100). На следующих N строках дается матрица, где ‘.’ – пустая клетка и ‘#’ – клетка, которую нельзя посетить. На следующих q строках дан номер строки и номер столбца, которые надо изменить.

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

Вывести на каждый из q запросов “Yes”, если из клетки (S_x; S_y) в клетку (t_x; t_y) можно попасть, “No” – иначе.

Пояснение
В тестовом примере после первого запроса матрица будет такой:

..#

##.

###

Из точки (1; 1) в (2; 3) нет прохода, следовательно, выводим “No”.

После второго запроса матрица будет такой:

..#

#..

###

Из точки (1; 1) в (2; 3)есть проход, следовательно, выводим “Yes”. Выделен путь, по которому мы сможем идти.

Обход в глубину

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

Алгоритмизация и программирование#27032

Дана исходная последовательность цифр: 1234
Задан алгоритм преобразования последовательности, на каждом шаге которого выполняются следующие операции:
1. В конец последовательности, имеющейся перед выполнением шага, дописывается ее копия, но развернутая зеркально (цифры записываются в обратном порядке).
2. В конце получившейся последовательности удаляется количество цифр, равное номеру шага выполнения алгоритма.

Ниже приведены результаты выполнения первых двух шагов алгоритма:
1: 1234432
2: 123443223443

Определите, какие цифры будут на A-ой, B-ой и C-той позиции от начала последовательности, которая получилась после выполнения 8-ого шага алгоритма. В ответе укажите через пробел три цифры: сначала цифру, которая стоит на А-ой позиции, затем цифру, которая стоит на В-ой позиции и затем цифру, которая стоит на С-той позиции. A, B и C задаются с клавиатуры.

Задача на реализацию Задачи на моделирование Строки

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

27031#27031

Сколько существует таких натуральных чисел в диапозоне от a до b, что их запись в шестнадцатеричной системе счисления будет иметь ровно две значащих цифры, а в восьмеричной системе счисления – ровно три значащих цифры?

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

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

Матвей и замок#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средняяВойти и решать

Обратная перестановка#27019

По данной перестановке π требуется найти π^-1.

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

В первой строке входных данных содержится число 0 < N <= 20000 – количество элементов в перестановке π. Во второй строке записана сама перестановка π.

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

Выведите π^-1

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

Разбор:
Вводим N и заводим массив от 1-го до N. Теперь начинаем считывать данную перестановку - хранить ее не обязательно, поэтому разумно будет вводить каждый элемент в одну и ту же переменную. Вводя i-й элемент кладем его порядковый номер (i) в ячейку массива с номером, равному этому числу, т.е. для каждого элемента данной перестановки сохраняем его место в этой перестановке. Теперь выводим полученный массив.

Алгоритмы обработки Перестановки

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

Алгоритм#27016

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

В первой строке ввода содержатся два целых числа A и B (1 ≤ A ≤ B ≤ 10⁹).

Вывести одно целое число – значение K после завершения работы алгоритма.

Ввод	Вывод
10 100	2

Задачи на моделирование Цикл for

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

Алгоритм#27013

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

В первой строке ввода содержится два целых числа, разделенных пробелом - S (0 ≤ S ≤ 20000 ≤ S ≤ 2000) и P (0 ≤ P ≤ 10000000 ≤ P ≤ 1000000).

Вывести два целых числа I и J через пробел.

Ввод	Вывод
22 120	10 12

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

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

Школьные наборы#27000

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

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

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

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

Вывести искомое количество наборов.

Ввод	Вывод
2	3

Комбинаторика

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

Пароль#26999

Антон вводит пароль. Артур подглядывает за Антоном и записывает последовательность клавиш, которые тот нажимает. Иногда Артур не разбирает клавишу и пишет вместо неё символ «*». Артур знает, что пароль Антона является сочетанием (без пробелов) его часто произносимых слов.

Каждое слово может присутствовать в пароле любое количество раз, в том числе 0. Артур решил восстановить пароль Антона. Какое минимальное количество вариантов ему потребуется перебрать?

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

В первой строке находятся два числа N и K (1 <= N <=1000,1 <=K <= 10). Во второй строке находится строка из N символов - последовательность, которую записал Артур. Последовательность может содержать строчные буквы латинского алфавита и знак «*».

Далее идут K строк, которые обозначают часто произносимые слова Антона. Каждое слово состоит не более чем из 10 строчных латинских букв. Других символов в словах нет.

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

Если количество вариантов не более 10⁹, выведите это количество. Иначе выведите единственную строку «MNOGO».

Ввод	Вывод
12 3 r*mm** mama mila ramu	4
10 8 ********** a b c d e f g h	MNOGO

Динамическое программирование: один параметр Строки

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

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

Разбиения на сумму нечетных#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средняяВойти и решать

Дипломы#25961

Когда Петя учился в школе, он часто участвовал в олимпиадах по информатике, математике и физике. Так как он был достаточно способным мальчиком и усердно учился, то на многих из этих олимпиад он получал дипломы. К окончанию школы у него накопилось n дипломов, причём, как оказалось, все они имели одинаковые размеры: w — в ширину и h — в высоту. Сейчас Петя учится в одном из лучших российских университетов и живёт в общежитии со своими одногруппниками. Он решил украсить свою комнату, повесив на одну из стен свои дипломы за школьные олимпиады. Так как к бетонной стене прикрепить дипломы достаточно трудно, то он решил купить специальную доску из пробкового дерева, чтобы прикрепить её к стене, а к ней — дипломы. Для того чтобы эта конструкция выглядела более красиво, Петя хочет, чтобы доска была квадратной и занимала как можно меньше места на стене. Каждый диплом должен быть размещён строго в прямоугольнике размером w на h. Дипломы запрещается поворачивать на 90 градусов. Прямоугольники, соответствующие различным дипломам, не должны иметь общих внутренних точек. Требуется написать программу, которая вычислит минимальный размер стороны доски, которая потребуется Пете для размещения всех своих дипломов.

Входные данные: на вход подаются три целых числа: w, h, n (\(1<=w,\ h,\ n <= 10^9\) ).

Выходные данные: необходимо вывести ответ на поставленную задачу.

Примеры

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

Бинарный поиск по ответу

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

Левый и правый двоичный поиск#25960

Дано два списка чисел, числа в первом списке упорядочены по неубыванию. Для каждого числа из второго списка определите номер первого и последнего появления этого числа в первом списке.

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

В первой строке входных данных записано два числа N и M (\(1<=N,\ M <=20000\)). Во второй строке записано N упорядоченных по неубыванию целых чисел — элементы первого списка. В третьей строке записаны M целых неотрицательных чисел - элементы второго списка.
Все числа в списках - целые 32-битные знаковые.

Формат входных данных
Программа должна вывести M строчек. Для каждого числа из второго списка нужно вывести номер его первого и последнего вхождения в первый список. Нумерация начинается с единицы. Если число не входит в первый список, нужно вывести одно число 0.

Бинарный поиск в массиве

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

Дело в шляпах#25919

Как-то раз в город Шляп заехал известный парикмахер. До его приезда парикмахеры были явно не очень, так как все жители города предпочитали ходить в шляпах. Но наконец-то настало время снять шляпы!

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

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

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

Местного шляпника теперь интересует, каким жителям ему больше не нужно будет делать шляпы, так как они будут ходить с новыми стильными стрижками?

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

В первой строке содержится число N (1 <= N <= 10⁵) количество людей, которые придут к парикмахеру.

Каждая из следующих N строк обозначает пришедшего к парикмахеру жителя и содержит по три числа: фасон шляпы (все фасоны местного шляпника пронумерованы от 1 до 10⁹), момент времени прихода s (1 <= s <= 10⁹), и время на стрижку t (1 <= t <= 10⁹). Строки упорядочены по времени прихода жителей. Гарантируется, что все приходят в разное время. Так как парикмахер очень крут, гарантируется, что он успеет постричь всех жителей до момента времени 2 · 10⁹, даже если бы из очереди никто не уходил.

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

В единственной строке выведите через пробел номера людей в очереди в порядке возрастания, которых парикмахер всё-таки пострижёт. Люди нумеруются в порядке прихода в очередь, начиная с 1.

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

Задачи на моделирование Очередь Разбор случаев

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

Слажал - отжался#25917

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

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

В первой строке число содержится число N (2 <= N <= 1000) количество детей в классе. В

следующей строке записана исходная расстановка школьников: N чисел через пробел, i-е число

обозначает рост i-го школьника r_i (1 <= r_i <= 10⁹) в нанометрах.

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

Одно число суммарное количество отжиманий. Гарантируется, что школьники суммарно отожмутся не более 2 · 10⁹ раз.

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

Замечание

В примере школьники с ростом 1 и 2 поменяются местами и каждый отожмјтся по разу, затем школьники 1 и 3 (каждый отжимается 2 раза, суммарно плюс 4 отжимания), и последними школьники 2 и 3 (плюс 2 отжимания).

Использование сортировки реализация

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

Очень Важный Объект#25916

Антон сторож на очень важном объекте. Как и положено всем важным объектам, он обнесён забором. Правда, время не пощадило этот забор, и в нём есть дыры, через которые на объект могут попадать нарушители.

Известно, что изначально забор состоял из n столбов и n соединяющих их секций. Забор ограничивал территорию, являющуюся выпуклым многоугольником. Однако, со временем, некоторые секции забора развалились и теперь через эти дыры можно почти беспрепятственно пройти внутрь: Антону сложно следить за всеми дырами в заборе. Известно, что в заборе нет двух отсутствующих секций подряд.

Поняв, что, если на объект будет попадать слишком много нарушителей, Антон решил взять инициативу в свои руки и заделать некоторые дыры. Для этого он попросил у начальства моток колючей проволоки. Полученный им моток из l метров колючей проволоки нужно будет потом вернуть в целости, поэтому Антону запрещено его резать. Антон может закрепить один из концов мотка с проволокой в любом месте на границе объекта.

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

Формат входных данных
В первой строке входного файла содержится три целых числа n (3 <= n <= 10⁵) количество столбов в заборе, l (0 <= l <= 10¹⁸) длина выданного Антону мотка проволоки и k (0 <= k <=n/2) количество дыр в заборе.

Во второй строке по возрастанию заданы k чисел a_i (1 < a_i <= n). Числу ai соответствует отсутствие секции забора между столбами a_i и a_i+1 mod n. Гарантируется, что из двух соседних секций хотя бы одна не отсутствует.

В следующих n строках находится по два целых числа x_i и y_i (|xi| <= 10¹⁸, |y_i| <= 10¹⁸) координаты i-го столба забора. Многоугольник может быть задан в порядке обхода как по, так и против часовой стрелки.

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

Выведите единственное число минимальную суммарную длину дыр в заборе после установки колючей проволоки. Ответ будет считаться правильным, если если он отличается от правильного не более, чем на p · 10^?6

, где p периметр многоугольника.

Примеры

Ввод	Вывод
6 4 3 1 3 5 0 0 3 0 4 1 3 2 0 2 -1 1	2.82842712474619

геометрия Задачи на моделирование реализация

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