1. Задания финального (Real-Time) тура

ЗАДАНИЯ ФИНАЛЬНОГО ТУРА NetOI-2019

Задача Decentralization. Реформа децентрализации хорошо повлияла на количество денег, которые местная власть может отдать на важные проекты. Однако не все города пользуются популярностью среди туристов, а власть стремится максимально увеличить привлекательность страны в целом, потому отметила из всех N городов ровно K самых популярных. Государственные эксперты порекомендовали всем мэрам городов в случае необходимости "поделиться" их местными бюджетами с другими городами (*), чтобы те могли развить туристический сектор, а также поставили четкую метрику привлекательности страны - минимальный среди бюджетов, выделенных на развитие популярных городов.

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

Примечания

*)по новым антикоррупционным правилам, часть бюджета может перейти из одного города в другой лишь в случае, когда хотя бы один из них туристически популярный (то есть имеется в том же списке из К городов), а кроме того между этими двумя городами заключен договор сотрудничества. При этом лимита на "переливание" средств нет (кроме того, что бюджет не должен "пойти в минус"). Кроме того, разрешается делиться только целым количеством гривен.

Технические условия. Программа Decentralization читает с первой строки стандартного устройства ввода три числа - N и K (1 ≤ K ≤ N ≤ 10'000), а также количество договоров сотрудничества M (0 ≤ M ≤ N *  (N - 1)  / 2). Со второй строки следует прочитать ровно K различных чисел, каждое из которых в пределах от 1 до N - отмеченные города. Дальше, с третьей строки, программа читает еще N чисел - бюджеты городов, каждое число от 0 до 10⁶, i- тое число задает бюджет i- го города. Дальше следуют ровно M пар чисел, которые задают договоры сотрудничества в формате A_i B_i, что означает, что между городами A_i и B_i  заключен договор.

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

Примеры

Ввод	Вывод	Пояснения
3 2 2 1 3 3 3 3 1 2 2 3	4	Из второго города можно отдать по 1 гривне в первый и третий город, после чего их бюджеты будут равными - по 4 гривни. При этом, даже если последнюю гривну бюджета второго города отдать кому-то другому, увеличить метрику не удастся - ведь минимальный из бюджетов все равно будет равен 4.
3 2 2 2 3 6 0 4 1 2 2 3	5	Можно перевести из первого города во второй все 6 гривен бюджета, после чего из второго в третий перевести 1 гривну. После этого минимальное значение бюджета среди популярных городов станет равным 5.

---

Задача Forum.  На форуме одной  маленькой, но очень гордой  олимпиады есть тема, посвященная обсуждению правил. Она содержит N страниц, пронумерованных от 1 до N. Заходя в тему, пользователь попадает на страницу с номером 1. Интерфейс пользователя (UI)   на форуме организован таким образом, что из страницы с номером i возможно за один клик перейти на страницы с номерами i - 1 (если  i>1), i+1 (если i<N), 1, N, floor ((1+i)/2), ceil ((i+N)/2).*  Анализ активности сайта показал, что в теме пользователь выполняет не больше K кликов.  Администрацию олимпиады  интересует, сколько страниц темы  при таких условиях вообще кто-то сможет прочитать.

Технические условия. Программа Forum читает с устройства стандартного ввода 2 целіх числа, N (1≤N≤2*10⁸) и K (0≤K≤10⁶). Программа выводит единственное целое число - количество страниц, которые можно прочитать за K либо меньше кликов.

Пример

Ввод

10 1

 Вывод

4

*)Примечание: floor((1+i)/2) – наибольшее целое число, не превосходящее  (1+i)/2

                              ceil((i+N)/2) – наименьшее целое число, не меньшее (i+N)/2

Вам необходимо найти минимальное возможное время тест-драйва.

Технические условия. Программа  HardWay читает с устройства стандартного ввода в первой строке число N (2 ≤ N ≤ 30) - количество зон на карте. Со следующей строки программа читает N - 1 чисел y_i, задающих y = y_i  - границы зон (i-тая прямая задает границу между i и i+1 зонами). С третьей строки программа читает четыре числа x_A y_A x_B y_B - координаты начальной и конечной точек маршрута. Все числа натуральные и удовлетворяют неравенству: 0 < y_A < y₁ < y₂ < …  < y_N-1 < y_B ≤ 100’000, x_A ≤ 100’000, x_B ≤ 100’000. С четвертой строки программа читает N чисел V_i – максимально возможные скорости в каждой из N зон. При этом 1 ≤ V_i ≤ 10000. Скорости заданы в порядке прохождения зон.

Программа выводит ровно одно действительное число - минимальное время, необходимое на путь между пунктами A и B при условии движения по каждой зоне с максимально возможной для нее скоростью. Ответ будет засчитан, если абсолютная или относительная погрешность составят не более чем 10^-6.

Пример

Ввод	Вывод	Комментарий
2 2 1 1 1 22 1 20	2.0000000	Оптимальным будет движение по прямой - тогда в первой зоне будет пройдено 1 единицу пути (со скоростью 1), во второй 20 единиц (со скоростью 20), всего 2 единицы времени.
3 5 11 1 1 15 15 3 4 3	5.8333333	Показано (см.рисунок)   оптимальный маршрут. Затраченное время при этом составит 5/3 + 10/4 + 5/3 = 35/6, то есть 5,8(3)

 

---

Задача Spiral.   Числа натурального ряда вписаны в клетки плоскости по спирали, так что 1 вписано в клетку (0,0), 2 - в (1,0), 3 - (1,1) и т. д.  Найти сумму, по модулю 1000000007, чисел, лежащих (включительно) в прямоугольнике, стороны которого параллельны осям,  с углами в (x0, y0) и (x1, y1).

Технические условия.    Программа Spiral читает со стандартного устройства ввода 4 целых числа: x0, y0, x1, y1 (-10⁹≤x0≤x1≤10⁹, -10⁹≤y0≤y1≤10⁹). Программа выводит на стандартное устройство вывода единственное число - искомую сумму по модулю.

   Пример.

   Ввод  -1 1 2 3

   Вывод  216

Комментарий к примеру. Прямоугольник   -1≤x≤2 ,  1≤y≤3 содержит 12 клеток. Их сумма 5+4+3+12+16+15+14+13+35+34+33+32=216.

---

Задача Status. В одной очень известной в кругах участников NetOI компьютерной игре герой и монстр имеют такие свойства: HP (здоровье), Atk (атака), Def (защита), Spd (скорость). Бой между ними происходит следующим образом:  у кого выше Spd - ходит первым; при равных Spd - первым ходит монстр - у него было время подготовиться, пока герой  к нему добрался. За  один ход игрок  HP противника  "наносит ему потери" на величину разности своей Atk и его Def   (если эта величина положительна, иначе  HP соперника не изменяется). Бой заканчивается, когда здоровье одного из участников падает до 0 или ниже.  Определите, на какое наименьшее количество  пунктов (суммарно) нужно герою увеличить параметры (количество пунктов - это сумма 4-х (целых, неотрицательных) слагаемых к HP, Atk, Def, Spd соответственно) перед боем, чтобы победить (когда в конце поединка  HP героя будет положительным, а монстра 0 или ниже). 

Технические условия. Программа Status читает с устройства стандартного ввода 8 натуральных чисел не больших 999999999: сначала  4 параметра героя (в порядке HP, Atk, Def, Spd),  далее 4 параметра  монстра (в том же порядке). Программа выводит на стандартное устройство вывода единственное целое число - минимально необходимое суммарное число пунктов, которые нужно до начала боя где-то раздобыть герою для победы.

  Пример

  Ввод: 10 7 4 10 29 10 2 5

  Вывод: 5

 Комментарий к примеру. В начальной ситуации герой наносит монстру 7-2 = 5 пунктов потерь за  1- ход, а монстр герою - 10-4 = 6  (герой ходит первым). Таким образом, через 2 хода каждого соперника, здоровье героя уменьшается до -2, а у монстра еще остается 19. Но если повышать защиту героя на 5 пунктов, то монстр буде наносить герою 10- (4 + 5) = 1 потерю за ход, і тогда после  6-ти ходов героя (і 5  монстра) здоровье монстра снижается до -1, а у героя еще осталось 5.

---

Завдання підготували М.Авраменко, В.Бездушний, Г.Непомнящий, Ю.Пасіхов, Д.Поліщук, М.Стречень