Темы --> Информатика --> Алгоритмы
    Задачи на моделирование(78 задач)
    Арифметические алгоритмы(240 задач)
    Алгоритмы поиска(155 задач)
    Алгоритмы сортировки(194 задач)
    Динамическое программирование(355 задач)
    Алгоритмы на графах(319 задач)
    Перебор(154 задач)
    Игры и выигрышные стратегии(33 задач)
    Вычислительная геометрия(216 задач)
    Эвристические методы(30 задач)
    Алгоритмы на строках(45 задач)
    Пересечение множеств(10 задач)
    Жадный алгоритм(71 задач)
    Теория расписаний(5 задач)
    Обработка текста(31 задач)
    Дата и время(14 задач)
---> 17 задач <---
Источники --> Личные олимпиады --> Украинские олимпиады
    1999(3 задач)
    2000(5 задач)
    2001(4 задач)
    2002(7 задач)
    2003(3 задач)
    2004(6 задач)
    2005(5 задач)
    2006(6 задач)
    2007(6 задач)
    2008(5 задач)
    2009(6 задач)
    2010(0 задач)
    2011(0 задач)
    2012(0 задач)
    2013(0 задач)
    2016(5 задач)
Страница: << 1 2 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
#1637
Домино
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Набор домино состоит из прямоугольных костяшек, каждая из которых разделена на две половинки линией, параллельной более короткой стороне. На каждой из половинок нарисованы точки, количество которых соответствует числу от 0 до \(M\) включительно. На костяшках полного набора домино обозначены все возможные различные пары чисел, например, если M равно 3, то полный набор содержит 10 костяшек: (0, 0), (0, 1), (0, 2), (0, 3), (1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (3, 3).

Из костяшек можно выкладывать цепочки, соединяя пары костяшек короткими сторонами, если количества точек на соседних с местом соединения половинках костяшек равны.

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

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

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

В первой строке входного файла содержится одно целое число \(M\) (0≤\(M\)≤100), которое соответствует максимально возможному количеству точек на половинке костяшки. Во второй строке записано одно целое число \(N\), равное количеству костяшек, удаленных из полного набора. Каждая \(і\)-я из последующих \(N\) строк содержит по два числа \(A_i\) и \(B_і\). Это количества точек на половинках \(i\)-й удалённой костяшки.

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

Единственная строка выходного файла должна содержать одно целое число \(L\) – минимальное количество цепочек.

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