Темы --> Информатика
    Язык программирования(952 задач)
    Алгоритмы(1657 задач)
    Структуры данных(279 задач)
    Интерактивные задачи(17 задач)
    Другое(54 задач)
---> 544 задач <---
Источники --> Личные олимпиады
    Олимпиады сайта(17 задач)
    Школьная личная олимпиада ФМШ №2007 г. Москвы(7 задач)
    Золотая середина (Новосибирск)(10 задач)
    Нижегородская олимпиада школьников(42 задач)
    Московская олимпиада школьников(168 задач)
    Индивидуальная олимпиада по информатике и программированию (ИОИП)(22 задач)
    Открытая олимпиада школьников(173 задач)
    Украинские олимпиады(61 задач)
    Республиканская олимпиада школьников (Беларусь)(6 задач)
    Жаутыковские олимпиады(8 задач)
    Всероссийская олимпиада школьников(304 задач)
    Международные олимпиады(32 задач)
    Central European Olympiad in Informatics (4 задач)
    Интернет-олимпиады(2 задач)
    COCI(36 задач)
    Турнир Архимеда(36 задач)
    Baltic Olympiad in Informatics(10 задач)
Страница: << 46 47 48 49 50 51 52 >> Отображать по:
#1392
Великий Флатландский Забор
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

С незапамятных времен граница страны Флатландия имеет форму N-угольника без самопересечений и самокасаний (необязательно выпуклого). В каждой из вершин этого многоугольника король построил по башне.

В целях увеличения обороноспособности государства на его территории король задумал построить Великий Флатландский Забор. По причине многолетней войны ресурсов хватает на строительство ровно K стен (неважно, какой длины). Каждая стена должна соединять ровно две башни по прямой и не должна даже частично выходить за пределы Флатландии. К тому же, Забор должен представлять собой не более чем K-угольник также без самопересечений и самокасаний (углов может оказаться и меньше, чем K, так как некоторые соседние стены могут лежать на одной прямой). Военный советник настаивает на том, что площадь защищенной области должна быть как можно больше.

Ваша задача — помочь спроектировать такой Забор.

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

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

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

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

Будем считать, что башни занумерованы числами от 1 до N в порядке перечисления их во входном файле. Во третью строку через пробел выведите номера Q башен, которые будут вершинами Забора, в порядке его обхода против часовой стрелки.

Частичные ограничения

Первая группа состоит из тестов, в которых N ≤ 20 и граница Флатландии представляет собой выпуклый многоугольник.

Вторая группа состоит из тестов, в которых N ≤ 20, но граница может быть уже любой.

Примеры
Входные данные
3 3
0 0
1 0
0 1
Выходные данные
0.50000
3
1 2 3
Входные данные
6 5
0 0
7 0
4 3
4 4
3 4
0 7
Выходные данные
24.50000
5
1 2 3 5 6
Входные данные
4 3
0 0
1 3
0 2
-2 -2
Выходные данные
2.00000
3
1 3 4
#1396
Эволюция
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

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

  1. Все живые организмы планеты происходят от бактерии Bitozoria Programulis.
  2. Эволюция происходила шаг за шагом (по предположению ученых – во время изменения климата на планете).
  3. На каждом шаге эволюции из каждого вида образовывались ровно два подвида, а предыдущий вид исчезал.
  4. Если считать появление бактерии Bitozoria Programulis первым шагом эволюции, то существующие сейчас живые организмы находятся на N-ом шаге.

Чтобы не придумывать названия во время исследований, ученые пронумеровали все виды организмов, которые когда-либо существовали на планете. Для этого они нарисовали дерево эволюции с корнем Bitozoria Programulis, которая получила номер 1. Далее нумеровали виды каждого шага эволюции слева направо. Таким образом непосредственные подвиды Bitozoria Programulis получили номера 2 и 3. Следующими были занумерованы виды третьего шага эволюции – подвиды вида 2 получили номера 4 и 5, а вида 3 – номера 6 и 7, и т.д.

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

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

Первая строка входного файла содержит целое число N (1≤N≤100) – количество этапов эволюции, которые произошли на планете Олимпия до текущего времени. Вторая и третья строки файла содержат по одному натуральному числу, которые представляют номера видов, для которых требуется найти номер их ближайшего общего предка.

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

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

Примеры
Входные данные
4
15
12
Выходные данные
3
Входные данные
18
233016
233008
Выходные данные
14563
#1398
Окружности
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

На плоскости заданы N разных окружностей. Две окружности пересекаются, если они имеют хотя бы одну общую точку.

Напишите программу, которая по координатам центров окружностей и их радиусам найдет пару пересекающихся окружностей.

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

В первой строке входного файла содержится целое числоN (1≤N≤10 000) . В каждой из последующих N строк содержатся три натуральных числа X, Y, R меньших 10 000, которые задают координаты центра окружности (X, Y) и его радиус R.

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

Единственная строка выходного файла должна содержать пару номеров пересекающихся окружностей, либо единственное число 0, если никакие две окружности не пересекаются. Окружности нумеруются соответственно порядку во входном файле, начиная с 1 до N. Если существует несколько пар пересекающиеся окружностей, выведите любую из них. Элементы пары могут быть выведены в произвольном порядке.

Примеры
Входные данные
5
5 10 4
6 20 3
10 15 3
12 8 2
13 13 1
Выходные данные
5 3
#1634
Спички
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Какое минимальное количество спичек необходимо для того, чтобы выложить на плоскости \(N\) квадратов со стороной в одну спичку? Спички нельзя ломать и класть друг на друга. Вершинами квадратов должны быть точки, где сходятся концы спичек, а сторонами – сами спички.

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

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

Единственная строка входного файла содержит одно целое число \(N\) (1≤\(N\)≤\(10^9\)).

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

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

Примеры
Входные данные
4
Выходные данные
12
#1635
Альтернативные пути
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Задано прямоугольную таблицу размером \(M\) строк на \(N\) столбиков. В каждой клеточке записано натуральное число, не превышающее 200. Путник должен пройти по этой таблице из левого верхнего угла в правый нижний, на каждом шаге перемещаясь либо на 1 клеточку направо, либо на 1 клеточку вниз. Очевидно, таких путей много. Для каждого пути можно вычислить сумму чисел в пройденных клеточках. Среди этих сумм, очевидно, есть максимальная.

Будем снисходительными к Путнику, считая «хорошими» не только пути, на которых в точности достигается максимально возможная сумма, а еще и пути, сумма которых отличается от максимальной не более чем на \(K\).

Количество «хороших» путей гарантированно не превышает \(10^9\).

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

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

Первая строка входного файла содержит три целых числа \(M\) (2≤\(M\)≤200), N (2≤\(N\)≤200) и \(K\) (0≤\(K\)≤200). Каждая из последующих \(M\) строк содержит \(N\) чисел, записанных в соответствующих клеточках.

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

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

Примеры
Входные данные
2 3 3
1 9 7
2 5 3
Выходные данные
20
2
Страница: << 46 47 48 49 50 51 52 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест