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

Рассмотрим ориентированный граф G, имеющий n вершин, пронумерованных натуральными числами от 1 до n. В графе G возможно наличие нескольких дуг между одной и той же парой вершин, а также дуг, ведущих из вершины в нее саму. Каждая дуга графа помечена некоторой буквой латинского алфавита. Каждому пути в графе G можно поставить в соответствии строку, состоящую из букв, написанных на последовательно проходимых в соответствии с этим путем дугах. Эта строка называется путевой меткой пути. Назовем строку S путевой строкой графа G, если в нем существует путь, путевая метка которого равна S.

Ваша задача посчитать остаток от деления на 1 000 000 количества путевых строк графа G, состоящих ровно из L символов.

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

В первой строке входных данных записаны целые числа n, m, L (1 ≤ n  ≤ 10, 1 ≤ m ≤ 10 000, 1 ≤  L ≤ 100), равные количеству вершин и ребер графа G, а также длине путевых строк, которые нужно искать. Следующие m строк задают дуги графа G. Каждая из этих строк содержит два натуральных числа a, b (1 ≤  a, b  ≤ n) и маленькую латинскую букву c, что означает наличие дуги из вершины a в вершину b, помеченной символом c. Элементы каждой строки отделены друг от друга пробелами.

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

Единственная строка выходных данных должна содержать одно число, равное остатку от деления количества путевых строк длины L в графе G на 1 000 000.

Примеры
Входные данные
4 4 100
1 2 a
2 3 b
3 4 a
4 1 b
Выходные данные
2
#78
Прямоугольники
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Дан прямоугольник N x M, состоящий из квадратиков 1 x 1. Некоторые квадратики вырезали. Надо найти наименьшее количество прямоугольников, на которое можно разрезать оставшуюся фигуру.

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

В первой строке входных данных заданы числа N и M, (1 ≤  N, M ≤ 10). Далее следует N строк. В (i+1)-ой содержится M чисел; j-е число равно 1, если клетку на i-й строке и в j-м столбце вырезали из доски, 0 – если оставили.

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

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

Примеры
Входные данные
2 2 
0 0
1 0
Выходные данные
2
#79
Арбузная грядка
  
ограничение по времени на тест
3.0 second;
ограничение по памяти на тест
64 megabytes

Ограничение по времени:        3 секунды
Ограничение по памяти:         64 мегабайта

На этот раз Вася увлекся выращиванием арбузов. Его огород имеет форму прямоугольника \(N \times M\) метров, разделенного на одинаковые ячейки размером \(1 \times 1\) метр, в каждой из которых растет по арбузу. Как-то раз он решил  осмотреть некоторые из них, начав в левом верхнем углу, пройдясь по огороду и вернувшись обратно. Ячейки, оказавшиеся внутри цикла, считаются осмотренными, остальные – не осмотренными. По некоторым банальным соображениям Вася не ходит по грядкам, а только лишь по специальным дорожкам, расположенным на границах ячеек с арбузами. Вдобавок, он хочет, чтобы его путь получился без самопересечений. К счастью, дорожки достаточно широкие для того, чтобы гулять по ним много раз, не считая это за самопересечение (см. рисунки к примерам).

Ваша задача – узнать, за какое минимальное время Васе удастся обойти ровно i арбузов. Можно считать, что он двигается равномерно со скоростью 1 метр в секунду.

Формат входных данных 

В первой строке входных данных содержатся два числа \(N, M (1 \le N, M \le 50)\). В следующих N строках идет описание огорода. В (i + 1)-й строке содержатся M символов. Символ "I" на j-й позиции означает, что Вася хочет осмотреть арбуз, расположенный в i-й строке и j-м столбце огорода; символ " ." означает, что ему не важно, что происходит в соответствующей ячейке; символ "X" означает, что он не хочет осматривать это растение. Других символов в строке нет.

Гарантируется, что  суммарное количество символов "I" и "X" не превосходит 10, и присутствует хотя бы один символ "I".

Формат выходных данных 

Выведите ровно K чисел, разделенных пробелами, где K – количество арбузов, которые Вася хочет осмотреть (количество символов "I" во входном файле). Число номер i должно быть равно минимальному времени, за которое он успеет осмотреть ровно i арбузов, соответствующих символам "I".

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

Примеры

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

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

1 1
I             

4

2 2
XX
XI

8
Рис. 1

3 3
III
IXI
III

4 6 8 10 12 14 16 18
Рис. 2

3 3
X. I
.I.
I..

8 10 14

1 10
IIXIIXIXII

4 6 12 14 20 26 28

#80
Двоичные строки заданной длины
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

По данному числу N выведите все строки длины N из нулей и единиц в лексикографическом порядке.

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

Задано единственное число N. (натуральное, 1 ≤ N ≤ 10)

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

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

Примеры
Входные данные
2
Выходные данные
00
01
10
11
#81
Двоичные строки заданной длины в обратном порядке
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

По данному числу N выведите все строки длины N из нулей и единиц в обратном лексикографическом порядке.

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

Задано единственное число N. (1 ≤ N ≤ 10)

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

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

Примеры
Входные данные
2
Выходные данные
11
10
01
00
Страница: << 8 9 10 11 12 13 14 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест