Страница: << 56 57 58 59 60 61 62 >> Отображать по:
#1771
Свечки
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes
На круглом торте расположены свечки, заданные двумя координатами. Разрезы торта заданы уравнениями прямых. Требуется определить, есть ли на каком-либо кусочке торта более одной свечки.

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

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

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

Первая строка входного файла содержит целые числа \(n\), \(m\) и \(r\) (1 ≤ \(n\) ≤ 10000, 0 ≤ \(m\) ≤ 1000, 1 ≤ \(r\) ≤ 2000).

Следующие n строк содержат пары целых чисел \(x_i\), \(y_i\) – координаты точек, где расположены свечки. Гарантируется, что эти точки лежат внутри круга, размерами свечек следует пренебречь. Никакие две свечки не совпадают.

Последние \(m\) строк содержат описание разрезов – тройки целых чисел \(a_i\), \(b_i\), \(c_i\). Такая тройка соответствует разрезу, который задается уравнением \(a_i\) \(x\) + \(b_i\) \(y\) + \(c_i\) = 0. Ни один разрез не проходит через свечку. Никакие два разреза не совпадают. Числа ai, bi, ci не превышают 10000 по модулю.

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

Если одному из гостей досталось более одной свечки, выведите в выходной файл слово «YES», иначе выведите слово «NO».

Примеры
Входные данные
3 2 3
2 2
1 -1
-2 0
2 -1 0
0 1 -1
Выходные данные
NO
Входные данные
3 2 3
2 2
1 -1
-2 0
1 1 -1
0 1 -1
Выходные данные
YES
Входные данные
4 2 10
1 1
1 -1
-1 1
-1 -1
0 1 0
1 0 0
Выходные данные
NO
#1772
N-угольники
  
Требуется найти множество чисел, не превосходящих K, такое, что из этих отрезков с такими длинами нельзя было составить невырожденный N-угольник.

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

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

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

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

Входной файл содержит два целых числа: \(n\) – количество вершин в запрещенных многоугольниках и \(k\) – максимальную длину отрезков (3 ≤ \(n\) ≤ 10, 1 ≤ \(k\) ≤ \(10^8\)).

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

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

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

Примеры
Входные данные
3 7
Выходные данные
5
1 1 2 3 5
#1773
Нефть
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes
Задан набор стран, продающих нефть. Для каждой страны известна стоимость барреля в долларах и в евро. Страна может продавать только за доллары или только за евро. По известному количеству имеющихся долларов и евро требуется определить максимальное количество баррелей нефти, которое можно купить.

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

Исследование внешнего рынка показало, что в мире есть \(n\) стран, экспортирующих нефть. При этом \(i\)-е государство продает баррель нефти либо за \(a_i\) долларов, либо за \(b_i\) евро.

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

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

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

На первой строке входного файла записаны три целых числа: \(n\), \(a\) и \(b\) (1 ≤ \(n\) ≤ 100, 0 ≤ \(a\), \(b\) ≤ 1000). В последующих \(n\) cтроках содержатся пары чисел \(a_i\), \(b_i\) (1 ≤ \(a_i\), \(b_i\) ≤ 1000).

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

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

Примеры
Входные данные
3 2 5
6 4
3 5
8 7
Выходные данные
 1.91666666666667E+0000
Входные данные
4 3 2
2 4
3 2
4 1
3 3
Выходные данные
 3.50000000000000E+0000
#1774
Перестановки
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Саша и Федя играют в интересную игру. У них есть \(n\) кубиков, на которых написаны различные числа от 1 до \(n\). Ребята нарисовали на бумаге \(n\) клеточек в ряд и играют по следующим правилам.

Сначала первый игрок выставляет некоторые кубики на клеточки, затем второй игрок выставляет на свободные клетки оставшиеся кубики. После этого первый игрок делает следующие действия: он смотрит, какое число написано на последнем кубике (пусть это число a) и после этого переставляет последние a кубиков в обратном порядке. Эти действия первый игрок повторяет до тех пор, пока последним не станет кубик с числом 1.

Например, пусть у ребят пять кубиков. Если первый игрок поставил второй и третий кубик на третье и пятое место: «..3.2», то второй игрок может расставить оставшиеся кубики так: «41352». В этом случае первому игроку потребуется сделать пять действий: «41325», «52314», «54132», «54123», «54321», после чего игра закончится.

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

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

Во входном файле содержится число \(n\) (1 ≤ \(n\) ≤ 25). Следующие \(n\) чисел задают расположение кубиков после хода Саши. Число 0 означает, что клетка свободна, число от 1 до \(n\) – номер кубика, который стоит в этой клетке. Во входном файле не более 10 нулей.

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

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

На второй строке выведите \(n\) чисел от 1 до \(n\), где \(i\)-е число означает номер кубика, стоящего в \(i\)-ой клетке после хода Феди. Если оптимальных решений несколько, выведите любое.

Примеры
Входные данные
3
0 0 0
Выходные данные
2
2 1 3
Входные данные
4
0 0 0 0
Выходные данные
4
2 4 1 3
#1775
Непростая задача
  

Дана прямоугольная таблица, состоящая из \(m\) строк и \(n\) столбцов. На пересечении \(i\)-й строки и \(j\)-го столбца записано целое число \(a_{ij}\). Требуется найти такие четыре различные ячейки таблицы, чтобы их центры были вершинами прямоугольника со сторонами, параллельными сторонам таблицы, а сумма чисел, записанных в этих ячейках, была максимальна.

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

На первой строке записаны два натуральных числа \(m\) и \(n\) (2 ≤ \(m\), \(n\) ≤ 500). Далее следует описание таблицы – \(m\) строк, каждая из которых содержит по \(n\) целых чисел (-\(10^7\) ≤ \(a_{ij}\) ≤ \(10^7\)).

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

На первой строке выходного файла выведите целое число \(r\) – максимальную сумму выбранных элементов, на второй строке выведите 4 натуральных числа \(x_1\), \(y_1\), \(x_2\), \(y_2\) – координаты левой верхней и правой нижней из выбранных ячеек, соответственно (1 ≤ \(x_1\) < \(x_2\) ≤ \(m\), 1 ≤ \(y_1\) < \(y_2\) ≤ \(n\)). Если оптимальных решений несколько, выведите любое.

Примеры
Входные данные
4 5
7 5 0 7 1
8 9 9 6 7
8 0 2 7 6
7 1 9 2 4
Выходные данные
33
2 1 4 3
Входные данные
3 3
5 -4 -2
5 1 -2
5 -8 2
Выходные данные
10
1 1 3 3
Страница: << 56 57 58 59 60 61 62 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест