Дана строка, состоящая из маленьких латинских букв. Ваша задача — найти длину ее самой длинной подстроки, встречающейся в строке хотя бы 2 раза. Вхождения подстрок могут перекрываться (см. пример 2).
В первой строке входных данных записана строка. Гарантируется, что строка не пуста, состоит из маленьких латинских букв, и ее длина не превосходит 100.
Выведите одно число — длину самой длинной подстроки, встречающейся в строке хотя бы 2 раза.
abcd
0
ababa
3
zzz
2
На вечеринку пришли N человек. Затем те, у кого не было знакомых среди пришедших, ушли. Затем те, у кого был ровно 1 знакомый среди оставшихся, тоже ушли. Затем аналогично поступали те, у кого было ровно 2, 3, ..., N - 1 знакомых среди оставшихся к моменту их ухода.
Какое наибольшее число людей могло в итоге остаться?
В первой строке входного файла содержится одно число T — количество тестов (1 ≤ T ≤ 105). В каждой из следующих T строк записано одно целое число N (1 ≤ N ≤ 105).
Для каждого теста выведите в отдельной строке одно число — наибольшее количество людей, которое могло остаться.
1
3
1
В 2N - 1 ящике лежат яблоки и апельсины. Требуется выбрать N ящиков так, что в них окажется не менее половины всех яблок и не менее половины всех апельсинов.
В первой строке входного файла содержится одно число T — количество тестов. Описание каждого теста начинается с натурального числа N — количества ящиков. Далее в каждой из следующих 2N - 1 строке записаны числа ai и oi — количество яблок и апельсинов в i-ом ящике (0 ≤ ai, oi ≤ 109). Сумма N по всем тестам во входных данных не превышает 105. Все числа во входных данных целые.
Для каждого теста выведите две строки. В первой строке выведите YES, если возможно выбрать N ящиков, или NO — в противном случае. В случае положительного ответа во второй строке выведите N чисел — номера выбранных ящиков. Ящики нумеруются с 1 в том порядке, в котором они заданы во входных данных. Иначе оставьте вторую строку пустой. Разделяйте числа одним пробелом.
2
2
10 15
5 7
20 18
1
0 0
YES
1 3
YES
1
Даны середины трёх равных сторон строго выпуклого четырёхугольника. Требуется восстановить исходный четырёхугольник.
В первой строке входного файла содержится одно число T — количество тестов (1 ≤ T ≤ 5· 104). В каждой из следующих T строк записаны числа x1, y1, x2, y2, x3, y3 — координаты различных точек, являющихся серединами трёх равных сторон (целые неотрицательные числа, не превосходящие 10).
Для каждого теста выведите две строки. Если искомый четырёхугольник существует, выведите в первой строке YES, а во второй — четыре пары чисел — координаты вершин многоугольника в порядке обхода. Не забудьте, что четырёхугольник должен быть строго выпуклым, т. е. никакие 3 его точки не должны лежать на одной прямой. Числа выводите с 9 знаками после точки.
Если искомый четырёхугольник не существует, в первой строке выведите NO, а вторую строку оставьте пустой.
3
1 1 2 2 3 3
0 1 1 0 2 2
9 3 7 9 9 8
NO
YES
3.5 1.5 0.5 2.5 -0.5 -0.5 2.5 0.5
NO
Недавно Вася придумал новую игру с деревом (напоминаем, что дерево — это связный граф без циклов): он удаляет любое (возможно, нулевое) количество ребер данного дерева, и подсчитывает произведение размеров получившихся компонент связности. Ваша задача — для заданного дерева определить, какое наибольшее число сможет получить Вася в своей новой игре.
В первой строке содержится целое число n (1 ≤ n ≤ 700) — число вершин в дереве. Далее в n - 1 строках записаны ребра дерева. Каждая строка содержит пару номеров вершин, соединенных ребром, ai, bi (1 ≤ ai, bi ≤ n). Гарантируется, описанный во входных данных граф является деревом.
Выведите единственное число — какое наибольшее произведение размеров компонент связности можно получить, удалив из дерева некоторые ребра.
5
1 2
2 3
3 4
4 5
6
8
1 2
1 3
2 4
2 5
3 6
3 7
6 8
18
3
1 2
1 3
3