Алгоритмы

Расшифровка письменности Майя оказалась более сложной задачей, чем предполагалось ранними исследованиями. На протяжении более чем двух сотен лет удалось узнать не так уж много. Основные результаты были получены за последние 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

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

2

Дана последовательность целых чисел. Найти в ней минимальное число, не кратное 3. В последовательности имеется как минимум одно число не кратное 3

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

Примеры

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

 
 

Дана последовательность целых чисел. Найти в ней минимальное число, кратное 3. В последовательности имеется как минимум одно число кратное 3

Входные данные: В первой строке вводится число N - количество чисел в последовательности (N - положительное число, не превышающее 100) , а затем N целых чисел, по одному в строке (каждое число не превышает по модулю 1000).
Выходные данные: Выведите ответ на задачу

Примеры

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

 
 

Дана последовательность целых чисел. Найти в ней максимальное число, кратное 3. В последовательности имеется как минимум одно число кратное 3

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

Примеры

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

 
 

Есть озеро, рядом с которым хотят построить дом. Архитектурный проект (форма дома) уже утверждён, можно только выбрать расположение дома так, чтобы он оказался рядом с озером. Желательно выбрать расположение дома рядом с озером так, чтобы у как можно большего числа жителей дома окна выходили на озеро, то есть чтобы длина общей границы дома и озера была максимальной.

План дома и озера задан в виде изображения на клетчатой бумаге, в котором отмечены клетки, принадлежащие дому и озеру. Первая строка входных данных содержит число N – количество строк в плане дома и озера. Вторая строка входных данных содержит число M – количество столбцов в плане дома и озера.

Следующие N строк содержат по M символов – план дома. Символ «.» в этих строках обозначает пустую клетку, символ «H» обозначает» обозначает клетку дома. План дома является связной областью и не содержит «дырок» внутри. В плане есть хотя бы одна клетка, принадлежащая дому. Следующие N строк по M символов в каждой содержат план озера, в этих строках символ «.» обозначает пустую клетку, символ «W» обозначает клетку, занятую озером. План» обозначает клетку, занятую озером. План озера является связной областью и не содержит «дырок» внутри. В плане есть хотя бы одна клетка, принадлежащая озеру.

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

Ввод	Вывод	Примечание
5 6 ...... .HHHH. .HHHH. .HHHH. ...... ..WWW. ..WWW. ..WWW. ..WWW. ..WWW.	3	. . . . W W W H H H H W W W H H H H W W W H H H H W W W       . . . . W W W
5 7 ...HHH. .H...H. .H.HHH. .H.H... .HHH... ....... ..WWWWW WWW...W W.W...W ..W....	11

В турнире участвуют 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.

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

Формат входных данных
Программа получает на вход два целых числа N и K (N > 0, 0 ≤ K ≤ N), записанные в отдельных строках, — текущее число членов совета и число родителей в совете.

Формат выходных данных
Программа должна вывести единственное число — минимальное число родителей, которое необходимо ввести в совет.

Пояснение к примеру
В примере совет состоит из 27 человек, из которых родители составляют 7 человек. Если в совет ввести ещё 3 родителей, то в совете станет 30 человек, из которых родителей будет 10.

Входные данные 
Входная строка содержит четыре числа, разделённые пробелами: a , b , c и N .

Выходные данные 
В первой строке нужно вывести число K способов, которыми можно купить заданное количество мастики (N кг), не вскрывая ящики. В каждой из последующих K строчек программа должна вывести (через пробелы) три числа, ka , kb и kc : количество ящиков 1, 2 и 3 типов для каждого из K вариантов закупки. Варианты должны выводиться в лексикографическом порядке: сначала варианты с наименьшим значением ka , для одинаковых ka – сначала варианты с наименьшим значением kb и т.д.

 

Примеры

№	Входные данные	Выходные данные
1	15 17 21 185	5 0 1 8 1 10 0 3 7 1 5 4 2 7 1 3

Дан массив произвольных целых чисел. Напишите программу, которая за один проход по массиву находит непрерывный кусок, сумма чисел в котором максимальна.
Примечание. Фактически требуется найти такие i и j (i<=j), что сумма всех элементов массива от ai до aj включительно будет максимальна. Индексация элементов начинается с 1.

Входные данные
В первой строке задается натуральное число n <= 100000 — количество элементов в массиве. В следующих n строках задаются сами элементы массива — целые числа, по модулю не превосходящие 30 000.

Выходные данные
Выведите пару искомых значений индексов. Если таких пар несколько, то j должно быть минимально возможным, а при равных j значение i должно быть максимально возможным. В первой строке выведите i, во второй - j.
 

Примеры

№	Входные данные	Выходные данные
1	5 -1 2 3 -2 2	2 3
2	7 2 -2 3 -1 5 -2 7	3 7

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

Входные данные
Первая строка содержит размер массива N. Во второй строке через пробел задаются N чисел – элементы массива (целые неотрицательные числа, не превышающие 1000). Гарантируется, что 0 < N ≤ 10000.

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

Примеры

№	Входные данные	Выходные данные
1	6 4 14 5 8 12 13	5 8 13

Дан массив чисел. Необходимо записать в другой массив все простые числа исходного массива. Если в исходном массиве нет простых чисел, программа должна вывести число 0.

Входные данные
Первая строка содержит размер массива N. Во второй строке через пробел задаются N натуральных чисел – элементы массива (все числа не превышают 1000). Гарантируется, что 0 < N ≤ 10000.

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

Примеры

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

На плоскости даны N точек. Вам требуется построить выпуклую оболочку данного множества точек. Выведите два числа: периметр и площадь.

Входные данные
Первая строка содержит количество точек N, 1≤N≤10000. Каждая из последующих N строк содержит два целых числа – координаты xi и yi. Все числа по модулю не превосходят 104.

Выходные данные
Вывести два числа: периметр и площадь выпуклой оболочки.
 

Ввод	Вывод
4 0 0 3 4 3 1 6 0	16.0000000000 12.0000000000

Дано N целых чисел. Найти третий по величине максимальный элемент последовательности (элемент, который бы стоял третьим, если бы входные данные отсортировали по неубыванию).

Входные данные
В первой строке задается число N (\(3<=N<=10^5\)). Далее идут N строк, по одному числу в каждой строке.

Выходные данные
Выведите третий максимальный элемент.
 

 

Примеры

№	Входные данные	Выходные данные
1	7 10 15 35 35 14 35 10	35
2	5 10 5 7 11 9	9

 
 

Дано натуральное число \(n  <= 10^9,\) определите количество натуральных чисел, меньших \(n\) и взаимно простых с \(n\). Это число обозначается \( f(n) \)и называется фи-функцией Эйлера. Сложность алгоритма должна быть \( O(\sqrt{n})\) .

Входные данные
На вход подается натуральное число n.

Выходные данные
Выведите ответ на задачу.
 

 

Примеры

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

Примеры

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

Даны натуральные числа a, b, c. Если уравнение \(ax+by=c\) имеет решения в целых числах, то выберите то решение, в котором число x имеет наименьшее неотрицательное значение и выведите это решение (два числа x и y через один пробел). Если решения не существует, то выведите слово Impossible.

Входные данные 
Вводятся три натуральных числа.

Выходные данные
Выведите ответ на задачу.

Примечание
Сложность алгоритма должна быть равна сложности алгоритма Евклида + константа.
 

Примеры

№	Входные данные	Выходные данные
1	1 2 3	1 1
2	10 6 8	2 -2

Обеденный перерыв Гомера Симпсона составляет T миллисекунд. Один гамбургер Гомер съедает за N миллисекунд, один чизбургер - за M. Какое количество гамбургеров и чизбургеров нужно съесть, чтобы потраченное время было как можно больше, не превышая T. При равенстве потраченного времени необходимо максимизировать суммарное количество съеденных гамбургеров и чизбургеров.

Ограничения: 1 <=M, N, T, <= 1000000 , все числа целые.

Входные данные
В первой строке находятся три числа - M, N и T, разделённые пробелами.

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

Ввод	Вывод
1 2 1000	1000
2 1 1000	1000
3 6 1000	333 1

Дано два целых числа x и y - координаты точки.
Необходимо определить цвет этой точки на рисунке. 
Для вывода цветов используйте следующие обозначения:
W - белый (все точки, находящиеся за границей рисунка, считаются белыми)
G - зеленый
Y - желтый
R - красный
B - черный (если точка попала на границу областей рисунка)

Одна клеточка рисунка равна 1.

Картинку можно увеличить, щелкнув по ней (откроется в новом окне).

 

Примеры

№	Входные данные	Выходные данные
1	-6 2	W
2	0 1	R

n школьников делят k яблок “поровну”, то есть так, чтобы количество яблок, доставшихся любым двум школьникам, отличалось бы не более, чем на 1.
Запрещено использовать какие-либо алгоритмические конструкции (if, while, for и т.п.), кроме арифметических операций 

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

№	Входные данные	Выходные данные
1	7 30	5