Темы
    Информатика(2656 задач)
---> 109 задач <---
Источники --> Личные олимпиады --> Всероссийская олимпиада школьников --> Региональный этап
    2009(8 задач)
    2010(8 задач)
    2011(8 задач)
    2012(8 задач)
    2013(8 задач)
    2014(8 задач)
    2015(8 задач)
    2016(8 задач)
    2017(8 задач)
    Московская областная олимпиада(13 задач)
    Кировская открытая областная олимпиада(21 задач)
    Санкт-Петербург(3 задач)
Страница: << 9 10 11 12 13 14 15 >> Отображать по:
#3207
Чемпионат по стрельбе
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

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

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

Будем считать, что участник соревнования занял \(k\)-е место, если ровно \((k - 1)\) участников чемпионата набрали строго больше очков, чем он. При этом победителями считались все участники чемпионата, занявшие первое место.

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

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

Первая строка входного файла содержит целое число \(n\) — количество участников чемпионата страны по стрельбе (\(3 \le n \le 10^5\)).

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

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

В выходном файле должно содержаться одно целое число — самое высокое место, которое мог занять папа школьника. Если не существует ни одного участника чемпионата, который удовлетворяет, описанным выше условиям, выведите в выходной файл число 0.

Примечание

Правильные решения для тестов, в которых \(1 \le n \le 1000\), оцениваются из 50 баллов.

Примеры
Входные данные
7
10 20 15 10 30 5 1
Выходные данные
6
Входные данные
3
15 15 10
Выходные данные
1
#3208
Делители
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

Натуральное число \(a\) называется делителем натурального числа \(b\), если \(b = ac\) для некоторого натурального числа \(c\). Например, делителями числа 6 являются числа 1, 2, 3 и 6. Два числа называются взаимно простыми, если у них нет общих делителей кроме 1. Например, 16 и 27 взаимно просты, а 18 и 24 — нет.

Будем называть нормальным набор из \(k\) чисел (\(a_1, a_2, \ldots, a_k\)), если выполнены следующие условия:

  1. каждое из чисел \(a_i\) является делителем числа \(n\);
  2. выполняется неравенство \(a_1 \lt a_2 \lt \ldots \lt a_k\);
  3. числа \(a_i\) и \(a_{i+1}\) для всех \(i\) от \(1\) до \(k - 1\) являются взаимно простыми;
  4. произведение \(a_1a_2\ldots a_k\) не превышает \(n\).

Например, набор (2, 9, 10) является нормальным набором из 3 делителей числа 360.

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

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

Первая строка входного файла содержит два целых числа: \(n\) и \(k\) (\(2 \le n \le 10^8\), \(2 \le k \le 10\)).

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

В выходном файле должно содержаться одно число — количество нормальных наборов из \(k\) делителей числа \(n\).

Примечание

Правильные решения для тестов, в которых \(n \le 1000\) и \(k = 2\), оцениваются из 30 баллов.

Правильные решения для тестов, в которых \(k = 2\), оцениваются из 60 баллов (в эти баллы включаются также 30 баллов для случая \(n \le 1000\), \(k = 2\)).

Примеры
Входные данные
90 3
Выходные данные
16
Входные данные
10 2
Выходные данные
4
#3209
Дом у дороги
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes
Пересечение полуплоскостей за O(NlogN)

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

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

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

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

Первая строка входного файла содержит одно целое число \(n\) — количество наиболее важных трасс (\(1 \le n \le 10^4\)).

Последующие \(n\) строк описывают трассы. Каждая трасса описывается четырьмя целыми числами \(x_1\), \(y_1\), \(x_2\) и \(y_2\) и представляет собой прямую, проходящую через точки \((x_1, y_1)\) и \((x_2, y_2)\). Координаты заданных точек не превышают по модулю \(10^4\). Точки \((x_1, y_1)\) и \((x_2, y_2)\) ни для какой прямой не совпадают.

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

Выходной файл должен содержать два разделенных пробелом вещественных числа: координаты точки, в которой следует построить офис министерства дорожного транспорта. Координаты по модулю не должны превышать \(10^9\), гарантируется, что хотя бы один такой ответ существует. Если оптимальных ответов несколько, необходимо выведите любой из них.

Ответ должен иметь абсолютную или относительную погрешность не более \(10^{-6}\), что означает следующее. Пусть максимальное расстояние от выведенной точки до некоторой трассы равно \(x\), а в правильном ответе оно равно \(y\). Ответ будет засчитан, если значение выражения \(|x - y| / max(1, |y|)\) не превышает \(10^{-6}\).

Примечание

Правильные решения для тестов, в которых \(n \le 100\) и все прямые параллельны, оцениваются из 20 баллов.

Правильные решения для тестов, в которых \(n \le 100\) и все прямые параллельны осям координат, оцениваются из 20 баллов.

Правильные решения для тестов, в которых \(n \le 100\), оцениваются из 70 баллов (в эти баллы включаются также по 20 баллов за случаи, описанные в предыдущих двух абзацах).

Примеры
Входные данные
4
0 0 0 1
0 0 1 0
1 1 2 1
1 1 1 2
Выходные данные
0.5000000004656613 0.4999999995343387
Входные данные
7
376 -9811 376 -4207
6930 -3493 6930 -8337
1963 -251 1963 -5008
-1055 9990 -684 9990
3775 -348 3775 1336
7706 -2550 7706 -8412
-9589 8339 -4875 8339
Выходные данные
4040.9996151750674 12003.999615175067
#3864
Цапли
  
Темы: [Целые числа]
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Петя и Маша пришли в зоопарк. Больше всего Пете понравились цапли. Он был поражен их способностью спать на одной ноге.

В вольере находятся несколько цапель. Некоторые из них стоят на двух ногах, некоторые — на одной. Когда цапля стоит на одной ноге, то другую ее ногу не видно. Петя пересчитал видимые ноги всех цапель, и у него получилось число a.

Через несколько минут к вольеру подошла Маша. За это время некоторые цапли могли поменять позу, поэтому Петя предложил ей заново пересчитать видимые ноги цапель. Когда Маша это сделала, у нее получилось число b.

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

Требуется написать программу, которая по заданным числам a и b выведет минимальное и максимальное количество цапель, которое могло быть в вольере.

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

Входной файл содержит два целых числа a и b, разделенных ровно одним пробелом (1 ≤ a ≤ 109, 1 ≤ b ≤ 109).

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

Выведите в выходной файл два целых числа, разделенных пробелом — минимальное и максимальное число цапель, которое могло быть в вольере. Гарантируется, что хотя бы одно количество цапель соответствует условию задачи.

Примечание к примеру тестов

В приведенном примере возможны следующие варианты:

  1. В вольере две цапли. Когда Петя считал ноги, одна цапля стояла на двух ногах, а другая — на одной. Петя насчитал три ноги. Когда Маша считала ноги, обе цапли стояли на двух ногах, Маша насчитала четыре ноги.
  2. В вольере три цапли. Когда Петя считал ноги, все цапли стояли на одной ноге, Петя насчитал три ноги. Когда Маша считала ноги, одна цапля стояла на двух ногах, а еще две — на одной. Маша насчитала четыре ноги.
Примеры
Входные данные
3 4
Выходные данные
2 3
#3865
Круглый стол
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

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

Руководитель клуба Иван Петрович недавно заметил, что не все ребята активно участвуют в обсуждении. Понаблюдав за несколькими заседаниями клуба, он заметил, что активность члена клуба зависит от того, кто с кем сидит рядом.

В клуб приходят на занятия m мальчиков и n девочек. Иван Петрович заметил, что мальчик активно участвует в обсуждении только тогда, когда непосредственно рядом с ним с обеих сторон от него сидят девочки, а девочка активно участвует в обсуждении только тогда, когда непосредственно рядом с ней с одной стороны от нее сидит мальчик, а с другой — девочка.

Желая сделать заседание клуба как можно более интересным, Иван Петрович решил разместить участников за круглым столом таким образом, чтобы как можно больше членов клуба приняло активное участие в обсуждении.

Требуется написать программу, которая по заданным числам m и n выведет такой способ размещения m мальчиков и n девочек за круглым столом, при котором максимальное количество членов клуба будет активно участвовать в обсуждении.

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

Входной файл содержит два целых числа m и n, разделенных ровно одним пробелом (0 ≤ m ≤ 1000, 0 ≤ n ≤ 1000, m + n ≥ 3).

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

Выходной файл должен содержать строку с расположенными в некотором порядке m символами «B» (заглавная латинская буква) и n символами «G» (заглавная латинская буква). Символ «B» означает мальчика, а символ «G» — девочку.

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

Примечание к примерам тестов

В первом примере все члены клуба примут активное участие в обсуждении.

Во втором примере мальчики примут активное участие в обсуждении, а девочки нет. В этом примере можно также разместить членов клуба следующим образом: «BBGG». В этом случае активное участие в обсуждении примут обе девочки, а мальчики — нет. Разместить всех так, чтобы три или четыре члена клуба приняли активное участие в обсуждении, нельзя.

Примеры
Входные данные
1 2
Выходные данные
BGG
Входные данные
2 2
Выходные данные
BGBG
Страница: << 9 10 11 12 13 14 15 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест