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

У Андрюши есть маленькая сестричка Аня. Она любит писать сообщения своему другу Гоше. Она хочет, чтобы никто не мог прочитать ее сообщения, поэтому она шифрует их подстановочным шифром. Подстановочный шифр заменяет каждый символ в сообщении на какой-либо еще, при этом равные символы заменяются на равные, а различные — на различные. Например, при шифровании с помощью подстановочного шифра e – a, l – b, o – w, v - c слово "love" оказывается зашифровано как "bwca".

Андрюша недавно перехватил одно из Аниных сообщений t и хочет выяснить, встречается ли там текст р. А именно, он хочет найти все позиции i, такие что существует подстановочный шифр, такой что t[i..i+|р| — 1] представляет собой зашифрованную версию р. Будем называть такие позиции потенциальными вхождениями р в t.

Помогите Андрюше найти все потенциальные вхождения р в i.

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

Первая строка входного файла содержит t. Вторая строка входного файла содержит р. Каждая строка состоит из символов с ASCII кодами от 33 до 126. Длина р не превышает длины t. Длина t не превышает 200 000. Обе строки непусты.

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

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

Примечание

За тесты в которых \(t \le 1000\) начисляется 50% баллов. За остальные тесты тоже 50%. Баллы начисляются только при прохождении всех тестов группы.

Примеры
Входные данные
abacabadabacaba
aba
Выходные данные
7
1 3 5 7 9 11 13
Входные данные
abacabadabacaba
love
Выходные данные
0
#3371
Автостоянка
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Автостоянка в Цветочном городе представляет собой прямоугольник \(N\times M\) клеток, в каждую из которых можно поставить машину. Стоянка обнесена забором, одна из сторон угловой клетки удалена (это ворота). Машина ездит по дорожке шириной в одну клетку. Незнайку попросили разместить как можно больше машин на стоянке таким образом, чтобы любая машина могла выехать, когда все прочие стоят. Например, на рисунке справа показано, как можно расположить 24 машины на стоянке размером \(7\times 7\). Помогите Незнайке решить эту задачу.

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

Во входном файле записано два натуральных числа N и M, не превосходящие 7.

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

Выведите в выходной файл единственное число: максимальное количество машинок, которое можно расставить на стоянке данного размера.

Примеры
Входные данные
1 3
Выходные данные
1
Входные данные
2 2
Выходные данные
2
#3372
Жадная волна
  
ограничение по времени на тест
0.2 second;
ограничение по памяти на тест
64 megabytes

Поле размером \(N\times M\) клеток заполнено целыми числами. Требуется найти на поле клетку, из которой волна, запущенная не более чем на \(K\) итераций, покроет площадь с максимальной суммой расположенных на ней чисел.
Пример распространения волны для поля размером \(5\times 4\). Волна запущена из клетки (3, 3) и была остановлена после трех итераций. Белые клетки – клетки, не покрытые волной, серые и черные – клетки, покрытые волной. Клетки, покрытые волной на последней итерации, отмечены серым цветом.

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

В первой строке входного файла содержатся три целых числа через пробел \(N\), \(M\) и \(K\) (\(1 \leq N, M \leq 100\), \(1 \leq K \leq N + M\)). Следующие \(N\) строк содержат по \(M\) чисел, каждое из которых не превосходит \(10000\) по абсолютной величине.

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

Выведите четыре числа \(R\), \(C\), \(P\) и \(S\), где \(R\) – номер строки, \(C\) – номер столбца, из которых следует запустить волну, \(P\) – количество итераций распространения волны, \(S\) – максимальная сумма чисел, покрытых волной. Если существует несколько вариантов ответа, то вывести любой, в котором число \(P\) минимально. \(1 \leq P \leq K\).

Оценка

Решение, верно работающее при \(N, M \leq 15\) будет получать 50 баллов. Эти баллы выставляются при прохождении всех тестов группы. В оставшихся тестах \(N, M \leq 100\), эта группа оценивается при прохождении всех тестов группы.

Примеры
Входные данные
5   4   3
1   2   3   4
1   6   7   8
9  10  11  12 
0   0   0   0
2   0   0   1
Выходные данные
3  3  3  66
#3373
Печатная схема
  
ограничение по времени на тест
0.1 second;
ограничение по памяти на тест
64 megabytes

Печатной схемой называется плоская поверхность содержащей узлы и перемычки, соединяющие пары узлов. Мы будем рассматривать печатные схемы специального вида, где все узлы расположены в узлах прямоугольной сетки, а перемычки (вертикальные или горизонтальные) соединяют пары соседних узлов. Печатная схема называется связной, если любые два узла соединены друг с другом последовательностью перемычек. На вход дается печатная схема, где некоторые соседние узлы уже соединены перемычками. К ней необходимо добавить некоторое количество перемычек таким образом, чтобы схема стала связной. Стоимость вертикальной перемычки – 1, а горизонтальной – 2.
Ваша программа должна по начальной печатной схеме определить количество добавляемых перемычек, минимальную стоимость такого добавления, а также вывести сами добавляемые перемычки.

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

Первая строка входного файла содержит два натуральных числа \(N\) и \(M\) – количество строк (\(1 \leq N \leq 100\)) и количество столбцов (\(1 \leq M \leq 100\)) соответственно. Каждый узел определяется своими координатами, нумерация начинается с верхнего левого угла (координаты (\(1\), \(1\))). Далее дается описание решетки в виде \(N\) строк по \(M\) чисел. Каждое число обозначает связь узла (\(i\), \(j\)) с узлами (\(i+1\), \(j\)) и (\(i\), \(j+1\)) в следующем формате: \(0\) – узел (\(i\), \(j\)) не соединен ни с одним из узлов (\(i+1\), \(j\)) и (\(i\), \(j+1\)). \(1\) – узел (\(i\), \(j\)) соединен только с узлом (\(i+1\), \(j\)) \(2\) – узел (\(i\), \(j\)) соединен только с узлом (\(i\), \(j+1\)) \(3\) – узел (\(i\), \(j\)) соединен и с узлом (\(i+1\), \(j\)), и с узлом (\(i\), \(j+1\)).

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

Первая строка должна содержать два числа \(K\) и \(V\) – количество добавленных перемычек и стоимость добавления соответственно. Каждая из следующих \(K\) строк должна содержать описание добавленной перемычки в формате \(i\), \(j\), \(d\), где (\(i\), \(j\)) – координаты начального узла, а \(d\) может принимать значения \(1\) или \(2\). \(d = 1\) обозначает, что соединены узлы (\(i\), \(j\)) и (\(i+1\), \(j\)), \(d = 2\) – узлы (\(i\), \(j\)) и (\(i\), \(j+1\)). Если решений несколько – выведите любое из них.

Примеры
Входные данные
4 5
2 1 1 2 1
0 3 0 1 0
3 0 0 3 1
0 2 0 2 0
Выходные данные
5 6
1 1 1
2 3 1
3 3 1
4 3 2
2 5 1
#3374
Последовательность
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Известны первые \(k\) членов последовательности – \(a_1, a_2, \dots, a_k\) (\(0 \leq a_i \leq 9\), где \(i = 1, 2, \dots, k\)). Другие члены последовательности вычисляются по следующему правилу: \(a_i = \sum_{j=i-k}^{i-1}a_j\), то есть каждый следующий член равен сумме \(k\) предыдущих. Необходимо найти последние \(r\) цифр числа \(a_n\).

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

В первой строке входного файла находятся \(3\) целых числа – \(k\), \(n\) и \(r\) (\(1 \leq k \leq 20\), \(1 \leq n \leq 10^{18}\), \(1 \leq r \leq 9\)). В следующей строке находится \(k\) чисел – \(a_1, a_2, \dots, a_k\).

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

Первой строкой выходного файла выведите \(r\) цифр числа \(a_n\). Ведущие нули следует опустить.

Примечание

1. Тесты, в которых \(r = 1\), будут оцениваться 75 баллами:
1.1 Тесты, в которых \(n<10^6\), будут оцениваться 25 баллами.
1.2 Тесты, в которых \(n \geq 10^6\), будут оцениваться 50 баллами:
1.2.1 Тесты, в которых \(k < 7\), будут оцениваться 30 баллами.
1.2.2 Тесты, в которых \(6 < k < 11\), будут оцениваться 20 баллами.
2. Тесты, в которых \(r > 1\), будут оцениваться 25 баллами.

Примеры
Входные данные
2 5 1
1 2
Выходные данные
8
Входные данные
1 100001 1
5
Выходные данные
5
Страница: << 227 228 229 230 231 232 233 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест