Темы --> Информатика --> Алгоритмы
    Задачи на моделирование(78 задач)
    Арифметические алгоритмы(240 задач)
    Алгоритмы поиска(155 задач)
    Алгоритмы сортировки(194 задач)
    Динамическое программирование(355 задач)
    Алгоритмы на графах(319 задач)
    Перебор(154 задач)
    Игры и выигрышные стратегии(33 задач)
    Вычислительная геометрия(216 задач)
    Эвристические методы(30 задач)
    Алгоритмы на строках(45 задач)
    Пересечение множеств(10 задач)
    Жадный алгоритм(71 задач)
    Теория расписаний(5 задач)
    Обработка текста(31 задач)
    Дата и время(14 задач)
---> 1657 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 283 284 285 286 287 288 289 >> Отображать по:
#111774
Суффиксы
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Назовём строкой последовательность из маленьких букв латинского алфавита. Строкой, например, является пустая последовательность, слово «aabaf» или бесконечная последовательность букв «a».

i-ый суффикс Si строки S — это строка S, из которой вырезаны первые i букв; так, для строки S = aabaf суффиксы будут такими:

  1. S0 = aabaf
  2. S1 = abaf
  3. S2 = baf
  4. S3 = af
  5. S4 = f
  6. S5 = S6 = S7 = ... = «»

Суффиксы определены для всех i \(\ge\) 0.

Циклическое расширение S *  конечной строки S — это строка, полученная приписыванием её к самой себе бесконечное количество раз. Так,

  1. S *  = S * 0 = aabafaabafaabafaa...
  2. S * 1 = abafabafabafabaf...
  3. S * 2 = bafbafbafbafbafb...
  4. S * 3 = afafafafafafafaf...
  5. S * 4 = ffffffffffffffff...
  6. S * 5 = S * 6 = S * 7 = ... = ""

По заданной строке S выясните, сколько её суффиксов Si имеют такоей же циклическое расширениe, как и строка S, то есть количество таких i, что S *  = S * i.

Входные данные

В первой и единственной строке входного файла задана строка S, состоящая из не менее, чем одной, и не более, чем 100000 маленьких латинских букв 'a'-'z'.

Выходные данные

Выведите в первую строку выходного файла одно число — количество суффиксов строки S, имеющих такое же циклическое расширение, как и она сама.

Примеры
Входные данные
aa
Выходные данные
2
Входные данные
ab
Выходные данные
1
Входные данные
qqqq
Выходные данные
4
Входные данные
xyzzyxy
Выходные данные
1
#111776
Платные дороги
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Мэр одного большого города решил ввести плату за проезд по шоссе, проходящим в районе города, чтобы снизить объем транзитного транспорта. В районе города проходит n шоссе.

Но руководство области, в которой расположен город, воспротивилось планам мэра. Действительно – дальнобойщики представляют собой неплохой источник доходов для большого количества кафе и гостиниц в небольших городках.

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

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

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

Входные данные

Первая строка входного файла содержит два целых числа: n и m – количество шоссе и количество станций метро, соответственно (1 ≤ n, m ≤ 100 000).

Следующие n строк описывают шоссе. Каждое шоссе описывается тремя целыми числами a, b и c и представляет собой прямую на плоскости, задаваемую уравнением a×x+b×y+c = 0 (|a|, |b|, |c| ≤ 106). Следующие m строк входного файла описывают станции метро. Каждая станция описывается двумя целыми числами x и y и представляет собой точку на плоскости с координатами (x, y) (|x|, |y| ≤ 106).

Выходные данные

Первая строка выходного файла должна содержать одно целое число – количество шоссе, которые проходят через город. Вторая строка должна содержать номера этих шоссе в возрастающем порядке. Шоссе нумеруются от 1 до n в порядке, в котором они описаны во входном файле.

Система оценки

Система тестов состоит из двух групп:

В тестах первой группы выполняется ограничение \(n \le 10^4\). За прохождение этой группы ставится 50 баллов.

В тестах второй группы дополнительных ограничений нет. За прохождение этой группы ставится также 50 баллов.

Примеры
Входные данные
4 2
0 1 0
1 0 1
1 1 0
1 1 -1
0 0
2 0
Выходные данные
3
1 3 4
#111777
Число возрастающих подпоследовательностей
  
ограничение по времени на тест
0.5 second;
ограничение по памяти на тест
64 megabytes

Задана последовательность из n чисел a1, a2, ..., an. Подпоследовательностью длины k этой последовательности называется набор индексов i1, i2, ..., ik, удовлетворяющий неравенствам 1 ≤ i1 < i2 < ... < ik ≤ n. Подпоследовательность называется возрастающей, если выполняются неравенства ai1 < ai2 < ... < aik.

Необходимо найти число возрастающих подпоследовательностей наибольшей длины заданной последовательности a1, ... ,an. Так как это число может быть достаточно большим, необходимо найти остаток от его деления на 109 + 7.

Входные данные

Первая строка входного файла содержит целое число n (1 ≤ n ≤ 105). Вторая строка входного файла содержит n целых чисел: a1, a2, ... ,an. Все ai не превосходят 109 по абсолютной величине.

Выходные данные

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

Примеры
Входные данные
5
1 2 3 4 5
Выходные данные
1
Входные данные
6
1 1 2 2 3 3
Выходные данные
8
#111780
Машинки
  
ограничение по времени на тест
0.25 second;
ограничение по памяти на тест
64 megabytes

Лена играет в машинки. Для этого она вырезала из бумаги машинку (являющуюся многоугольником без самопересечений и самокасаний) и стала возить её по столу. К сожалению, во время игры она разлила чай и на столе образовалась река. Для того, чтобы продолжить игру, Лене нужно провезти машинку через реку. Для этого она решила построить мост — длинную ленту, по которой и поедет машинка. На столе машинку можно поворачивать на любой угол, но для того, чтобы проехать через реку, её границы не должны выходить за границы моста. Ниже расположена фотография игрового поля и предполагаемое решение проблемы. Лене стало интересно — какой минимальной ширины может быть мост, чтобы машинка смогла проехать через реку?




Внезапно Лена задумалась — ведь эта игра может стать прекрасной задачей по информатике, достойной финала международной студенческой олимпиады! Её Вам и предстоит решить.

Входные данные

Первая строка входного файла содержит T (Первая группа тестов: 0 < T < 11, вторая группа тестов: T = 1) -- количество тестов во входном файле. Далее следуют T тестов. Первая строка теста содержит число N (Первая группа тестов: 3 <= N <= 100. Вторая группа: 3 <= N <= 2 * 105) — количество вершин многоугольника.

Следующие N строк содержат по два числа — xi и yi (Первая группа тестов: 0 <= xi, yi <= 1000. Вторая группа: -105 <= xi, yi <= 105), задающие координаты многоугольника в порядке обхода. Гарантируется, что он не имеет самокасаний и самопересечений.

Выходные данные

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

Примеры
Входные данные
2
3
0 0
3 0
0 4
4
0 10
10 0
20 10
10 20
Выходные данные
2.4000
14.1422
#111787
Наибольший квадрат
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Дан двумерный массив целых чисел n × m, все элементы которого — нули или единицы. Найти в нём наибольший по площади квадрат, состоящий только из единиц. Гарантируется, что в нём есть хотя бы одна единица.

Входные данные

Вводятся два целых числа n и m (1 ≤ n, m ≤ 1000), а потом n строк по m чисел 0 или 1 — элементы массива.

Выходные данные

Вывести три числа — длину стороны квадрата и координаты его левого верхнего угла.

Примеры
Входные данные
1 1
1
Выходные данные
1
1 1
Входные данные
3 5
1 1 0 0 0
1 1 1 1 1
0 0 0 1 1
Выходные данные
2
1 1
Страница: << 283 284 285 286 287 288 289 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест