Темы --> Информатика
    Язык программирования(952 задач)
    Алгоритмы(1657 задач)
    Структуры данных(279 задач)
    Интерактивные задачи(17 задач)
    Другое(54 задач)
---> 2656 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 192 193 194 195 196 197 198 >> Отображать по:
#1326
Максимальные подпалиндромы
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Дана непустая строка, длина которой не превышает 106. Требуется для каждой позиции  символа в строке найти длину наибольшего палиндрома с центром в этом символе. Строка состоит из букв английского алфавита, большие и маленькие буквы считаются различными. Ограничение времени - 1 секунда.

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

Одна строка длины N, 0 < N ≤ 106.

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

N чисел, разделенные пробелами.

Примеры
Входные данные
abcd
Выходные данные
1 1 1 1
Входные данные
aaaaa
Выходные данные
1 3 5 3 1
#1327
Период строки
  

Дана непустая строка s. Нужно найти такое наибольшее число k и строку t, что s совпадает со строкой t, выписанной k раз подряд.

Ограничение времени - 1 секунда.

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

Одна строка длины N, 0 < N ≤ 106, состоящая только из маленьких латинских букв.

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

Одно число - наибольшее возможное k.

Примеры
Входные данные
aaaaa
Выходные данные
5
Входные данные
abcabcabc
Выходные данные
3
Входные данные
abab
Выходные данные
2
#1329
Кладоискатель
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Кладоискателю Васе попалась карта древнего подземелья. Подземелье представляет собой лабиринт размера \(N \times M\) (\(1 \le N, M \le 100\), \(N \times M \le 100\)). Каждая клетка лабиринта либо пуста и по ней можно пройти, либо содержит стену. Из клетки можно переходить только в смежную по стене клетку (так, у каждой клетки может быть не более 4 смежных).

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

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

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

Первая строка содержит 2 числа \(N\) и \(M\), задающие размеры лабиринта. Далее следует описание лабиринта: \(N\) строк по \(M\) символов в каждой. 0 означает, что клетка свободна; 1, что в клетке находится стена. Символ * обозначает клетку с сокровищем (такая клетка в лабиринте ровно одна).

В \((N+2)\)-й строке находится число \(K\) (\(1 \le K \le N \times M\)) -- количество входов в лабиринт. Далее в \(K\) строках содержатся координаты входов. Так, в \(i\)-й строке содержатся числа \(x_i\) и \(y_i\), означающие,что \(i\)-й вход расположен в \(x_i\)-й строке и в \(y_i\)-м столбце (\(1 \le x_i \le N, 1 \le y_i \le M\)). Гарантируется, что координаты входов попарно различны, и то, что все входы расположены в пустых клетках. Ни один из входов не находится в клетке с сокровищем.

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

Необходимо вывести одно число - искомый номер входа (нумерация начинается с 1). Если до сокровища невозможно добраться, выведите -1.

Примеры
Входные данные
5 5
00000
00000
10*00
01111
00000
4
1 1
1 5
4 1
5 5
Выходные данные
1
Входные данные
3 3
010
1*1
010
4
1 1
1 3
3 1
3 3
Выходные данные
-1
#1330
Маршрут кладоискателя
  

Вася из задачи A по-прежнему занят поиском кладов. Более того, у него появились последователи. Один из таких последователей попросил Васю помочь в своих поисках. Так, по карте сокровищ Васю просят восстановить кратчайший путь до клада. Конфигурация лабиринта совпадает с конфигурацией, описанной в задаче A (поле \(N \times M\) (\(1 \le N, M \le 100\), \(N \times M \le 100\))), в одной клетке которого находится клад, в \(K\) клетках находятся входы в лабиринт).

Требуется вывести искомый путь.

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

Первая строка содержит 2 числа \(N <= 100\) и \(M <= 100\), задающие размеры лабиринта. Далее следует описание лабиринта: \(N\) строк по \(M\) символов в каждой. 0 означает, что клетка свободна; 1, что в клетке находится стена. Символ * обозначает клетку с сокровищем (такая клетка в лабиринте ровно одна).

В \((N+2)\)-й строке находится число \(K\) (\(1 \le K \le N \times M\)) -- количество входов в лабиринт. Далее в \(K\) строках содержатся координаты входов. Так, в \(i\)-й строке содержатся числа \(x_i\) и \(y_i\), означающие,что \(i\)-й вход расположен в \(x_i\)-й строке и в \(y_i\)-м столбце (\(1 \le x_i \le N, 1 \le y_i \le M\)). Гарантируется, что координаты входов попарно различны, и то, что все входы расположены в пустых клетках. Ни один из входов не находится в клетке с сокровищем.

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

В первой строке вывести одно число - длину кратчайшего маршрута. В следующих строках необходимо вывести кратчайший маршрут. Каждую клетку маршрута (включая начальную и конечную) вывести на отдельной строке в формате \(x_i\) \(y_i\), где \(x_i\) - строка клетки, а \(y_i\) - столбец клетки.

Если существует несколько путей минимальной длины, выведите любой. Если до сокровища невозможно добраться, в единственной строке выведите -1.

Примеры
Входные данные
5 5
00000
00000
10*00
01111
00000
4
1 1
1 5
4 1
5 5
Выходные данные
4
Входные данные
3 3
010
1*1
010
4
1 1
1 3
3 1
3 3
Выходные данные
-1
#1332
Транзитивное замыкание
  

Невзвешенный ориентированный граф задан своей матрицей смежности. Требуется построить его транзитивное замыкание, то есть матрицу, в которой в \(i\)-й строке и \(j\)-м столбце находится 1, если от вершины \(i\) можно добраться до вершины \(j\), и 0 - иначе.

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

В первой строке дано число \(N\) (\(1 \le N \le 100\)) - число вершин в графе. Далее задана матрица смежности графа: в \(N\) строках даны по \(N\) чисел 0 или 1 в каждой. \(i\)-е число в \(i\)-й строке всегда равно 1.

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

Необходимо вывести матрицу транзитивного замыкания графа в формате, аналогичным формату матрицы смежности.

Примеры
Входные данные
4
1 1 0 0
0 1 1 0
1 0 1 0
0 0 1 1
Выходные данные
1 1 1 0 
1 1 1 0 
1 1 1 0 
1 1 1 1
Страница: << 192 193 194 195 196 197 198 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест