#113093

Том и Джерри

Источники: [ Личные олимпиады, Турнир Архимеда, 2015, Задача F ]

В этой задаче мы снова возвращаемся в младшую группу детского сада «Телепузики». Чтобы окончательно успокоить детей, воспитательница решила включить им мультик про Тома и Джерри. Серия, которую сейчас смотрят дети, довольно-таки незамысловата — в ней Джерри развесил по потолку комнаты наковальни на веревках. Когда Том оказывается под очередной наковальней, Джерри перерезает веревку. Наковальня падает на Тома, Тому больно, всем остальным весело, дети смеются. В общем, вполне обычная серия.

А вам нужно по кадру из этой серии определить, упадет ли наковальня на Тома, если Джерри перережет веревку.

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

Вам дана ASCII-арт картинка, то есть картинка, нарисованная символами. На ней есть наковальня, привязанная веревкой к потолку, и кот Том. В первой строке даны числа $N$, $M$ ($4 \le N \le 100, 1 \le M \le 100$). Следующие $N$ строк состоят из $M$ символов каждая, и представляют собой саму картинку. Картинка устроена следующим образом:

Первые $K_1$ строк в одной и той же позиции $X_1$ стоит символ «|», в остальных — пробел. Это веревка.
Следующие $K_2$ строк в одних и тех же позициях с $X_2$ по $X_3$ стоит символ «#», в остальных — пробел. Это наковальня.
$2 \times X_1 = X_2 + X_3$, то есть наковальня подвешена за середину.
Следующие $K_3$ строк содержат только пробелы. Это пустота между наковальней и котом.
Следующие $N \ − \ K_1 \ − \ K_2 \ − \ K_3$ строк содержат произвольные символы. Любой символ, кроме пробела — часть кота. Существует хотя бы один непробельный символ.

Числа $K_1, K_2, K_3 \ и \ N \ − \ K_1 \ − \ K_2 \ − \ K_3$ ненулевые.

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

Выведите «YES», если при падении наковальня заденет Тома, в противном случае выведите «NO».

Примеры

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

13 29
          |                  
          |                  
          |                  
    #############            
    #############            
    #############            
                             
                             
            /\_/\            
            >^.^<.---.       
           _'-`-'     )\     
          (6--\ |--\ (`.`-.  
              --'  --'  ``-'

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

YES

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

16 30
    |                         
 #######                      
 #######                      
 #######                      
 #######                      
                              
            ,                 
           \)\_               
          /    '. .---._      
        =P ^     `      '.    
         `--.       /     \   
         .-'(       \      |  
        (.-'   )-..__>   , ;  
        (_.--``    (__.-/ /   
                .-.__.-'.'    
                 '-...-'

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

NO

#113094

Куртки

Источники: [ Личные олимпиады, Турнир Архимеда, 2015, Задача G ]

Благотоворительные организации каждый год собирают деньги на теплую одежду бедным. У главного героя этой задачи есть целых две куртки, но это не мешает ему страдать. Одна из его курток — зимняя, а вторая — демисезонная (в ней приятно ходить осенью или весной). Куртки подобраны идеально: в зимней куртке комфортно при температуре в $x$ градусов или ниже, а в демисезонной – при температуре выше $x$ градусов. В общем, жить бы ему и радоваться. Но откуда бы тогда появиться задаче?

Проблема нашего героя в том, что он, надевая сегодня не ту куртку, которую носил вчера, по- стоянно забывает переложить проездной, ключи и прочие полезные вещи в карман новой куртки. Немного подумав, он решил, что не совсем подходящая к сегодняшней температуре куртка — это не так плохо, как забытые вещи. Поэтому, если сегодня незначительно теплее, чем граничная температура, он все равно пойдет в зимней куртке, аналогично для демисезонной. Чуть более формально это звучит так: он меняет куртку с зимней на демисезонную, только если сегодня за окном есть хотя бы $x \ + \ d$ градусов, а с демисезонной на зимнюю — если за окном $x \ − \ d$ градусов или холоднее. Иногда ему, конечно, не очень комфортно на улице, но зато все вещи точно с собой.

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

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

В первой строчке даны два вещественных числа $x$ и $d$ — граница температуры между куртками и отклонение температуры, которое герой задачи считает незначительным ($−89 \le x \le 55, 1 \le d \le 6$).

Во второй строчке дано целое число $n$, $1 \le n \le 10^5$ — количество дней в архиве прогноза погоды.

В третьей строчке перечислены n вещественных чисел $t_i$ — температура в $i$-й день ($−89 \le t_i \le 55$).

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

Выведите одно число: количество дней, в которые герою задачи было некомфортно в той куртке, в которой он вышел в этот день

Примеры

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

5 1
7
6 7 4 4 2 3 7

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

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

0 2
4
-1 1 -1 1

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

#113095

Мама, я диспетчер! (М)

Источники: [ Личные олимпиады, Турнир Архимеда, 2015, Задача H ]

Максим вырос, разочаровался в большой науке и теперь работает авиадиспетчером. Каждый день он делает очень важное и ответственное дело: сажает самолеты.

Этот процесс не такой уж сложный, как может показаться на первый взгляд. В аэропорту, в котором работает Максим, всего одна посадочная полоса, поэтому самолеты должны садиться по очереди. Посадка занимает \)b$ минут. Если самолет прилетел, а посадочная полоса занята, его отправляют совершать дополнительные круги над городом до тех пор, пока он не прилетит к аэропорту со свободной взлётно-посадочной полосой. Один круг занимает $f\( минут. Если посадочная полоса свободна, самолёт немедленно начинает посадку. Если несколько самолётов подлетают к аэропорту со свободной посадочной полосой одновременно, то один из них идёт на посадку, а другие отправляются совершать дополнительные круги.

Сегодня в аэропорт должны прилететь \)n\( самолетов, известно время прилета каждого из них. За какое время все самолёты совершат посадку?

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

В первой строке даны три целых числа \)n$, $b$, $f$ — количество самолетов ($1 \le n \le 1000$), время, которое занимает посадка и время, которое занимает один круг над аэропортом ($1 \le b, \ f \le 10^9$ ). В следующей строке дано $n$ целых чисел $t_i$ — времена прибытия самолетов, перечисленные в произвольном порядке ($0 \le t_i \le 10^9$ ).

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

Выведите одно число: время, за которое все самолёты совершат посадку.

Примеры

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

10 5 12
13 0 1 10 20 20 2 1 10 20

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

#113096

Призы(2016)

Темы: [Линейный поиск]

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Региональный этап, 2016, 1 день, Призы ] [ Личные олимпиады, Всероссийская олимпиада школьников, Региональный этап, 2016, 1 день, Задача A ]

Петя участвует в конкурсе, в котором разыгрывается $n$ призов. Призы пронумерованы от 1 до $n$.

По итогам конкурса участник может набрать от 2 до $n$ баллов. Если участник наберет $k$ баллов, то он получит один из призов с номером от 1 до $k$. Перед тем, как участник выберет свой приз, ведущий конкурса удаляет один из призов из списка. Затем участник может выбрать любой приз из оставшихся $k$ – 1.

Список призов стал известен Пете. Петя определил для каждого приза его ценность, для $i$-го приза она задается целым числом $a_i$ .

Требуется написать программу, которая по заданным ценностям призов определяет для каждого $k$ от 2 до $n$, приз с какой максимальной ценностью гарантированно достанется Пете, если он наберет в конкурсе $k$ баллов.

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

Первая строка входного файла содержит число $n$ ($2 \le n \le 100 000$). Вторая строка этого файла содержит n целых чисел: $a_1, a_2, …, a_n$ ($1 \le a_i ≤ 10^9$ ).

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

Выходной файл должен содержать одну строку, содержащую $n$ – 1 целых чисел: для каждого $k$ от 2 до $n$ должна быть выведена ценность приза, который достанется Пете, если он наберет $k$ баллов.

Описание подзадач и системы оценивания

Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи успешно пройдены.

Подзадача 1 (24 балла)

$n \le 100$

Подзадача 2 (24 балла)

$n \le 5000$

Подзадача 3 (52 балла)

$n \le 100000$

Примеры

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

5
1 3 4 2 5

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

1 3 3 4

#113097

Космическое поселение

Темы: [Бинарный поиск по ответу]

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Региональный этап, 2016, 1 день, Задача B ]

Для освоения Марса требуется построить исследовательскую базу. База должна состоять из $n$ одинаковых модулей, каждый из которых представляет собой прямоугольник.

Каждый модуль представляет собой жилой отсек, который имеет форму прямоугольника размером $a \times b$ метров. Для повышения надежности модулей инженеры могут добавить вокруг каждого модуля слой дополнительной защиты. Толщина этого слоя должна составлять целое число метров, и все модули должны иметь одинаковую толщину дополнительной защиты. Модуль с защитой, толщина которой равна $d$ метрам, будет иметь форму прямоугольника размером $(a + 2d) \times (b + 2d)$ метров.

Все модули должны быть расположены на заранее подготовленном прямоугольном поле размером $w \times h$ метров. При этом они должны быть организованы в виде регулярной сетки: их стороны должны быть параллельны сторонам поля, и модули должны быть ориентированы одинаково.

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

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

Строка содержит пять разделенных пробелами целых чисел: $n$, $a$, $b$, $w$ и $h$ ($1 \le n, a, b, w, h \le 10^{18}$). Гарантируется, что без дополнительной защиты все модули можно разместить в поселении описанным образом.

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

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

Пояснения к примерам

В первом примере можно установить дополнительную защиту толщиной 2 метра и разместить модули на поле, как показано на рисунке.

Во втором примере жилой отсек имеет размер $5 \times 5$ метров, а поле – размер $6 \times 6$ метров. Добавить дополнительную защиту к модулю нельзя.

Описание подзадач и системы оценивания

Подзадача 1 (26 баллов)

$1 \le n \le 1000, 1 \le a, b, w, h \le 1000$.

Баллы за подзадачу начисляются только в случае, если все тесты успешно пройдены

Подзадача 2 (23 балла)

$1 \le n \le 1000, 1 \le a, b, w, h \le 10^9$.

Баллы за подзадачу начисляются только в случае, если все тесты успешно пройдены.

Подзадача 3 (до 24 баллов)

$1 \le n \le 10^9 , 1 \le a, b, w, h \le 10^{18}$.

В этой подзадаче 8 тестов, каждый тест оценивается в 3 балла. Баллы за каждый тест начисляются независимо.

Подзадача 4 (до 27 баллов)

$1 \le n \le 10^{18} , 1 \le a, b, w, h \le 10^{18}$.

В этой подзадаче 9 тестов, каждый тест оценивается в 3 балла. Баллы за каждый тест начисляются независимо.

Примеры

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

11 2 3 21 25

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

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

1 5 5 6 6

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