Задача A. Частые подстроки ≡

Условие

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

Например, в строке "ABC ABDC ABCC A" наиболее часто встречающаяся подстрока из двух символов — "AB", а наиболее часто встречающаяся подстрока из трёх символов — "C A".

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

Рекомендуется рассмотреть частичные решения

• K = 1
• N ≤ 100

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

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

Ограничения

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

sample text
1

e

AABBBBAA
2

BB

sample
6

sample

Задача B. Канатная дорога ≡

Условие

Не так давно администрация столицы Флатландии приняла решение о строительстве канатной дороги. Этот транспорт подходит городу как нельзя лучше: столица построена на N холмах, каждый из которых при взгляде сбоку имеет вид параболы с направленными вниз ветвями. То есть i-й холм можно однозначно определить такими тремя числами A_i, B_i, C_i, что точка плоскости с координатами (x, y) находится внутри холма тогда и только тогда, когда A_i x² + B_i x + C_i ≥ y. Холмы могут пересекаться, но вершина холма никогда не находится внутри другого холма.

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

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

Рекомендуется рассмотреть частичные решения

• K = 2
• K = N

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

В первой строке входного файла находятся числа N K H, где N — количество холмов, K — число столбов и H — высота каждого из них (вещественное число). В каждой из следующих N строк содержится тройка вещественных чисел A_i B_i C_i, определяющая вид i-го холма. Холмы заданы в порядке увеличения абсциссы вершин.

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

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

Ограничения

2 ≤ N ≤ 300, 2 ≤ K ≤ N, 1 ≤ H ≤ 10⁶.

−10⁶ ≤ A_i < 0, −10⁶ ≤ B_i, C_i ≤ 10⁶.

Все вещественные числа во входном файле заданы не более чем с 5 знаками после десятичной точки.

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

3 3 1.5
-1 -5 0
-2 0 10
-1 4 0

10.831

3 2 1.5
-1 -5 0
-2 0 10
-1 4 0

-1

Задача C. Крестики-нолики ≡

Условие

Позиция в игре "крестики-нолики" определяется массивом размером 3 × 3 символа, в котором латинская буква "X" обозначает крестик, латинская буква "O" — нолик, а символ "." (ASCII 46) — свободную клетку.

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

• позиция не может возникнуть в процессе игры — "impossible",
• игра окончена, "крестики" победили — "X wins",
• игра окончена, "нолики" победили — "O wins",
• игра окончена, ничья — "tie",
• игра продолжается, ход "крестиков" — "X moves",
• игра продолжается, ход "ноликов" — "O moves".

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

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

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

...
...
...

X moves

...
.O.
...

impossible

X.O
.XO
X.O

O wins