training_2009_04_18 - условия

Problem A. Knuth-Morris-Pratt ≡

problems
details
visible spaces
basic formulae
wide text
editor

Author:	StdAlg	Time limit:	1 sec
Input file:	input.txt	Memory limit:	256 Mb
Output file:	output.txt

Statement

You are to write a program that receives two strings and finds position where the second string appears in the first one as a substring.

Input file format

First and second lines of input file contain given strings. Each string is a sequence of lower-case Latin letters from 'a' to 'z' and spaces.

Output file format

Output file must contain a single integer — position of the first occurrence of the substring in a string, or  − 1 if there is none. Positions are numbered from 1.

Constraints

Length of each string does not exceed 100000 characters.

Sample tests

No.	Input file (`input.txt`)	Output file (`output.txt`)
1	`yezhiki nachinayut i vyygryvayut yut`	`16`

Задача B. Кубики ≡

задачи
детали
видимые пробелы
простые формулы
широкий текст
редактор

Автор:	Жюри XVIII городской олимпиады школьников Санкт-Петербурга по информатике	Ограничение времени:	1 сек
Входной файл:	input.txt	Ограничение памяти:	64 Мб
Выходной файл:	output.txt

Условие

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

Теперь Петя видит перед собой N цветных кубиков, но не знает, какие из этих кубиков настоящие, а какие - всего лишь отражение в зеркале.

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

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

Первая строка входного файла содержит число N и количество различных цветов, в которые могут быть раскрашены кубики - M. Следующая строка содержит N целых чисел от 1 до M - цвета кубиков.

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

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

Ограничения

1 ≤ N,M ≤ 100000

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

№	Входной файл (`input.txt`)	Выходной файл (`output.txt`)
1	`6 2 1 1 2 2 1 1`	`3 5 6`