Темы --> Информатика --> Алгоритмы
    Задачи на моделирование(78 задач)
    Арифметические алгоритмы(240 задач)
    Алгоритмы поиска(155 задач)
    Алгоритмы сортировки(194 задач)
    Динамическое программирование(355 задач)
    Алгоритмы на графах(319 задач)
    Перебор(154 задач)
    Игры и выигрышные стратегии(33 задач)
    Вычислительная геометрия(216 задач)
    Эвристические методы(30 задач)
    Алгоритмы на строках(45 задач)
    Пересечение множеств(10 задач)
    Жадный алгоритм(71 задач)
    Теория расписаний(5 задач)
    Обработка текста(31 задач)
    Дата и время(14 задач)
---> 115 задач <---
Источники --> Личные олимпиады --> Открытая олимпиада школьников
    2002(9 задач)
    2003(10 задач)
    2004(13 задач)
    2005(12 задач)
    2006(12 задач)
    2007(11 задач)
    2008-2009(19 задач)
    2009-2010(23 задач)
    2010-2011(19 задач)
    2011-2012(8 задач)
    2012-2013(21 задач)
    2013-2014(8 задач)
    2014-2015(8 задач)
Страница: << 12 13 14 15 16 17 18 >> Отображать по:
#1937
Стройка-2
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

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

Деревья на плане изображаются кругами, которые могут пересекаться друг с другом или даже быть вложены один в другой (деревья могли срастись из-за локальных загрязнений окружающей среды, неизбежных при строительстве). Они лежат внутри окружности, соответствующей клумбе, но могут касаться её.

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

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

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

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

Если деревья невозможно оградить забором, не выходящим за границы клумбы, выведите impossible. Иначе в первую строку запишите possible, а в следующие – координаты вершин искомого треугольника. Если ответов несколько, выведите любой.

Примеры
Входные данные
0 0 1000
0 0 500
0 0 500
Выходные данные
possible
-468.09507906626652000000 -883.67810709213904000000
-531.24014997680422000000 847.22128340394170000000
999.33522904307131000000 36.45682368819722500000
#1938
ЕГЭ
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

С целью упрощения ЕГЭ по литературе, было решено оставить в нем вопросы только с ответами «да» или «нет». Бланк ответов представляет клетчатое поле из \(N\) строк и \(M\) столбцов, в котором каждая клеточка соответствует своему вопросу. Ученику необходимо один раз перечеркнуть по диагонали те клеточки, которые, по его мнению, соответствуют вопросам с ответом «нет» (перечеркивать можно по любой из двух диагоналей). При этом во избежание ошибок при сканировании, никакие две диагонали не должны "сливаться", то есть иметь общий конец.

Авторам варианта необходимо знать, какое наибольшее количество вопросов с ответом «нет» можно вставить в вариант, чтобы бланк с правильными ответами мог быть верно распознан компьютером.

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

Вводится два натуральных числа – количество строк \(N\) и количество столбцов \(M\). Количество вопросов в варианте не превосходит 100, то есть \(1 ≤ N ∙ M ≤ 100\).

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

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

Примеры
Входные данные
1 1
Выходные данные
1
/
Входные данные
2 1
Выходные данные
2
/
/
Входные данные
3 3
Выходные данные
6
///
../
\\.
#1939
Эвакуация
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

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

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

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

Сначала вводятся два натуральных числа \(N\), \(K\) (\(1\) ≤ \(N\) ≤ 100000, \(1\) ≤ \(K\) ≤ \(N\)) — количество бункеров и количество выходов соответственно.

Далее через пробел записаны \(K\) различных чисел от \(1\) до \(N\), обозначающих номера бункеров, в которых расположены выходы.

Потом идёт число \(M\) (1 ≤ \(M\) ≤ 100000) — количество туннелей. Далее вводятся M пар чисел – номера бункеров, соединенных туннелем. По каждому из туннелей можно двигаться в обе стороны. В организации не существует туннелей, ведущих из бункера в самого себя, зато может существовать более одного туннеля между парой бункеров.

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

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

Примеры
Входные данные
3
1
2 
3
1 2
3 1
2 3
Выходные данные
1 0 1
Входные данные
10
2
10 8 
9
6 7
7 5
5 8
8 1
1 10
10 3
3 4
4 9
9 2
Выходные данные
1 4 1 2 1 3 2 0 3 0
#1940
Последовательность-2
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

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

Сначала он пишет на доске натуральное число \(A\). Каждое следующее число, выписанное им на доске, будет равно степени с основанием \(A\) и показателем, равным предыдущему числу. Другими словами, последовательность будет выглядеть так:

\(x[1] = A\),

\(x[k + 1] = A^{x[k]}\), \(k\) > 0

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

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

Вводятся два натуральных числа \(A\), \(N\) (\(1\) ≤ \(A\) ≤ \(10^9\), \(1\) ≤ \(N\) ≤ \(10^9\)).

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

Если ни один элемент последовательности не делится на \(N\), выведите 0. Иначе выведите минимальный номер элемента рассмотренной последовательности, делящегося на \(N\).

Примеры
Входные данные
2 2
Выходные данные
1
Входные данные
2 4
Выходные данные
2
#1941
Самолёт
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Самолёт вылетает из города А в \(h_1\) часов \(m_1\) минут по местному времени города А и прилетает в город Б в \(h_2\) часа \(m_2\) минуты (по местному времени города Б). Из города Б он вылетает в \(h_3\) часа \(m_3\) минуты (по местному времени города Б, возможно в другие сутки) и прилетает в город А в \(h_4\) часа \(m_4\) минуты (по местному времени города А). При этом полёт в обе стороны продолжается одно и то же время. Сколько длится полет в одну сторону? Ответ нужно вывести в часах и минутах, округлив его при необходимости до целого числа минут в большую сторону.

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

В каждой из четырех строк в формате hh:mm записаны времена вылета и прилета в том порядке, в котором они перечислены в условии; 0 ≤ \(h_j\) < 24, 0 ≤ \(m_j\) < 60.

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

Выведите время полёта в том же формате hh:mm. Если ответов несколько, выведите минимальный.

Примеры
Входные данные
08:00
10:00
12:00
18:00
Выходные данные
04:00
Входные данные
00:00
00:00
23:59
01:30
Выходные данные
00:46
Страница: << 12 13 14 15 16 17 18 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест