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

27031#27031

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

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

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

S.L.O.T.#27023

Вчера знаменитый певец S.L.O.T. исполнил на концерте свой лучший трек "10 марта" и множество других. Дамир ОЧЕНЬ захотел на этот концерт и уже купил билеты, как вдруг понял, что до концерта всего час, а ему нужно доехать до места проведения концерта (естественно, на трамвае).

Трамвай необходимое расстояние преодолевает за 59 минут. Будем считать, что концерт проводится на трамвайной остановке, то есть Дамир вполне на него успевает, но ему подходит только ему подходят лишь трамваи, номера которых являются перестановками от 1 до n. При этом он только что увидел, как с его остановки уезжает трамвай с номером p. Однако Дамир - великий эстет, и он хочет сесть на трамвай, номер которого равен следующей перестановке после p. Поскольку трамваи подходят к его остановке мнгновенно, на концерт любимого исполнителя он успеет в любом случае.

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

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

В первой строке вводится число n - количество чисел в перестановке в номере трамвая

Во второй строке ЧЕРЕЗ ПРОБЕЛ!! вводится n чисел, которые задают p - номер трамвая, который только что отошёл от остановки Дамира

Третья строка содержит k - количество трамваев, которые скоро подъедут к остановке Дамира (гарантируется, что один из трамваев подходит Дамиру)

Далее идут k строк, которые содержат по n чисел через пробел - номера трамваев

(n <= 7, k <= 5)

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

выведите порядковый номер трамвая, который подходит Дамиру (если таких несколько, выведите наименьший из них, то есть порядковый номер того искомого трамвая, который подъедет к остановке Дамира раньше).

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

Комбинаторика Перестановки

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

Сложные пароли#27022

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

Ввод:
в первой строке вводится n - количество слов и наборов цифр, в следующих n строках вводятся слова / наборы цифр. (n<20, длина строк не превышает 20).

Вывод:
Необходимо вывести все возможные перестановки слов и наборов цифр, если это невозможно, вывести "unreal".

Ввод	Вывод
3 cat 123 215	123cat215 215cat123

(с) Вероника Пеутина

Комбинаторика Простые задачи на перебор реализация

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

"Гробы" из 43-го#27021

На уроке информатике Антон Витальевич задал придумать задачи на перестановки. Ребята в 43 кабинете очень обрадовались этому заданию и решили придумать n гробов для своего класса. Сложность каждой задачи – это число от 1 до n. Ребята хотят узнать насколько, они «загробили» контест, коэффициент «загробленности» (КЗ) считается, как номер перестановки, которую подали на ввод. Ребята радуются, если КЗ будет больше, чем сумма разниц между двумя подряд идущими элементами в данной перестановки по модулю умноженная на количество гробов в контесте.

Вывести “positumque loculum” (гроб), если ребята будут рады своей работе, иначе вывести наименьшую подходящую перестановку (элементы разделять пробелами), номер которой |КЗ – номер текущей| <= k, а если это невозможно, то вывести “easily”.

В первой строке вводится количество гробов в контесте n <= 7 и k, 0 <= k <= n!

Во второй строке вводится сама перестановка.

Ввод	Вывод
7 2518 7 5 2 4 1 6 3	positumque loculum
4 1 3 2 4 1	easily
4 2 3 2 4 1	3 4 2 1

Приятного решения ♥♥
(с) Елизавета Ястреба

Генерация по номеру Комбинаторика

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

Номер перестановки#27020

Вам даны две строки - S и одна из её перестановок - P. Требуется найти номер строки P среди всех перестановок строки S, отсортированных по убыванию в лексикографическом порядке.

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

На вход подаются две строки - S и P (1 =< |S| <= 9). В строках содержатся только строчные буквы латинского алфавита.

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

Выведите одно число - номер перестановки P.

Ввод	Вывод
abcd dcba	1
abc abc	6

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

Комбинаторика Перестановки

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

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

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

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

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

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

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

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

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

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

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

Алгоритм#27018

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

В первой строке ввода содержится одно целое число N (2 ≤ N ≤ 10⁹).

Каждое число, которое выводится в алгоритме, вывести на отдельной строке.

Ввод	Вывод
12	2 2 3

Задачи на моделирование Простые числа и разложение на множители

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

Алгоритм#27016

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

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

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

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

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

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

Алгоритм#27015

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

В первой строке ввода содержатся целое число N (1 ≤ N ≤ 100). Далее следует N строк, содержащих по одному целому числу в диапазоне от −1000 до 1000.

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

Ввод	Вывод
4 2 3 -7 4	5

Алгоритмы обработки Линейные алгоритмы

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

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

Курьер#26986

Курьеру Васе поручили доставить n посылок. Вася начинает работать в первый день и каждый день может доставить ровно одну посылку. Про каждую посылку известен последний день, когда ее можно доставить d_i, и штраф w_i, который придется заплатить, если посылка не будет доставлена в срок.

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

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

Формат ввода

В первой строке дано единственное натуральное число n (1 n 200 000) — количество посылок.

Затем следует n строк, в каждой из которых содержится по два числа d_i и w_i (1 d_i 200 000, 1 w_i 200 000) — последний день, когда можно доставить посылку без штрафа и стоимость опоздания для i-й посылки.

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

В первой строке выведите единственное число, равное минимально возможному суммарному штрафу. Во второй строке через пробел выведите n чисел, где i-е число — день, в который необходимо доставить i-ю посылку.

Если возможно несколько оптимальных расписаний, выведите любое из них.

Пример

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

Жадный алгоритм Использование сортировки

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

Максимальное число делителей#26984

Напишите программу, которая по заданному числу n находит такое число от 1 до n, включительно, что оно имеет максимальное число положительных целых делителей. Например, если n = 15, то ответом на задачу будет число — 12, так как у него 6 делителей: 1, 2, 3, 4, 6 и 12.

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

Дано одно натуральное число n (1 ≤ n ≤ 100 000).

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

В первой строке выведите число из диапазона от 1 до n, включительно, которое имеет максимальное число делителей. Во второй строке выведите число его делителей. Если в диапазоне от 1 до n существует несколько чисел с максимальным числом делителей, то выведите любое из них.

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

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

На связи#26983

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

Владимир, как истинный программист, решил заменить все цифры в своем сообщении на их названия на английском языке:

0 - zero
1 - one
2 - two
3 - three
4 - four
5 - five
6 - six
7 - seven
8 - eight
9 - nine

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

Формат ввода

В единственной строке введена строка s — сообщение Владимира для Даши. Строка может содержать любые символы с ASCII-кодами от 32 до 126. Длина строки не превосходит 4 × 10⁶.

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

Выведите измененное сообщение Владимира, в котором каждая цифра заменена на её название на английском языке.

Пример

Ввод	Вывод
Dashka, I love you!!! <3	Dashka, I love you!!! <three

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

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

Пути в музее#26978

Болик добрался до музея, здание которого представляет собой квадрат N × N, разбитый на N² равных квадратных залов. Вход в музей расположен в левом нижнем зале, а Лёлик ждет Болика в правом верхнем. Из каждого зала можно пройти в соседний с ним зал (два зала называются соседними, если у них есть общая стена).

Теперь Болик хочет определить сколько возможных путей до Лёлика у него есть. Конечно, его интересуют только пути кратчайшей длины.

Формат ввода

На вход подается одно натуральное число N (2 ≤ N ≤ 22).

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

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

Пример

Ввод	Вывод
3	6

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

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

Достать шоколадку#26977

Лёлик пришел в школу и решил подкрепиться шоколадкой. Он подошел к автомату с шоколадками и с удивлением обнаружил, что на него поставили защиту от первоклассников. А именно, для того, чтобы достать шоколадку, необходимо решить уравнение ax + b = c. Программа безопасности просит ввести целую часть корня этого уравнения, слово NO, если корней нет, или INFINITY, если корней бесконечно много. Чтобы ежедневно покупать шоколадки, Лёлик решил написать программу для решения уравнения, но не смог. А вы сможете?

Формат ввода

На вход подаются три действительных числа, разделенных пробелом: a, b, и c. Все числа по модулю не превышают 10⁹.

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

Выведите решение уравнения. Решением может являться либо целое число - целая часть корня уравнения,корня уравнения, либо слово NO, если корней нет, либо INFINITY, если корней бесконечно много.

Пример

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

Вычисление по заданной формуле Линейные алгоритмы

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

Поход в музей#26976

Лёлик наконец решил просветиться, и пошел в музей. В музее ему так понравилось, что он решил позвать туда своего друга Болика. Болик захотел присоединиться к своему другу, однако ему нужно доехать на автобусе №154 до метро, затем проехать три станции на метро, после чего проехать на автобусе №93 до музея. Помимо этого Болику нужно купить билет в музей. Теперь Болик хочет посчитать сколько денег ему нужно, чтобы встретиться с Лёликом в музее.

Известно, что проезд на автобусе стоит a рублей, в метро b рублей, а вход в музей стоит c рублей.

Формат ввода

На вход подаются три натуральных числа, разделенных пробелом: a, b, и c. Все числа не превышают 10⁹.

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

Выведите единственное натуральное число — сумму, которую должен иметь Болик.

Пример

Ввод	Вывод
10 30 50	100

Вычисление по заданной формуле Линейные алгоритмы

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

Числа Фибоначчи#25962

Числа Фибоначчи определяются рекуррентной формулой:

\(F_0 = F_1 = 1, \\ F_n = F_{n-1} + F_{n-2}, \text{ при}\ n \ge 2\)

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

В единственной строке входных данных записано натуральное число n (\(1<=n<=45\)).

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

Вывести одно n-е число Фибоначчи - F_n.

Примеры

№	Входные данные	Выходные данные
1	1	1
2	7	21

Динамическое программирование Рекуррентные последовательности

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

Двоичный поиск#25959

Реализуйте алгоритм бинарного поиска.

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

В первой строке входных данных содержатся натуральные числа N и K (\(0<N,\ K <= 100000\)). Во второй строке задаются N элементов первого массива, отсортированного по возрастанию. В третьей строке – K элементов второго массива.
Элементы обоих массивов - целые числа, каждое из которых по модулю не превосходит \(10^9\).

Формат выходных данных
Требуется для каждого из K чисел вывести в отдельную строку "YES", если это число встречается в первом массиве, и "NO" в противном случае.

Алгоритмы поиска Бинарный поиск в массиве

✓ 1 468✗ 2 525400лёгкаяВойти и решать

Хакер Василий#25958

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

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

Дано количество оценок Василия (не больше 100), затем сами оценки.

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

Требуется вывести исправленные оценки в том же порядке.

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

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

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

Это Бомба#24906

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

Инструкция:

Посчитайте числовой код для числа на дисплее соответственно приведённым правилам и введите его. Применяется первое подошедшее правило:

1. Если число <= 2, то числовой код равен 1.

2. Если число заканчивается на 7, то нужно отнять от него 5. Посчитайте числовой код для нового числа и прибавьте 1.

3. Если число делится на 4 без остатка, его числовой код равен сумме кодов для числа,делённого на 4 и числа, делённого на 2.

4. Во всех остальных случаях к числу нужно прибавить 1. Посчитайте числовой код для нового числа и прибавьте 2.

Какой числовой код нужно ввести Мише?

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

В единственной строке содержится одно число от 1 до 10⁸, которое отображается на дисплее.

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

Выведите в ответ одно число, которое Мише нужно срочно ввести.

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

Выведите в ответ одно число, которое Мише нужно срочно ввести.

Ввод	Вывод
1	1
10	12

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

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