Страница: << 130 131 132 133 134 135 136 >> Отображать по:
#112038
Межрегиональная олимпиада
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

На межрегиональной олимпиаде по программированию роботов соревнования проводятся в один тур и в необычном формате. Задачи участникам раздаются последовательно, а не все в самом начале тура, и каждая \(i\)-я задача (1 ≤ \(i\) ≤ \(n\)) становится доступной участникам в свой момент времени \(s_i\). При поступлении очередной задачи каждый участник должен сразу определить, будет он ее решать или нет. В случае, если он выбирает для решения эту задачу, то у него есть \(t_i\) минут на то, чтобы сдать ее решение на проверку, причем в течение этого времени он не может переключиться на решение другой задачи. Если же участник отказывается от решения этой задачи, то в будущем он не может к ней вернуться. В тот момент, когда закончилось время, отведенное на задачу, которую решает участник, он может начать решать другую задачу, ставшую доступной в этот же момент, если такая задача есть, или ждать появления другой задачи. При этом за правильное решение \(i\)-й задачи участник получает \(c_i\) баллов.

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

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

Формат входного файла

Первая строка входного файла содержит одно целое число \(n\) (1 ≤ \(n\) ≤ \(10^5\)) количество задач на олимпиаде.

Последующие \(n\) строк содержат описания задач, по три числа на каждой строке: \(s_i\) момент появления \(i\)-й задачи в минутах, \(t_i\) время, отведенное на ее решение в минутах, и \(c_i\) сколько баллов получит участник за решение этой задачи (1 ≤ \(s_i\), \(t_i\), \(c_i\) ≤ \(10^9\)).

Формат выходного файла

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

Вторая строка должна содержать одно целое число \(m\) - количество задач, которые надо решить при оптимальном выборе.

Третья строка должна содержать \(m\) разделенных пробелом целых чисел - номера этих задач в порядке их решения. Задачи пронумерованы, начиная с единицы, в порядке их описания во входном файле.

Если оптимальных ответов несколько, необходимо вывести любой из них.

Пояснения к примерам

В первом примере Артур успевает решить все задачи и получить три балла.

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

Система оценивания

Частичные правильные решения для тестов, в которых все \(c_i\) одинаковы и \(n\) ≤ 1000, оцениваются из 30 баллов.

Частичные правильные решения для тестов, в которых все \(c_i\) одинаковы, оцениваются из 50 баллов.

Частичные правильные решения для тестов, в которых \(n\) ≤ 1000, оцениваются из 50 баллов.

Примеры
Входные данные
2
1 1 1
2 2 2
Выходные данные
3
2
1 2
Входные данные
3
1 2 1
3 2 1
2 4 3
Выходные данные
3
1
3
#112039
Дом Мэра
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

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

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

Когда Мэру города М принесли на согласование план распределения территорий для больших проектов, ему стало интересно, насколько сложным будет маршрут от мэрии до его будущего дома. Мэрия находится в центре нового района, на пересечении нулевой улицы, направленной с юга на север, и нулевой улицы, направленной с востока на запад. С итоговым расположением дома Мэр еще не определился и на выбор у него есть \(k\) вариантов. Каждый из вариантов находится на пересечении \(x_i\)-ой улицы, направленной с юга на север (положительный x означает, что улица находится восточнее мэрии, отрицательный – западнее) и \(y_i\)-ой улицы, направленной с востока на запад (положительный \(y\) означает, что улица находится севернее мэрии, отрицательный южнее).

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

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

Формат входного файла

Первая строка входного файла содержит два целых числа \(n\) и \(k\) (0 ≤ \(n\) ≤ \(10^5\), 1 ≤ \(k\) ≤ 10) – количество блоков кварталов, которые по плану будут отданы большим проектам и количество вариантов расположения дома Мэра, соответственно.

Последующие \(n\) строк содержат по описанию блоков кварталов четыре целых числа \(u_1\), \(v_1\), \(u_2\), \(v_2\) (\(–10^9\) ≤ \(u_1\) < \(u_2\) ≤ \(10^9\), \(–10^9\) ≤ \(v_1\) < \(v_2\) ≤ \(10^9\)) — номера улиц, на пересечении которых расположены противоположные углы блока кварталов, отданных под застройку и закрытых для проезда.

Последующие последние \(k\) строк содержат по два целых числа \(x_i\) и \(y_i\) (|\(x_i\)| ≤ \(10^9\), |\(y_i\)| ≤ \(10^9\), \(x_i\) ≠ 0 или \(y_i\) ≠ 0) — возможные расположения дома Мэра.

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

Формат выходного файла

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

Если не существует несложный маршрут, то сообщение должно содержать слово NO на одной строке. Иначе, в первой строке должно содержаться слово YES, во второй строке – одно число \(t\) (0 ≤ \(t\) ≤ 2) количество поворотов, и в последующих \(t\) строках – описания поворотов в порядке их совершения: в каждой строке по три числа \(x\), \(y\) и \(d\) номера улиц, на которых расположен перекресток, где необходимо повернуть, и направление поворота, при этом \(d\) = –1 означает поворот налево и \(d\) = 1 – поворот направо.

Координаты перекрестков, где необходимо совершить повороты, не должны превышать \(10^9\). Если кратчайших несложных путей несколько, необходимо вывести любой из них.

Пояснения к примеру

Далее приведен рисунок для второго примера.

Система оценивания

Частичные правильные решения для тестов, в которых все координаты (\(x\), \(y\), \(u\) и \(v\)) по модулю не превышают 100, и \(n\) ≤ 50, будут оцениваться из 30 баллов.

Частичные правильные решения для тестов, в которых \(n\) ≤ 50, будут оцениваться из 60 баллов.

Примеры
Входные данные
1 2
-2 1 9 2
2 0
3 3
Выходные данные
YES
1
0 0 1
NO
Входные данные
2 1
0 2 2 4
1 0 4 2
3 3
Выходные данные
YES
2
0 2 1
3 2 -1
Входные данные
0 2
0 -1
0 1
Выходные данные
NO
YES
0
#112040
Светофоры
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

По территории компьютерного лагеря проложен маршрут для поездок на электрокарах. Поскольку на электрокаре можно добраться до ИКТ-центра, то школьник Пахом решил воспользоваться им. Следуя по маршруту, электрокар проехал с постоянной скоростью один за другим два светофора с зеленым светом. Пахому известно, что оба светофора находятся на расстоянии x метров друг от друга и переключаются абсолютно синхронно: зеленый свет горит a минут, потом включается красный свет и горит в течение b минут, после чего светофор переключается опять на зеленый свет и он горит также в течение a минут, и так далее. Переключений на желтый свет у светофоров нет. Скорость движения электрокара по маршруту не превышает 1000 м/мин. Электрокар может проехать на светофоре в тот момент, когда светофор переключается с одного света на другой.

Приехав в ИКТ-центр, Пахом заинтересовался, с какой максимальной постоянной скоростью он мог ехать на электрокаре между двумя светофорами.

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

Формат входного файла

Первая строка входного файла содержит три целых числа: \(a\), \(b\) и \(x\) (1 ≤ \(a\) ≤ 100, 1 ≤ \(b\) ≤ 100, 1 ≤ \(x\) ≤ \(10^5\)).

Формат выходного файла

Выходной файл должен содержать одно число – максимальную возможную скорость электрокара между двумя светофорами. Ответ должен отличаться от правильного не более чем на 10-9.

Система оценивания

Правильные решения для тестов, в которых ответ является целочисленным, будут оцениваться из 50 баллов.

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

Примеры
Входные данные
3 5 4000
Выходные данные
800.000000000
Входные данные
5 10 21010
Выходные данные
840.400000000
#112041
Кондиционеры
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

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

Все классы школы пронумерованы последовательно от 1 до \(n\). Известно, что для каждого класса с номером \(i\), требуется ровно один кондиционер, мощность которого больше или равна \(a_i\) ватт.

Администрации школы предоставили список из \(m\) различных моделей кондиционеров, которые можно закупить. Для каждой модели кондиционера известна его мощность и стоимость. Требуется написать программу, которая определит, за какую минимальную суммарную стоимость кондиционеров можно оснастить все классы школы.

Формат входного файла

Первая строка входного файла содержит одно целое число n (1 ≤ \(n\) ≤ 50 000) количество классов в школе.

Вторая строка содержит \(n\) целых чисел \(a_i\) (1 ≤ \(a_i\) ≤ 1000)- минимальная мощность кондиционера в ваттах, который можно установить в классе с номером \(i\).

Третья строка содержит одно целое число \(m\) (1 ≤ \(m\) ≤ 50 000) - количество предложенных моделей кондиционеров.

Далее, в каждой из \(m\) строк содержится пара целых чисел \(b_j\) и \(c_j\) (1 ≤ \(b_j\) ≤ 1000, 1 ≤ \(c_j\) ≤ 1000) мощность в ваттах \(j\)-й модели кондиционера и его цена в рублях соответственно.

Формат выходного файла

Выходной файл должен содержать одно число минимальную суммарную стоимость кондиционеров в рублях. Гарантируется, что хотя бы один корректный выбор кондиционеров существует, и во всех классах можно установить подходящий кондиционер.

Пояснения к примерам

В первом примере нужно купить один единственно возможный кондиционер за 1000 рублей.

Во втором примере оптимально будет установить в первом и втором классах кондиционеры четвертого типа, а в третьем классе – кондиционер третьего типа. Суммарная стоимость этих кондиционеров будет составлять 13 рублей (3 + 3 + 7).

Система оценивания

Частичные решения для \(n\), \(m\) ≤ 1000 будут оцениваться из 50 баллов.

Примеры
Входные данные
1
800
1
800 1000
Выходные данные
1000
Входные данные
3
1 2 3
4
1 10
1 5
10 7
2 3
Выходные данные
13
#112042
Конфеты
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

Кондитерская фабрика города П, в котором живет Петя, делает очень вкусные конфеты. Как-то раз, Петя собрался в гости к своему другу Васе, который живет в городе М. От города П до города М Петя решил доехать на поезде и взять с собой в подарок как можно больше коробок вкусных конфет.

Каждая коробка конфет имеет размеры \(a\) × \(b\) × \(c\) сантиметров, где \(a\) – длина, \(b\) – ширина и \(c\) – высота коробки. Для перевозки конфет Петя хочет использовать один большой ящик в форме прямоугольного параллелепипеда. В ящик должны быть уложены все коробки конфет. Для того чтобы не повредить их, все коробки в ящике должны сохранять исходную ориентацию и располагаться в одном направлении. Петя может использовать ящик любого размера, но по правилам железнодорожных перевозок размер ящика по сумме трех измерений не может превышать \(N\) сантиметров.

Требуется написать программу, которая по заданным числам \(N\), \(a\), \(b\) и \(с\) определяет такой размер ящика, который должен использовать Петя, чтобы в него поместилось максимальное количество коробок конфет.

Формат входного файла

Первая строка входного файла содержит разделенные пробелами четыре целых числа: \(N\), \(a\), \(b\), \(с\) (1 ≤ \(N\), \(a\), \(b\), \(c\) ≤ \(10^9\)).

Формат выходного файла

Выходной файл должен содержать три числа – длину, ширину и высоту ящика, который должен выбрать Петя и в который поместится максимальное количество коробок конфет. Если подходящих ответов несколько, необходимо вывести любой.

Пояснения к примерам

В первом примере выгоднее всего взять ящик размером 3 × 4 × 3 сантиметров, в который поместится три коробки конфет в длину, две коробки конфет в ширину и одна коробка конфет в высоту.

Во втором примере для того, чтобы разместить хотя бы две коробки конфет, нужен ящик размером хотя бы 8 × 3 × 4, у которого сумма измерений равна 15. В подходящий ящик поместится максимум одна коробка конфет. Подходящим также является ящик размером 9 × 3 × 2, хотя он и не является минимальным.

Система оценивания

Частичные правильные решения для тестов, в которых \(N\) ≤ 1000, будут оцениваться из 30 баллов.

Частичные правильные решения для тестов, в которых \(N\) ≤ 100 000, будут оцениваться из 60 баллов.

Примеры
Входные данные
10 1 2 3
Выходные данные
3 4 3
Входные данные
14 8 3 2
Выходные данные
8 3 2
Страница: << 130 131 132 133 134 135 136 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест