Темы --> Информатика --> Алгоритмы --> Эвристические методы
---> 29 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 1 2 3 4 5 6 >> Отображать по:
ограничение по времени на тест
0.0 second;
ограничение по памяти на тест
0 megabytes
Задана последовательность команд "поворот налево" и "поворот направо". Требуется каждой команде сопоставить число шагов, чтобы путь не пересекал и не касался самого себя.

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

Программа для робота представляет собой последовательность команд. Команды робота приведены в следующей таблице:

 

Команда

Обозначение

Действия робота

Перемещение

(X)

Переместиться вперед на X километров, прокладывая за собой оросительный канал
Поворот налево L Повернуть налево на 90o
Поворот направо

R

Повернуть направо на 90o

Любая программа начинается и заканчивается командами перемещения и не содержит двух команд перемещения или двух команд поворота подряд.

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

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

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

Входные данные содержат команды поворота исходной программы в том порядке, в котором они в ней следовали. Каждая команда представляет собой символ «L» либо «R», команды друг от друга не отделяются. Количество команд не превышает 30 000.

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

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

includegraphics{pics/program.1}
Примеры
Входные данные
LLLRRR
Выходные данные
(4)L(3)L(1)L(2)R(2)R(1)R(1)
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Спонсоры олимпиады предоставили оргкомитету N призов для победителей олимпиады. Стоимости всех призов различны и выражаются натуральными числами от 1 до N

Перед оргкомитетом возникла задача распределить эти призы между K участниками так, чтобы все участники получили одинаковое количество призов, и, кроме того, суммарные стоимости призов, полученных разными участниками, совпадали.

Гарантируется, что N делится на K

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

На вход программы поступают два числа: N и K (1≤<N≤200, 1≤K≤200, K является делителем N).

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

Выведите K строк по N/K чисел в каждой. В каждое строке должны быть выведены стоимости призов, которые вручаются соответствующему участнику.

Если распределить призы требуемым образом невозможно, выведите одно число 0.

Примеры
Входные данные
8 2
Выходные данные
1 4 6 7
2 3 8 5
Входные данные
6 3
Выходные данные
1 6
3 4
5 2
ограничение по времени на тест
8.0 second;
ограничение по памяти на тест
64 megabytes

Реализуйте структуру данных типа “множество строк”. Хранимые строки  – непустые последовательности  длиной не более 10 символов, состоящие из строчных латинских букв. Структура данных должна поддерживать операции добавления строки в множество и проверки принадлежности  данной строки множеству. Максимальное количество элементов в хранимом множестве не превосходит 106.

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

Каждая строка входных данных задает одну операцию над множеством. Запись операции состоит из типа операции и следующей за ним через пробел строки, над которой проводится операция. Тип операции  – один из двух символов:   +  означает добавление данной строки в множество;  ?  означает проверку принадлежности данной строки множеству. Общее количество операций во входном файле не превосходит 106. Список операций завершается строкой, в которой записан один символ # – признак конца входных данных. При добавлении элемента в множество НЕ ГАРАНТИРУЕТСЯ, что он отсутствует в этом множестве.

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

Программа должна вывести для каждой операции типа ? одну из двух строк YES или NO, в зависимости от того, встречается ли данное слово в нашем множестве.

Примеры
Входные данные
+ hello
? hello
? bye
+ bye
? bye
#
Выходные данные
YES
NO
YES
ограничение по времени на тест
5.0 second;
ограничение по памяти на тест
256 megabytes

Реализуйте структуру данных типа “множество строк”. Хранимые строки  – непустые последовательности  длиной не более 10 символов, состоящие из строчных латинских букв. Структура данных должна поддерживать операции добавления строки в множество, удаления строки из множества и проверки принадлежности данной строки множеству. Максимальное количество элементов в хранимом множестве не превосходит 106.

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

Каждая строка входных данных задает одну операцию над множеством. Запись операции состоит из типа операции и следующей за ним через пробел строки, над которой проводится операция. Тип операции  – один из трех символов:    +  означает добавление данной строки в множество;     -  означает удаление  строки из множества;      ?  означает проверку принадлежности данной строки множеству. Общее количество операций во входном файле не превосходит 106. Список операций завершается строкой, в которой записан один символ # – признак конца входных данных. При добавлении элемента в множество НЕ ГАРАНТИРУЕТСЯ, что он отсутствует в этом множестве. При удалении элемента из множества НЕ ГАРАНТИРУЕТСЯ, что он присутствует в этом множестве.

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

Программа должна вывести для каждой операции типа ? одну из двух строк YES или NO, в зависимости от того, встречается ли данное слово в нашем множестве.

Примеры
Входные данные
+ hello
+ bye
? bye
- bye
? bye
? hello
#
Выходные данные
YES
NO
YES
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Фирма OISAC выпустила новую версию калькулятора. Этот калькулятор берет с пользователя деньги за совершаемые арифметические операции. Стоимость каждой операции в долларах равна 5% от числа, которое является результатом операции. На этом калькуляторе требуется вычислить сумму N натуральных чисел (числа известны). Нетрудно заметить, что от того, в каком порядке мы будем складывать эти числа, иногда зависит, в какую сумму денег нам обойдется вычисление суммы чисел (тем самым оказывается нарушен классический принцип “от перестановки мест слагаемых сумма не меняется”). Например, пусть нам нужно сложить числа 10, 11, 12 и 13. Тогда если мы сначала сложим 10 и 11 (это обойдется нам в 1.05 €), потом результат с 12 (1.65 €), и затем с 13 (2.3 €), то всего мы заплатим 5 €, если же сначала отдельно сложить 10 и 11 (1.05 €), потом 12 и 13 (1.25 €) и, наконец, сложить между собой два полученных числа (2.3 €), то в итоге мы заплатим лишь 4.6 €. Напишите программу, которая будет определять, за какую минимальную сумму денег можно найти сумму данных N чисел.

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

Первая строка входных данных содержит число N (2 ≤ N ≤ 105). Во второй строке заданы N натуральных чисел, каждое из которых не превосходит 10000.

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

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

Примеры
Входные данные
4
10 11 12 13
Выходные данные
4.60
Входные данные
2
1 1
Выходные данные
0.10

Страница: << 1 2 3 4 5 6 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест