Темы --> Информатика
    Язык программирования(952 задач)
    Алгоритмы(1657 задач)
    Структуры данных(279 задач)
    Интерактивные задачи(17 задач)
    Другое(54 задач)
---> 59 задач <---
Источники --> Командные олимпиады --> Командные чемпионаты школьников Санкт-Петербурга по программированию
    1999(5 задач)
    2000(7 задач)
    2001(8 задач)
    2002(8 задач)
    2003(9 задач)
    2004(9 задач)
    2005(10 задач)
    2006(10 задач)
    2007(10 задач)
    2008(9 задач)
    2009(10 задач)
    2010(10 задач)
    2011(9 задач)
    2012(10 задач)
    2013(10 задач)
    2014(11 задач)
    2015(11 задач)
    2016(11 задач)
Страница: << 5 6 7 8 9 10 11 >> Отображать по:
#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
#1778
Перевод времени
  

Как известно, с целью экономии электроэнергии многие страны используют переход на так называемое летнее время. Перевод времени осуществляется два раза в год – весной и осенью. Весной осуществляется переход на летнее время: часы переводятся на один час вперед. Осенью летнее время отменяется и часы переводятся на один час назад.

Перевод времени осуществляется ночью. При переходе на летнее время через минуту после 01:59 сразу наступает 03:00. При отмене летнего времени час с 02:00 по 02:59 повторяется два раза. А именно, в день перевода, когда первый раз после 02:59 должно стать 03:00, вместо этого снова становится 02:00.

Как одному из разработчиков новой операционной системы «Mocrosoft Widows 2006», вам поручено написать фрагмент ядра операционной системы, который будет осуществлять автоматический перевод системных часов на летнее время и обратно.

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

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

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

На второй строке находятся два целых числа \(d_1\) и \(d_2\), которые указывают, какой перевод времени осуществляется в текущие и в следующие сутки. Значение 1 означает, что осуществляется переход на летнее время, -1 означает, что осуществляется отмена летнего времени, а 0 означает, что перевода времени не осуществляется.

На третьей строке записано число \(k\) – количество отсчетов времени, которое ваша программа должна вывести (1 ≤ \(k\) ≤ 600).

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

Выходной файл должен состоять из \(k\) строк, \(i\)-я из которых должна содержать показания часов через (\(i\)-1) минут после начального момента времени. Выводите время в формате «hh:mm».

Примеры
Входные данные
118
1 0
4
Выходные данные
01:58
01:59
03:00
03:01
Входные данные
190
-1 0
1
Выходные данные
02:10
Входные данные
0
-1 0
3
Выходные данные
00:00
00:01
00:02
Входные данные
1438
0 1
4
Выходные данные
23:58
23:59
00:00
00:01
#1780
Атака инопланетян
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

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

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

Флот инопланетян прилетел с северо-востока, и застыл в таком положении, что все оси кораблей направлены строго на юго-запад.

Единственный способ нанести урон инопланетной армии – это пустить из некоторой точки поверхности Земли лазерный луч вертикально вверх. Пущенный так луч прожигает насквозь все вражеские корабли, через которые он проходит (даже те, которые он задевает по границе). Но этот выстрел повредит инопланетянам только в случае, если все n кораблей будут при этом поражены.

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

Помогите военным определить площадь территории, на которой можно поставить лазер.

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

В первой строке входного файла содержится целое число \(n\) – количество инопланетных кораблей (1 ≤ \(n\) ≤ 100).

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

Размеры кораблей – положительные числа, не превышающие 1 000. Координаты носов кораблей не превышают по абсолютной величине \(10^5\).

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

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

Примеры
Входные данные
3
2 4 6
4 2 7
3 3 5
Выходные данные
4.500
Страница: << 5 6 7 8 9 10 11 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест