Темы --> Информатика --> Алгоритмы
    Задачи на моделирование(78 задач)
    Арифметические алгоритмы(240 задач)
    Алгоритмы поиска(155 задач)
    Алгоритмы сортировки(194 задач)
    Динамическое программирование(355 задач)
    Алгоритмы на графах(319 задач)
    Перебор(154 задач)
    Игры и выигрышные стратегии(33 задач)
    Вычислительная геометрия(216 задач)
    Эвристические методы(30 задач)
    Алгоритмы на строках(45 задач)
    Пересечение множеств(10 задач)
    Жадный алгоритм(71 задач)
    Теория расписаний(5 задач)
    Обработка текста(31 задач)
    Дата и время(14 задач)
---> 1657 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 116 117 118 119 120 121 122 >> Отображать по:
#1095
Арифметическое выражение
  
Источники: [ Личные олимпиады, Олимпиады сайта, 2009, Задача P ]

Дано выражение, содержащее натуральные числа и знаки сложения (+) и умножения (*).

Расставьте скобки так, чтобы значение этого выражения была наибольшим возможным.

Гарантируется, что максимальное значение выражения не превосходит 10000.

 

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

Вводится одна строка длиной не более 100 символов.

 

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

Выведите ту же строку с расставлеными скобками.

 

Примеры

 

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

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

2+2*3*4

(2+2)*3*4

2+2*3*4

(2+2)*(3*4)

2+2*3*4

((2+2)*3)*4

1+1

1+1

1+1

(1)+1

 

#1099
Скидки
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

В супермаркете проводится беспрецедентная акция – «Покупая два любых товара, третий получаешь бесплатно*», а внизу мелким шрифтом приписано «* - из трех выбранных вами товаров оплачиваются два наиболее дорогих».

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

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

Во входном файле задано сначала число N (1≤N≤1000), а затем N чисел – стоимости выбранных Васей товаров. Все стоимости – натуральные числа, не превышающие 10000.

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

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

Комментарии к примерам тестов

1. Вася сначала пройдет через кассу с товарами стоимостью 1, 3 и 4 – заплатит 7 рублей и товар стоимостью 1 получит в подарок, а затем снова зайдет в супермаркет и купит товары стоимостью 5 и 7, еще один товар стоимостью 5 получив в подарок.

2. Вася в первый заход в супермаркет купит товары стоимостью 15 и 25 рублей, в качестве подарка взяв товар стоимостью 8 рублей. А во второй заход в супермаркет купит товары стоимостью 3 и 8, не взяв никакого подарка.

Примеры
Входные данные
6
1 5 4 3 5 7
Выходные данные
19
Входные данные
5
3 15 25 8 8
Выходные данные
51
#1100
Муха
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Муха летит вдоль прямой. Если нанести на эту прямую координаты, то можно сказать, что в 0-й момент времени муха пролетает точку с координатой 0 и летит в положительном направлении со скоростью V. Муха может менять свою скорость, однако ускорение мухи не может по модулю превышать величины A, в частности, муха не может мгновенно остановиться. Максимальная скорость мухи не может превышать по модулю величины W.

Известно, что в момент времени T по прямой ударит мухобойка, которая полностью накроет отрезок от точки C до точки D. Если муха в этот момент окажется на этом отрезке, она погибнет.

Напишите программу, которая определит, есть ли у мухи шанс спастись, и если есть, то выведет, что должна муха для этого делать.

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

Во входном файле заданы числа V, W, A, T, C, D. Все числа целые. 0≤V≤W≤1000, 0≤A≤1000, 0<T≤1000, –1000000≤C≤D≤1000000.

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

Если муха может спастись, выведите, как она должна для этого лететь. Для этого выведите последовательность команд для мухи. Количество команд не должно превышать 100. Каждая команда задается двумя числами Ti, Ai, которые обозначают, что в течение времени Ti муха должна лететь с ускорением Ai. Ti и Ai не обязаны быть целыми, Ti должны быть положительны (не могут быть равны 0), сумма всех Ti должна быть равна T с точностью до 10-6.

Если, в рамках указанных ограничений, муха спастись не сможет, в выходной файл выведите одно число ­–1 (минус 1).

Примечания

Муха может сначала снизить скорость до 0, а затем полететь в обратную сторону (см. примеры).

Если в момент времени T муха окажется на концах отрезка, т.е. в точке C или D, она все равно погибнет.

Комментарии к примерам тестов

1. Муха не сможет спастись.

2. Сначала в течение времени 0.2 муха летит с постоянной скоростью 10, а затем ускоряется с ускорением 4

3. Муха сначала тормозит с ускорением -5, а затем с этим же ускорением начинает лететь в обратную сторону. Набрав скорость 10, муха продолжает лететь с ней без ускорения.

Примеры
Входные данные
10 10 5
1 -100 100
Выходные данные
-1
Входные данные
10 20 5
1 9 11
Выходные данные
1 5
Входные данные
10 10 5
5 0 1000
Выходные данные
4.000000000000000000 -5
1.000000000000000000 0
#1102
Найдите прямую
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

На плоскости дано N горизонтальных отрезков. Будем говорить, что прямая пересекает отрезок, если у этой прямой и этого отрезка есть хотя бы одна общая точка (в том числе прямая пересекает отрезок, если она проходит через один из его концов). Требуется найти прямую, пересекающую все отрезки, или установить, что такой нет.>

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

В первой строке входного файла находится единственное число N. В каждой из следующих N строк содержатся по три целых числа Pi, Qi, Ri, описывающих отрезки: соответствующий отрезок соединяет точки (Pi, Ri) и (Qi, Ri). Никакие два отрезка не лежат на одной прямой.

1≤N≤10000, Pi<Qi, все числа по модулю не превосходят 10000.

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

В случае, если искомая прямая существует, выведите в выходной файл коэффициенты ее уравнения (будем задавать прямую уравнением вида A∙x+B∙y+C=0, где x, y – координаты точек прямой, A, B, C – такие коэффициенты, что указанному уравнению удовлетворяют все точки прямой, и только они; соответственно, чтобы задать прямую, нужно задать три числа – A, B, C).

Коэффициенты уравнения должны быть целыми и не должны превосходить по модулю 109 (гарантируется, что при наличии решения такие A, B, C существуют).

Если прямой не существует, выведите в выходной файл сообщение “No solution” (без кавычек).

Примеры
Входные данные
3
0 1 0
0 1 1
0 1 2
Выходные данные
1 0 0
Входные данные
5
0 2 0
2 4 1
1 3 2
1 3 -1
1 3 -2
Выходные данные
3 -1 -5
Входные данные
3
0 1 0
1 2 1
-2 -1 2
Выходные данные
No solution
#1105
Игра с обменами
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Вася и Петя играют в увлекательную игру. Вася выписал подряд числа от 1 до N. А Петя выписал P пар чисел (Ai, Bi).

Теперь Вася преобразует имеющуюся последовательность чисел - он меняет местами числа в этой последовательности. Если некоторая пара чисел (Ai, Bi) выписана Петей, то Вася имеет право в любой момент взять числа из последовательности, стоящие на местах Ai и Bi и поменять их местами.

Например, если N=5. Тогда изначально Васей выписана последовательность

1 2 3 4 5

Пусть Петя написал две пары чисел: (1,2) и (2,5). Тогда Вася в любой момент может менять числа, стоящие на 1 и 2 местах, или же числа, стоящие на 2 и 5 местах.

Например, он может последовательно получить следующие последовательности:

2 1 3 4 5 (поменяв числа на 1 и 2 местах)

2 5 3 4 1 (поменяв числа на 2 и 5 местах)

5 2 3 4 1 (поменяв числа на 1 и 2 местах).

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

От Пети требуется проверить, мог ли Вася получить такую последовательность не нарушая правил игры, и если мог, то указать, в результате какой последовательности обменов (при этом не требуется, чтобы число обменов было минимально возможным).

Напишите программу, которая поможет Пете справиться с этой задачей.

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

Сначала записано число N (1≤N≤100) – количество чисел в последовательности. Дальше идет N чисел – последовательность, полученная Васей (в последовательности каждое из чисел от 1 до N встречается ровно один раз).

Далее идет число P (0≤P≤10000) – количество пар чисел, выписанных Петей. Далее записано P пар чисел (каждое число пары – из диапазона от 1 до N).

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

В первую строку выходного файла выведите сообщение YES (если такая последовательность могла быть честно получена Васей) и NO (если такую последовательность Вася не мог получить, не нарушая правил игры).

В случае, если такая последовательность могла быть получена, далее выведите способ ее получения (если вариантов несколько, выведите любой из них). Сначала выведите число K – количество операций обмена (оно не должно превышать 100000), а затем K пар чисел, задающих номера мест, на которых стоят обмениваемые элементы (числа в паре могут быть выданы в любом порядке). Гарантируется, что если решение существует, то существует решение с числом обменов, не превышающим 100000.

Примеры
Входные данные
5
5 2 3 4 1
2
1 2
2 5
Выходные данные
YES
3
1 2
2 5
1 2
Входные данные
5
2 3 4 5 1
2
1 2
2 5
Выходные данные
NO
Страница: << 116 117 118 119 120 121 122 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест