Темы --> Информатика --> Алгоритмы
    Задачи на моделирование(78 задач)
    Арифметические алгоритмы(240 задач)
    Алгоритмы поиска(155 задач)
    Алгоритмы сортировки(194 задач)
    Динамическое программирование(355 задач)
    Алгоритмы на графах(319 задач)
    Перебор(154 задач)
    Игры и выигрышные стратегии(33 задач)
    Вычислительная геометрия(216 задач)
    Эвристические методы(30 задач)
    Алгоритмы на строках(45 задач)
    Пересечение множеств(10 задач)
    Жадный алгоритм(71 задач)
    Теория расписаний(5 задач)
    Обработка текста(31 задач)
    Дата и время(14 задач)
---> 1657 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 104 105 106 107 108 109 110 >> Отображать по:
#976
Доброе мороженое
  
#977
Добрый иероглиф
  

Когда археологи проводили раскопки в древних городах Майя, они обнаружили множество непонятных иероглифов. Пример иероглифа показан справа, он обозначает имя Кьак-у-пакал, это имя военного и религиозного лидера в древнем городе Майя Чичен-Итца (см. А.В.Восс, Г. Дж.Кремер Кьак-у-пакал, Хун-пик-токь и Коком). Этот иероглиф можно увидеть во многих местах древнего города.

Вообще говоря, иероглифы Майя не являются иероглифами в прямом смысле этого слова, а, скорее, являются композицией отдельных глифов. Все известные глифы занумерованы целыми числами от 1 до 9999. Учеными был разработан специальный язык, с помощью которого можно представлять иероглиф в виде обычного текста. Например, иероглиф Кьак-у-пакал кодируется как “((669:604).(586:(27:(534.534))))”.

Приведем формальную грамматику этого языка:

<block> ::= <glyph id>|'('<block>'.'<horizontal group>')'|'('<block>':'<vertical group>')'

<horizontal group> ::= <block>['.'<horizontal group>]

<vertical group> ::= <block>[':'<vertical group>]

Код иероглифа описывает процесс его составления. Глифы комбинируются горизонтально и вертикально (с помощью ':' и '.') в блоки, которые, в свою очередь, комбинируются во все большие и большие блоки, до тех пор, пока не будет достигнута нужная конфигурация.

Как обычно, в процессе реализации забыли о важной части — обратном восстановлении обычного текста в иероглиф. Это предстоит сделать вам.

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

Единственная строка входного файла содержит строку, описывающую иероглиф Майя в виде обычного текста. Длина строки не превышает 255 символов. Строка не содержит пробелов.

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

Выведите текст, составленный из символов '+', '-', '|', ' ' (ASCII коды 43, 45, 124, 32), '0'..'9' и переводов строки. Все блоки одной группы должны иметь одинаковый размер. Номер глифа (glyph id) с одним пробелом перед ним, должен быть помещен в левый верхний угол блока. Вывод должен быть как можно короче. Гарантируется, что для всех тестов существует изображение, содержащее максимум 100 000 байт.

Примеры
Входные данные
((669:604).(586:(27:(534.534))))
Выходные данные
+-----------+-----------+
| 669       | 586       |
|           |           |
|           |           |
+-----------+-----------+
| 604       | 27        |
|           +-----+-----+
|           | 534 | 534 |
+-----------+-----+-----+
#983
Мосты
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Одна сказочная страна располагалась в дельте далекой реки ( far away river ).

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

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

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

Первая строка входных данных содержит 4 числа n, k, sh и sc — число городов, число мостов, которым можно построить, скорость лошади и скорость экипажа в метрах в секунду (1 ≤ k < n≤ 10 000, 1 ≤sh; sc·≤ 100 000). Каждая из следующих n – 1 строк содержит три целых числа bi, ei — номера соединяемых городов и длину дороги в метрах li (1 ≤ li ≤ 106). Города пронумерованы от 1 до n, дороги пронумерованы от 1 до n – 1.

Выходные данные
k чисел — номера мостов, которые должны быть построены. Если существует несколько оптимальных планов строительства мостов, то выведите любой из них.

Примеры
Входные данные
6 2 1 2
1 2 5
3 2 6
1 4 4
4 6 4
4 5 5
Выходные данные
1
3
#984
Внутренние узлы
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Рассмотрим бесконечную клетчатую бумагу. Покрасим некоторые узлы сетки в черный цвет, а остальные будем считать белыми. Узел V< называется внутренним, если он внутренний по вертикали и внутренний по горизонтали. Узел внутренний по горизонтали, если слева и справа от V расположены по крайней мере по одному черному узлу. Узел внутренний по вертикали, если сверху и снизу от V расположены по крайней мере по одному черному узлу.

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

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

Первая строка содержит одно целое число n (0 ≤ n≤ 100 000) – количество черных узлов в начале. Каждая из следующих n строк содержит два целых числа – координаты очередного черного узла, по модулю не превосходящие 109.

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

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

Примеры
Входные данные
10
-1 0
0 5
-4 -4
4 1
1 5
-2 -3
0 -2
1 -3
0 3
0 2
Выходные данные
10
#985
Экзамены
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

Первая сессия обычно доставляет много проблем. Одна из них заключается в том, что студенту нужен по крайней мере целый день, чтобы подготовиться к одному экзамену. В день одного экзамена к другому готовиться невозможно. Но основная проблема заключается в том, что студенты могут начать готовиться к i-му экзамену, не раньше чем за ti дней до него, иначе они все забудут. Глеб хочет начать готовиться к экзаменам как можно позже, но он собирается все экзамены сдать.

Помогите Глебу выбрать день начала подготовки к экзаменам.

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

Первая строка выходных данных содержит число экзаменов n (1 ≤ n ≤ 50 000). Следующие строки описывают экзамены. Каждое описание состоит из трех строк. Первая строка – это название экзамена (строка, содержащая только латинские буквы, длиной не более 10). Вторая строка – дата экзамена в формате dd.mm.yyyy. Третья строка содержит величину ti для этого экзамена (1 ≤ ti ≤ 100 000). Все экзамены проходят от 01.01.1900 до 31.12.2100. Не забудьте, что високосными считаются годы, которые делятся на 4 и не делятся на 100 или которые делятся на 400.

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

Выведите в формате dd.mm.yyyy, когда Глеб самое позднее сможет приступить к подготовке к экзаменам. Если расписание не позволяет подготовиться к каждому из экзаменов, то выведите слово Impossible.

Примеры
Входные данные
3
Philosophy
29.06.2005
1
Algebra
30.06.2005
3
Physics
02.07.2005
10
Выходные данные
27.06.2005
Страница: << 104 105 106 107 108 109 110 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест