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

Игра для Пети и Вани#37559

Некоторые уроки в школе для Вани и Пети очень скучны. На этих уроках Петя и Ваня придумали игру. Сначала мальчики записывают на листке два различных натуральных числа a и b .
Ход игры заключается в следующем: среди записанных чисел выбирают p и q такие, что модуля их разности $| p - q |$ еще нет на листке, и дописывают его.
Проигрывает тот, кто не может сделать ход.
Определите, кто из ребят окажется победителем при правильной игре обоих. Ваня вежливый мальчик, поэтому всегда ходит вторым.

Входные данные: В первой и единственной строке записано два различных натуральных числа 1 <= a , b <= 10^9 , разделенные пробелом - два исходных числа на листке.

Выходные данные: Выведите имя победителя в этой игре (Petya или Vanya)

Примечание: В первом примере Петя первым ходом допишет на листок число |6−2| = 4 . Больше ходов нет, поэтому выигрывает Петя. Во втором примере первым ходом на листок будет дописано число |4−1| = 3 . Затем Ваня может записать |3−1| = 2 , тогда у Пети ходов не останется. Побеждает Ваня.

Примеры

№	Входные данные	Выходные данные
1	6 2	Petya
2	4 1	Vanya

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

Задача для Пети и Вани#37555

Пятиклассники Петя и Ваня изучили на уроках математики следующий алгоритм Евклида:

Пусть a, b — числа, НОД которых надо найти.
Если b = 0, то число a — искомый НОД.
Если b > a, то необходимо поменять местами числа a и b.
Присвоить числу a значение a – b.
Вернуться к шагу 2.

Маша придумала для них задачу на закрепление. Она попросила мальчиков придумать такие числа a, b, c и d, что в процессе реализации алгоритма Евклида для заданной пары чисел (a, b) наступает такой момент, когда перед исполнением шага 2 число a будет равно c, а число b будет равно d.

Напишите для Маши программу, которая проверит, удовлетворяют ли числа a, b, c, d условиям Маши.

Входные данные: Первая строка входных данных содержит количество наборов входных данных K ($1 <= K <= 100$). Далее идут описания этих наборов. Каждое описание состоит из двух строк. Первая из них содержит два целых числа: a, b ($1 <= a,\ b <= 10^{18}$). Вторая строка – два целых числа: c, d ($1 <= c,\ d <= 10^{18}$).
Все числа в строках разделены пробелом.

Выходные данные: Для каждого набора входных данных выведите слово «YES», если в процессе применения алгоритма Евклида к паре чисел (a, b) в какой-то момент получается пара (c, d). В противном случае выведите слово «NO».

Примеры

№	Входные данные	Выходные данные
1	2 20 10 10 10 10 7 2 4	YES NO

Вывод формулы НОД и алгоритм Евклида

✓ 106✗ 1 7511 000средняяВойти и решать

Бомбоубежища#37258

Штаб гражданской обороны Тридесятой области решил обновить план спасения на случай ядерной атаки. Известно, что все n селений Тридесятой области находятся вдоль одной прямой дороги. Вдоль дороги также расположены m бомбоубежищ, в которых жители селений могут укрыться на случай ядерной атаки.

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

Входные данные: В первой строке вводится число n - количество селений (1 <= n <= 100000). Вторая строка содержит n различных целых чисел, i-е из этих чисел задает расстояние от начала дороги до i-го селения. В третьей строке входных данных задается число m - количество бомбоубежищ (1 <= m <= 100000). Четвертая строка содержит m различных целых чисел, i-е из этих чисел задает расстояние от начала дороги до i-го бомбоубежища. Все расстояния положительны и не превышают 10⁹. Селение и убежище могут располагаться в одной точке.

Выходные данные: Выведите n чисел - для каждого селения выведите номер ближайшего к нему бомбоубежища. Бомбоубежища пронумерованы от 1 до m в том порядке, в котором они заданы во входных данных.

Примеры

№	Входные данные	Выходные данные
1	4 1 2 6 10 2 7 3	2 2 1 1

Быстрая сортировка

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

Такси#37257

После затянувшегося совещания директор фирмы решил заказать такси, чтобы развезти сотрудников по домам. Он заказал N машин – ровно столько, сколь у него сотрудников. Однако когда они подъехали, оказалось, что у каждого водителя такси свой тариф за 1 километр.

Директор знает, какому сотруднику сколько километров от работы до дома (к сожалению, все сотрудники живут в разных направлениях, поэтому нельзя отправить двух сотрудников на одной машине). Теперь директор хочет определить, какой из сотрудников на каком такси должен поехать домой, чтобы суммарные затраты на такси (а их несет фирма) были минимальны.

Входные данные: Первая строка входных данных содержит натуральное число N (1 ≤ N ≤ 1000) – количество сотрудников компании (совпадающее с количеством вызванных машин такси). Далее записано N чисел, задающих расстояния в километрах от работы до домов сотрудников компании (первое число – для первого сотрудника, второе – для второго и т.д.). Все расстояния – положительные целые числа, не превышающие 1000. Далее записано еще N чисел – тарифы за проезд одного километра в такси (первое число – в первой машине такси, второе – во второй и т.д.). Тарифы выражаются положительными целыми числами, не превышающими 10000.

Выходные данные: Программа должна вывести N чисел. Первое число – номер такси, в которое должен сесть первый сотрудник, второе число – номер такси, в которое должен сесть второй и т.д., чтобы суммарные затраты на такси были минимальны. Если вариантов рассадки сотрудников, при которых затраты минимальны, несколько, выведите любой из них.

Примеры

№	Входные данные	Выходные данные
1	3 10 20 30 50 20 30	1 3 2
2	5 10 20 1 30 30 3 3 3 2 3	5 1 3 2 4

Быстрая сортировка

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

Спасаем роботов#37256

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

Входные данные
В первой строке вводится число n - количество роботов($1 <= n <= 100000$). Вторая строка содержит n различных целых чисел, i-е из этих чисел задает расстояние от начала дороги до места работы i-го робота. В третьей строке входных данных задается число m - количество ремонтных мастерских (1 <= m <= 100000). Четвертая строка содержит m различных целых чисел, i-е из этих чисел задает расстояние от начала дороги до i-й ремонтной мастерской. Все расстояния положительны и не превышают 10⁹. Робот и мастерская могут располагаться в одной точке.

Выходные данные
Выведите n чисел - для каждого робота выведите номер ближайшей к нему ремонтной мастерской. Ремонтные мастерские пронумерованы от 1 до m в том порядке, в котором они заданы во входных данных.

Примеры

№	Входные данные	Выходные данные
1	4 1 2 6 10 2 7 3	2 2 1 1

Быстрая сортировка

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

Преобразуем четырехзначные#37016

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

1. Можно увеличить первую цифру числа на 1, если она не равна 9.
2. Можно уменьшить последнюю цифру на 1, если она не равна 1.
3. Можно циклически сдвинуть все цифры на одну вправо.
4. Можно циклически сдвинуть все цифры на одну влево.

Например, применяя эти правила к числу 1234 можно получить числа 2234, 1233, 4123 и 2341 соответственно. Точные правила игры Витя пока не придумал, но пока его интересует вопрос, как получить из одного числа другое за минимальное количество операций.

Входные данные: на вход подаются два различных четырехзначных числа, каждое из которых не содержит нулей. Каждое число с новой строки

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

Примеры

№	Входные данные	Выходные данные
1	1234 4321	1234 2234 3234 4323 4322 4321

Обход в ширину

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

Эвакуация#34976

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

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

Формат входных данных
В первых двух строках вводятся два натуральных числа N, K ($1 <= N <= 100000$, $1 <= K <= N$) — количество бункеров и количество выходов соответственно. В третьей строке через пробел записаны K различных чисел от 1 до N, обозначающих номера бункеров, в которых расположены выходы. В четвертой строке идёт число M ($1 <= M <= 100000$) — количество туннелей. В следующих M строках вводятся пары чисел – номера бункеров, соединенных туннелем.
По каждому из туннелей можно двигаться в обе стороны. В организации не существует туннелей, ведущих из бункера в самого себя, зато может существовать более одного туннеля между парой бункеров.

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

Обход в ширину

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

Максимальная прибыть (ТЯжелая - 1, дубль 24755)#34958

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

Про каждую задачу известно время t_i, которое нужно затратить, чтобы сделать её, а также прибыль p_i, которую сделанная задача принесёт компании. Вы хотите включить в план некоторые задачи так, чтобы:

Суммарное время, затраченное на выполнение задач, включённых в план, не превышало T.
Суммарная прибыль от выполнения этих задач была максимальна.

Составьте план, обладающий описанными выше свойствами и определите прибыль, получаемую в результате выполнения этого плана.

Обратите внимание на то, что единственный подходящий под условия план может не содержать ни одной задачи.

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

В первой строке находятся натуральные числа T (1 ≤ T ≤ 100 000) и n (1 ≤ n ≤ 10) - число единиц времени в месяце и число задач.

Следующие n строк содержат по два натуральных числа t_i и p_i (1 <= t_i, p_i <= 100 000) - время, которое необходимо затратить на выполнение i-й задачи и прибыль, которую можно получить, выполнив её.

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

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

Примеры

№	Входные данные	Выходные данные
1	10 3 8 100 3 10 3 10	100
2	10 4 5 10 5 20 2 5 2 6	31

битмаски Перебор

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

Интересные числа#34923

Роман коллекционирует числа, кажущиеся ему интересными. Например, сейчас он считает интересным положительные числа, запись которых в системе счисления с основанием k заканчивается нечетным числом нулей. Например, при k = 2 такими числами являются 2₁₀ = 10₂, 24₁₀ = 11000₂.
Для того, чтобы пополнить свою коллекцию, Роман хочет найти n-ое в порядке возрастания такое число. Поскольку n он взял достаточно большим, то вручную у него это сделать не получается. Помогите Роману — напишите программу, которая найдет число, которое нужно ему для пополнения коллекции.

Входные данные: Первая строка содержит два целых числа (1 <= n <=10¹⁵, 2 <= k <= 10).

Выходные данные: Выведите n-ое в порядке возрастания число, запись которого в системе счисления с основанием k заканчивается на нечетное число нулей. Это число необходимо вывести в десятичной системе счисления.

Примеры

входные данные
1 2

выходные данные
2

входные данные
10 10

выходные данные
110

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

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

Учитель математики Юрий Петрович#34916

Легендарный учитель математики Юрий Петрович придумал забавную игру с числами. А именно, взяв произвольное целое число, он переводит его в двоичную систему счисления, получая некоторую последовательность из нулей и единиц, начинающуюся с единицы. (Например, десятичное число $19_{10} = 1\cdot2^4+0\cdot2^3+0\cdot2^2+1\cdot2^1+1\cdot2^0 $ в двоичной системе запишется как 10011₂.) Затем учитель начинает сдвигать цифры полученного двоичного числа по циклу (так, что последняя цифра становится первой, а все остальные сдвигаются на одну позицию вправо), выписывая образующиеся при этом последовательности из нулей и единиц в столбик — он подметил, что независимо от выбора исходного числа получающиеся последовательности начинают с некоторого момента повторяться. И, наконец, Юрий Петрович отыскивает максимальное из выписанных чисел и переводит его обратно в десятичную систему счисления, считая это число результатом проделанных манипуляций. Так, для числа 19 список последовательностей будет таким:

...
и результатом игры, следовательно, окажется число $1\cdot2^4+1\cdot2^3+1\cdot2^2+0\cdot2^1+0\cdot2^0 = 28_{10} $

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

Решите эту задачу с использованием битовых операций!

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

Входной файл содержит одно целое число N (0<=N<=32767).

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

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

Примеры

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

Битовые операции Двоичная система счисления

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

Музыкальный плейлист#34890

Недавно Вася решил, что все существующие алгоритмы сортировки слишком сложны, и обязательно должен существовать более простой и эффективный алгоритм.
Для начала Вася решил рассмотреть следующий алгоритм: по данному массиву целых чисел a размером n, он создает пустой массив b, а дальше на каждой из n последующих итераций будет брать k-й элемент массива a (или последний, если такого нет), удалять его из a, а затем записывать в конец b. Таким образом, после n итераций Вася планирует в качестве массива b получить отсортированный по возрастанию массив a.
Однако, протестировав на нескольких примерах, Вася понял, что этот алгоритм работает не всегда. Так, например, если исходный массив a=[1,2,3,4] и k=2, то после 4 итераций массив b вовсе не будет отсортированным:
После первой итерации в b добавляется число 2, а массив a равен [1,3,4];
После второй итерации в конец b добавляется число 3, а массив a равен [1,4];
После третьей итерации в конец b добавляется число 4, а массив a равен [1];
На последней, четвертой итерации, в конец b добавляется число 1, а массив a становится пустым;
Таким образом, итоговый массив b будет выглядеть так: [2,3,4,1]. Нетрудно заметить, что он не является отсортированным по возрастанию. Однако, Вася решил так легко не сдаваться и по данному числу k научиться находить такой массив a, содержащий перестановку последовательности натуральных чисел от 1 до n, который будет сортироваться по возрастанию методом, описанным выше. Помогите ему - по данным числам n и k найдите хотя бы один подходящий массив a.

Формат входных данных
В единственной строке содержится два числа n и k - размер массива и номер элемента, берущегося на каждой итерации, соответственно (1≤k≤n≤1000).

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

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

Жадный алгоритм реализация

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

Жребий Крижановского#34880

Петя играет с друзьями в игру, которую иногда называют "Жребий Крижановского". Правила игры следующие: в каждом туре каждый игрок загадывает произвольное натуральное число. После этого игрок, загадавший минимальное число, которое не повторяется, выигрывает в этом туре, причем его выигрыш равен этому числу. Например, если играют 6 человек и были загаданы числа 3, 2, 1, 1, 4 и 2, то выиграл первый игрок, причем его выигрыш равен 3. Если все загаданные числа повторяются, то тур считается ничейным и никто баллов не получает.

Общий выигрыш игрока за игру равен сумме баллов за все сыгранные туры.

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

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

Входные данные
В первой строке вводится число n - количество игроков (2 <= n <= 100). Вторая строка содержит n чисел - баллы игроков перед последним туром (неотрицательные целые числа, не большие 100). Баллы перечислены в том порядке, в котором игроки обычно называют числа (то есть Петины баллы указаны последними). В третьей строке задано (n-1) число - числа, названные игроками в последнем туре (числа не превышают 100), в том порядке, в котором они их называли.

Выходные данные
Выведите число, которое следует назвать Пете.

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

Ввод	Вывод
6 0 0 0 0 0 0 2 3 4 5 6	1
6 8 3 12 5 0 9 2 1 3 1 4	2

Сортировка подсчетом

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

Чехарда#34851

Дорожка замощена плитками в один ряд, плитки пронумерованы числами от 1 до 1000. На плитках с номерами A, B и C (A < B < C) сидят три кузнечика, которые играют в чехарду по следующим правилам:
1. На одной плитке может находиться только один кузнечик.
2. За один ход один из двух крайних кузнечиков (то есть с плитки A или с плитки C) может перепрыгнуть через среднего кузнечика (плитка B) и встать на плитку, которая находится ровно посередине между двумя оставшимися кузнечиками (то есть между B и C или A и B соответственно). Если между двумя оставшимися кузнечиками находится чётное число плиток, то он может выбрать любую из двух центральных плиток.
Например, если кузнечики первоначально сидели на плитках номер 1, 5, 10, то первым ходом кузнечик с плитки номер 10 может перепрыгнуть на плитку номер 3 (она находится посередине между 1 и 5), или кузнечик с плитки номер 1 может перепрыгнуть на плитку номер 7 или 8 (эти две плитки находятся посередине между плитками 5 и 10).
Даны три числа: A, B, C. Определите, какое наибольшее число ходов может продолжаться игра.

Формат входных данных
Программа получает на вход три целых числа A, B и C (1 <= A < B < C <= 1000), записанных в отдельных строках.
Формат выходных данных
Выведите одно число — наибольшее количество ходов, которое может продолжаться игра.

Ввод	Вывод	Примечание
1 4 6	2	В примере сначала кузнечик с плитки №6 прыгает на плитку №3. Затем кузнечик с плитки №4 прыгает на плитку №2.

Жадный алгоритм Цикл while

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

Ремонт дороги#34849

Длина автомобильной дороги составляет N километров. Часть дороги необходимо отремонтировать. При обследовании дорога была разбита на N участков длиной 1 километр, и для каждого участка было определено, нуждается ли он в ремонте или нет, после чего был составлен план дороги, на котором отмечены участки, нуждающиеся в ремонте.

Для ремонта дороги можно привлечь несколько компаний-подрядчиков. Каждая компания может отремонтировать только непрерывный фрагмент дороги. При этом из-за требований антимонопольного законодательства длина фрагмента дороги, который ремонтирует одна компания, не должна превышать L километров (даже если на фрагменте, который ремонтирует одна компания, есть не нуждающиеся в ремонте участки, общая длина данного фрагмента не должна превышать L километров).

Определите, какое наименьшее количество компаний-подрядчиков необходимо привлечь для ремонта дороги.
Первая строка входных данных содержит целое число L (L > 0) — максимальную длину фрагмента дороги, который может отремонтировать одна компания. Во второй строке входных данных записано целое число N (N > 0) — длина всей дороги. Следующие N строк содержат по одному числу, равному 0 или 1. Число 1 обозначает, что соответствующий участок дороги нуждается в ремонте, число 0 — что участок не требует ремонта.
Программа должна вывести одно целое число — минимальное количество компанийподрядчиков, которое необходимо привлечь для ремонта дороги.

Ввод	Вывод	Примечание
3 8 0 0 1 0 1 0 1 0	2	Первая компания может отремонтировать участок номер 3, вторая компания — участки с 5 по 7.

Жадный алгоритм

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

Задача из ЕГЭ#34848

Андрей готовился к ЕГЭ по информатике и встретил в демо-версии ЕГЭ 2015 года такую задачу:
Автомат получает на вход четырёхзначное число. По этому числу строится новое число по следующим правилам.
1. Складываются первая и вторая, а также третья и четвёртая цифры исходного числа.
2. Полученные два числа записываются друг за другом в порядке убывания (без разделителей).
Пример. Исходное число: 3165. Суммы: 3+1 = 4; 6+5 = 11. Результат: 114.
Укажите наименьшее число, в результате обработки которого автомат выдаст число 1311.
Андрей решил, что для самопроверки он напишет программу, которая решает подобную задачу. Мы думаем, что вы тоже с этим справитесь.
Программа получает на вход некоторое натуральное число N, которое может содержать две, три или четыре цифры.

Программа должна вывести такое наименьшее целое четырёхзначное число K, после применения к которому описанного выше алгоритма получается число N. Если же такого числа не существует, программа должна вывести число 0.

Ввод	Вывод
1311	2949

Задача на реализацию Простые задачи на перебор

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

Поле для игры#34839

Петя создает поле для своей новой игры. Поле разделено на клетки и представляет собой прямоугольник размером N на M клеток. Пусть клетки имеют координаты от 1 до N слева направо по горизонтали и от 1 до M снизу вверх по вертикали.

На этом поле Петя уже разместил супермаркет, который представляет собой прямоугольник размером C на D клеток (C –– размер по горизонтали, D –– по вертикали), и нижняя левая клетка супермаркета имеет координаты A, B на игровом поле (см. примеры и рисунки). Теперь Пете нужно разместить на том же игровом поле здание биржи. Здание биржи представляет собой прямоугольник размером E на F клеток (E –– по горизонтали, F –– по вертикали). Естественно, что здание биржи должно полностью располагаться на игровом поле и не должно иметь общих клеток с супермаркетом (но может касаться его).

Сколькими способами Петя сможет разместить здание биржи?

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

Вводятся числа N, M, A, B, C, D, E, F, каждое в отдельной строке. Числа удовлетворяют следующим условиям: 1 ≤ N ≤ 100, 1 ≤ M ≤ 100, 1 ≤ A ≤ N, 1 ≤ B ≤ M, 1 ≤ A + C - 1 ≤ N, 1 ≤ B + D - 1 ≤ M, 1 ≤ E ≤ N, 1 ≤ F ≤ M.

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

Выведите количество способов разместить здание биржи.

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

Примечание

Рисунки ниже соответствуют приведенным примерам. На рисунках серым показано здание супермаркета. Точками отмечены варианты размещения нижнего левого угла здания биржи.

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

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

Имена на Тау Кита#34823

На далекой планете Тау Кита есть непонятные нам обычаи. Например, таукитяне очень необычно для землян выбирают имена своим детям. Родители так выбирают имя ребенку, чтобы оно могло быть получено как удалением некоторого набора букв из имени отца, так и удалением некоторого набора букв из имени матери. Например, если отца зовут «abacaba», а мать — «bbccaa», то их ребенок может носить имена «a», «bba», «bcaa», но не может носить имена «aaa», «ab» или «bbc». Возможно, что имя ребенка совпадает с именем отца и/или матери, если оно может быть получено из имени другого родителя удалением нескольких (возможно, ни одной) букв.

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

Формально, строка S лексикографически больше строки T, если выполняется одно из двух условий: строка T получается из S удалением одной или более букв с конца строки S;
первые (i - 1) символов строк T и S не различаются, а буква в i-й позиции строки T следует в алфавите раньше буквы в i-й позиции строки S.

Требуется написать программу, которая по именам отца и матери находит лексикографически наибольшее имя для их ребенка.

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

Первая строка входного файла содержит X — имя отца. Вторая строка входного файла содержит Y — имя матери. Каждое имя состоит из строчных букв латинского алфавита, включает хотя бы одну букву и имеет длину не более 105 букв.

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

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

Примеры
входные данные

abcabca
abcda

выходные данные

ca

входные данные

ccba
accbbaa

выходные данные

ccba

Сортировка подсчетом

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

Драгоценные камни#34821

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

Купцы хотят продать шаху n драгоценных камней, которые они привезли с собой. Для этого они выкладывают их перед шахом в ряд, после чего шах оценивает эти камни и принимает решение о том, купит он их или нет. Видов драгоценных камней на Востоке известно не очень много всего 26, поэтому мы будем обозначать виды камней с помощью строчных букв латинского алфавита. Шах обычно оценивает камни следующим образом. Он заранее определил несколько упорядоченных пар типов камней: (a1, b1), (a2, b2), ..., (ak, bk). Эти пары он называет красивыми, их множество мы обозначим как P. Теперь представим ряд камней, которые продают купцы, в виде строки S длины n из строчных букв латинского алфавита. Шах считает число таких пар (i,j), что 1 ≤ i < j ≤ n, а камни Si и Sj образуют красивую пару, то есть существует такое число 1 ≤ q ≤ k, что Si=aq и Sj=bq.

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

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

Первая строка входного файла содержит целые числа n и k (1 ≤ n ≤ 100000, 1 ≤ k ≤ 676) число камней, которые привезли купцы и число пар, которые шах считает красивыми. Вторая строка входного файла содержит строку S, описывающую типы камней, которые привезли купцы.

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

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

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

Примеры
входные данные

7 1
abacaba
aa

выходные данные

входные данные

7 3
abacaba
ab
ac
bb

выходные данные

Сортировка подсчетом

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

Расшифровка письменности МАйя#34820

Расшифровка письменности Майя оказалась более сложной задачей, чем предполагалось ранними исследованиями. На протяжении более чем двух сотен лет удалось узнать не так уж много. Основные результаты были получены за последние 30 лет.

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

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

Археологи ищут некоторое слово W. Они знают значки для него, но не знают все возможные способы их расположения. Поскольку они знают, что Вы приедете на IOI ’06, они просят Вас о помощи. Они дадут Вам g значков, составляющих слово W, и последовательность S всех значков в надписи, которую они изучают, в порядке их появления. Помогите им, подсчитав количество возможных появлений слова W.

Задание

Напишите программу, которая по значкам слова W и по последовательности S значков надписи подсчитывает количество всех возможных вхождений слова W в S, то есть количество всех различных позиций идущих подряд g значков в последовательности S, которые являются какой-либо перестановкой значков слова W .

Ограничения

1 ≤ g ≤ 3 000, g – количество значков в слове W

g ≤ |S| ≤ 3 000 000 где |S| – количество значков в последовательности S

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

На вход программы поступают данные в следующем формате:

СТРОКА 1: Содержит два числа, разделенных пробелом – g и |S|.
СТРОКА 2: Содержит g последовательных символов, с помощью которых записывается слово W . Допустимы символы: ‘a’-‘z’ и ‘A’-‘Z’; большие и маленькие буквы считаются различными.
СТРОКА 3: Содержит |S| последовательных символов, которые представляют значки в надписи. Допустимы символы: ‘a’-‘z’ и ‘A’-‘Z’; большие и маленькие буквы считаются различными.

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

Единственная строка выходных данных программы должна содержать количество возможных вхождений слова W в S.

Важно для программирования на PASCAL

По умолчанию во FreePascal переменная типа string имеет ограничение размера в 255 символов. Если Вы хотите использовать более длинные строки, Вы должны добавить директиву {$ H +} в ваш код, сразу после строки program ...;.

Примеры
входные данные

4 11
cAda
AbrAcadAbRa

выходные данные

Сортировка подсчетом

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

Турнир#34778

В турнире участвуют N команд. Турнир проводится по олимпийской системе (команды играют на вылет, проигравшие команды выбывают из турнира, выигравшие проходят в следующий тур, ничьих не бывает). Число команд в этой задаче будет степенью двойки: N = 2 ^k .

Все команды пронумерованы числами от 1 до N. В первом туре играют команды с номерами 1 и 2, 3 и 4, 5 и 6 и т. д., всего играется N/2 матчей. По результатам этих матчей команды выходят во второй тур. Во втором туре играют победители первой и второй игры первого тура, победители третьей и четвёртой игры первого тура и т. д. Они выходят в третий тур. В третьем туре играют вместе победители первой и второй игры второго тура, победители третьей и четвёртой игры второго тура и т. д.

Вам даны результаты всех матчей. Определите номер команды, которая стала победителем турнира.
В первой строке входных данных записано число N – количество команд, участвовавших в турнире. Оно является степенью двойки и может принимать значения от 2⁰ = 1 до 2¹⁶ = 65536. Следующие N − 1 строк содержат результаты всех сыгранных матчей. Первые N/2 строк из них являются результатами матчей первого тура, затем идёт N/4 строк с результатами второго тура, N/8 строк с результатами третьего тура и т. д.

Результат каждого матча является одним из двух возможных чисел: 1 или 2. Число 1 означает, что в матче выиграла первая команда (номер которой меньше), число 2 означает, что в матче выиграла вторая команда (номер которой больше).
Программа должна вывести одно число – номер победившей в турнире команды.

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

Примечание к ответу
Далее нарисована схема турнира для примера из условия. В турнире участвовало 8 команд. Результаты матчей: 1, 2, 2, 1, 2, 1, 1.
В первом туре играли команды 1 и 2, 3 и 4, 5 и 6, 7 и 8. Результаты матчей первого тура: 1, 2, 2, 1, во второй тур вышли команды 1, 4, 6, 7.
Во втором туре играли команды 1 и 4, 6 и 7. Результаты матчей второго тура: 2, 1.
В третий тур вышли команды 4 и 6. В последнем, третьем, туре играют команды 4 и 6, результат матча: 1, поэтому победителем турнира является команда 4.

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

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