Задача A. Сплошной кафель

Автор:А. Кленин, Н. Кленина
Входной файл: input.txt   Ограничение времени:1 сек
Выходной файл: output.txt   Ограничение памяти:64 Мб

Условие

Плитка кафеля имеет форму квадрата размером 1 × 1, раскрашенного в один из цветов, заданных буквами от "a" до "z".

Если замостить квадратную область размером N × N разноцветными плитками, то могут образоваться горизонтальные или вертикальные одноцветные полосы длиной N плиток.

По описанию области следует определить цвета горизонтальных и вертикальных полос.

Формат входного файла

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

Формат выходного файла

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

Ограничения

1 ≤ N ≤ 100

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
4
owww
owow
wwow
oowo
NO
2
3
ibi
ibi
ibi
bi

Problem B. Very Simple Problem

Author:Far-Eastern Subregional
Input file: input.txt   Time limit:1 sec
Output file: output.txt   Memory limit:8 Mb

Statement

During a preparation of programming contest, its jury is usually faced with many difficult tasks. One of them is to select a problem simple enough to most, if not all, contestants to solve.

The difficulty here lies in diverse meanings of the term "simple" amongst the jury members. So, the jury uses the following procedure to reach a consensus: each member weights each proposed problem with a positive integer "complexity rating" (not necessarily different for different problems). The jury member calls "simplest" those problems that he gave the minimum complexity rating, and "hardest" those problems that he gave the maximum complexity rating.

The ratings received from all jury members are then compared, and a problem is declared as "very simple", if it was called as "simplest" by more than a half of the jury, and was called as "hardest" by nobody.

Input file format

The first line of input file contains integers N and P, the number of jury members and the number of problems. The following N lines contain P integers in range from 0 to 1000 each - the complexity ratings.

Output file format

Output file must contain an ordered list of "very simple" problem numbers, separated by spaces. If there are no such problems, output must contain a single integer 0 (zero).

Constraints

1 ≤ N, P ≤ 100

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
4 4
1 1 1 2
5 900 21 40
10 10 9 10
3 4 3 5
3

Задача C. Числа и музыка

Автор:А. Кленин
Входной файл: input.txt   Ограничение времени:5 сек
Выходной файл: output.txt   Ограничение памяти:64 Мб

Условие

"Музыкальная" последовательность, состоящая из нулей и единиц, строится следующим образом: на первом шаге последовательность состоит из одной единицы. На каждом следующем шаге к последовательности приписывается ее инверсия, т. е. последовательность, в которой 1 заменены на 0 и наоборот.

Таким образом, на первых 5 шагах последовательность будет выглядеть так:

1

10

1001

10010110

1001011001101001

Требуется по данному числу N определить значение N-го элемента последовательности.

Формат входного файла

Во входном файле содержится целое число N.

Формат выходного файла

В выходном файле должно содержаться число 0 (нуль) либо 1.

Ограничения

1 ≤ N ≤ 1000

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
13
1

Задача D. Текст

Входной файл: text.in   Ограничение времени:2 сек
Выходной файл: text.out   Ограничение памяти:256 Мб

Условие

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

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

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

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

Формат входного файла

Первая строка входного файла содержит натуральное число k — максимально допустимая длина строки.

Вторая строка входного файла содержит текст, который необходимо вывести. Текст состоит из латинских букв, цифр, пробелов и символов "," (запятая), "." (точка), "!" (восклицательный знак) и "?" (вопросительный знак).

Формат выходного файла

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

Ограничения

1 ≤ k ≤ 100. Размер входного файла не превышает 50000 байтов.

Примеры тестов

Входной файл (text.in) Выходной файл (text.out)
1
22
This     is a sample text!
This is a sample text!
2
12
This     is a sample text!
This is a
sample text!


Задача E. Укорачивание текста

Входной файл: input.txt   Ограничение времени:2 сек
Выходной файл: output.txt   Ограничение памяти:64 Мб

Условие

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

Формат входного файла

В первой строке входного файла находятся два числа K и N, в следующих двух строках находятся соответственно образец и строка.

Формат выходного файла

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

Ограничения

1 ≤ N ≤ 1000000, 1 ≤ K ≤ 100

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
3 4
a*b
abab
2

0.037s 0.003s 15