Страница: << 1 2 3 >> Отображать по:
#1152
Информатизация садоводства
  

Дачный участок Степана Петровича имеет форму прямоугольника размером a × b. На участке имеется n построек, причем основание каждой постройки — прямоугольник со сторонами, параллельными сторонам участка.

Вдохновленный успехами соседей, Степан Петрович хочет посадить на своем участке m видов плодовых культур (участок Степана Петровича находится в северной местности, поэтому m = 1 или m = 2). Для каждого вида растений Степан Петрович хочет выделить отдельную прямоугольную грядку со сторонами, параллельными сторонам участка. Само собой, грядки не могут занимать территорию, занятую постройками или другими грядками.

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


грядка №1



дом

сарай

грядка №2


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

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

В первой строке входного файла содержатся два целых числа n и m (0 ≤ n ≤ 10; 1 ≤ m ≤ 2).

Во второй строке содержатся два целых числа a и b (1 ≤ a, b ≤ 10000).

Далее следуют n строк, каждая из которых содержит четыре целых числа xi,1 , yi,1, xi,2, yi,2 –координаты двух противоположных углов постройки (0 xi,1 < xi,2 a, 0 yi,1 < yi,2   b). Различные постройки не могут пересекаться, но могут касаться друг друга.

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

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

В случае, если в вашем решении Степану Петровичу следует расположить менее m грядок, необходимо вывести для грядок, которые не следует сажать, строку «0 0 0 0» (см. второй пример ниже).

Примеры
Входные данные
2 2
7 5
4 2 6 4
0 1 2 2
Выходные данные
0 2 4 5
2 0 7 2
Входные данные
3 2
4 4
0 0 4 1
0 1 1 4
3 1 4 4
Выходные данные
1 1 3 4
0 0 0 0
#1340
Легкоатлетический манеж МГУ
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

В стране Флатландия решили построить легкоатлетический манеж с M одинаковыми прямолинейными беговыми дорожками. Они будут покрыты полосами из синтетического материала пружинкин. На складе имеются N полос пружинкина, длины которых равны 1, 2, …, N метров соответственно (i-я полоса имеет длину i метров).

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

Требуется написать программу, которая определяет, можно ли покрыть всем имеющимся материалом M дорожек, и если это возможно, то распределяет полосы пружинкина по дорожкам.

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

Во входном файле содержатся два целых числа, разделенных пробелом: M — количество дорожек и N — количество полос пружинкина (1 ≤ M ≤ 1000, 1 ≤ N ≤ 30000).

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

В случае, если распределить имеющиеся полосы пружинкина на M дорожек одинаковой длины невозможно, то в выходной файл выведите слово «NO».

В противном случае, в первую строку выведите слово «YES». В последующих M строках дайте описание использованных полос для каждой дорожки в следующем формате: сначала целое число t — количество полос на дорожке, затем t целых чисел — длины полос, которые составят эту дорожку. Если решений несколько, можно вывести любое из них.


В задаче есть группа на первые 17 тестов и она оценивается в 20 баллов. затем идёт потестовая оценка по 2 балла за пройденный тест.

Примеры входных и выходных данных

Ввод

Вывод

2 4

YES

2 1 4

2 3 2

3 4

NO


#2530
ЮграНефтеТранс
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

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

Ханты-Мансийский автономный округ — Югра является важнейшим нефтяным регионом России. Добыча нефти составляет 267 млн т в год, её транспортировка осуществляется по трубопроводам, общая длина которых превышает длину экватора Земли.

Система транспортировки нефти представляет собой совокупность \(n\) распределительных станций и \(m\) трубопроводов. Каждый трубопровод соединяет две различные станции. Между любыми двумя станциями проложено не более одного трубопровода.

Эффективность работы станций существенно зависит от вязкости нефти. Поэтому компания «ЮграНефтеТранс», в ведении которой находится сеть трубопроводов, заказала инновационному исследовательскому предприятию разработку и изготовление новых сверхточных датчиков вязкости на основе самых современных технологий.

Изготовление датчиков — процесс трудоёмкий и дорогостоящий, поэтому было решено изготовить \(k\) датчиков (\(k\le40\)) и выбрать \(k\) различных станций, на которых датчики будут установлены. Необходимо осуществить выбор станций так, чтобы датчики контролировали все трубопроводы: для каждого трубопровода хотя бы один датчик должен быть установлен на станции, где начинается или заканчивается этот трубопровод.

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

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

В первой строке входного файла записаны три натуральных числа — \(n\), \(m\) и \(k\) (\(k\le n\le2000\), \(1\le m\le10^5\), \(1\le k\le40\)). Далее следуют \(m\) строк, каждая из которых описывает один трубопровод. Трубопровод задаётся двумя целыми числами — порядковыми номерами станций, которые он соединяет. Станции пронумерованы от 1 до \(n\). Гарантируется, что к любой станции подведён хотя бы один трубопровод и между любыми двумя станциями проложено не более одного трубопровода. Числа в каждой строке разделены пробелами.

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

В первую строку выходного файла выведите слово «Yes», если требуемое расположение датчиков существует, в противном случае — слово «No». В случае положительного ответа выведите во вторую строку выходного файла \(k\) различных целых чисел — номера станций, на которых необходимо установить датчики. Номера можно выводить в любом порядке. Если существует несколько подходящих расположений датчиков, выведите любое из них. Разделяйте числа во второй строке пробелами.

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

Решения, корректно работающие при \(n\le100\) и \(k\le10\), будут оцениваться из 60 баллов.

Примеры
Входные данные
9 12 4
1 2
2 3
1 4
4 5
1 6
6 7
1 8
8 9
2 5
4 7
6 9
8 3
Выходные данные
Yes
2 4 6 8
Входные данные
8 12 4
7 4
7 5
3 1
2 8
4 3
3 2
6 1
1 2
1 4
6 5
8 6
8 7
Выходные данные
No
Входные данные
4 3 1
3 1
3 2
3 4
Выходные данные
Yes
3
#2970
Равенство
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Андрей Сергеевич — учитель математики в начальной школе. Вчера на уроке он записал на доске выражение вида

a1 ? a2 ? ... ? aN - 1 ? aN = S

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

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

В первой строке содержится число N (1 ≤ N ≤ 30) — количество чисел в левой части равенства, записанного на доске и число S, записанное в правой части равенства (1 ≤ S ≤ 106). В следующей строке даны N целых чисел в том порядке, в каком они были выписаны на доске. Все числа неотрицательные и не превышают 106.

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

Выведете на экран одно число –— количество различных вариантов расстановки знаков между числами, приводящих к правильному результату в записанном на доске выражении.

Примеры
Входные данные
2 4
2 2
Выходные данные
2
Входные данные
2 46
4 6
Выходные данные
0
Входные данные
4 8
2 2 2 2
Выходные данные
5
#3143
Перевес багажа
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

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

У Пети в чемодане лежат N предметов, каждый предмет имеет свой вес Wi килограмм и ценность Ai рублей, причем оказалось так, что для любого предмета выполняется следующее неравенство:

W1 + W2 + … + Wi-1 ≤ Wi

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

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

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

В первой строке задаётся количество предметов в багаже у Пети N (1 ≤ N ≤ 50) и какой у Пети перевес чемодана в килограммах M (1 ≤ M ≤ 1018). Во второй строке задаются N целых неотрицательных чисел – вес всех вещей Wi, сумма чисел не превышает 1018. В третьей строке заданы N целых неотрицательных чисел – ценность всех вещей Ai , все числа не превышают 109.

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

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

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