Задача A. Рабочая атмосфера Имя входного файла стандартный ввод Имя выходного файла стандартный вывод Ограничение по времени 1 секунда Ограничение по памяти 256 мегабайт в компании Контур
 Скачать 306.17 Kb.
|
|
Уральская командная олимпиада по программированию 2021 Екатеринбург, Россия, 7 ноября 2021 года Задача A. Рабочая атмосфера Имя входного файла: стандартный ввод Имя выходного файла: стандартный вывод Ограничение по времени: 1 секунда Ограничение по памяти: 256 мегабайт В компании «Контур» есть open space, где рабочие места выставлены в форме квадрата N × N ячеек. В каждой ячейке работает один человек. Начальство считает, что такое расположение по- вышает трудоспособность. Каждый из N 2 человек приходит в свое время, садится на свое место и старается переплюнуть свой ряд и столбец. Поэтому его трудоспособность равна максимуму из тру- доспособностей в ряду и столбце +1. Будем считать трудоспособность ещё не занятых мест равной 0. Каждый день сотрудники приходят в разное время. Когда все расселись, менеджер записывает максимальную трудоспособность во всем open space-е. Скажите, какое минимальное и максимальное значение может быть записано. Формат входных данных В единственной строке дано целое число N — длина стороны open space (1 6 N 6 10 9 ) Формат выходных данных Выведите два целых числа — минимальное и максимальное возможное значение максимальной трудоспособности во всем open space-е. Пример стандартный ввод стандартный вывод 2 2 4 Страница 1 из 13 Уральская командная олимпиада по программированию 2021 Екатеринбург, Россия, 7 ноября 2021 года Задача B. Две прогрессии Имя входного файла: стандартный ввод Имя выходного файла: стандартный вывод Ограничение по времени: 2 секунды Ограничение по памяти: 256 мегабайт Дан набор из N целых чисел a 1 , a 2 , . . . , a n . Разбейте его на две прогрессии: арифметическую и геометрическую. Каждое число должно войти ровно в одну из прогрессий, и в каждую из прогрессий должно попасть хотя бы одно число. Напоминаем, что арифметическая прогрессия — это последовательность чисел вида b, b + d, b + 2d, . . . , b + (k − 1) · d , где b — первый элемент прогрессии, d — шаг прогрессии, k — её длина. А геометрическая прогрессия — это последовательность чисел вида c, c · q, c · q 2 , . . . , c · q t−1 , где c — первый элемент прогрессии, q — шаг прогрессии (q 6= 0), t — её длина. Формат входных данных В первой строке дано целое число N — количество чисел в наборе (2 6 N 6 50 000). Во второй строке через пробел даны N целых чисел a 1 , a 2 , . . . , a n — сам набор чисел (0 6 a i 6 1 000 000 000). Формат выходных данных Если решения не существует, в единственной строке выведите «−1» (без кавычек). Иначе, в первой строке выведите целое число — длину арифметической прогрессии. Во второй строке выведите через пробел числа из арифметической прогрессии в том порядке, в котором они идут в этой прогрессии. В третьей строке выведите через пробел числа из геометрической прогрессии в том порядке, в котором они идут в этой прогрессии. Примеры стандартный ввод стандартный вывод 6 0 2 3 4 6 8 3 0 3 6 2 4 8 6 4 4 6 6 8 9 3 4 6 8 4 6 9 4 0 0 0 0 1 0 0 0 0 5 0 0 1 1 2 -1 Замечание В первом примере найдена арифметическая прогрессия с шагом 3 и геометрическая прогрессия с шагом 2. Правильным ответом также является пара из арифметической прогрессии 0, 2, 4, 6 и геометрической прогрессии 3, 8, а также арифметическая прогрессия 0, 2, 4, 6, 8 и геометрическая прогрессия 3. Во втором примере геометрическая прогрессия имеет шаг 3 2 . Обратите внимание, что геометри- ческая прогрессия может иметь нецелый шаг и при этом состоять из целых чисел. В третьем примере геометрическая прогрессия имеет первый элемент 0, а шагом может быть любое положительное число. Страница 2 из 13 Уральская командная олимпиада по программированию 2021 Екатеринбург, Россия, 7 ноября 2021 года Задача C. Сочинение Имя входного файла: стандартный ввод Имя выходного файла: стандартный вывод Ограничение по времени: 2 секунды Ограничение по памяти: 256 мегабайт Витя живет в Берляндии и очень хочет поступить в университет. Для этого ему нужно сдать Единый Берляндский Экзамен, а для этого нужно получить зачёт за так называемое «тотальное со- чинение». Витя не силен в берляндском языке, а в сочинениях вообще профан, поэтому он обратился за помощью к Вале. Валя разузнал, по каким критериям будет осуществлена проверка тотального сочинения, и поделился ими с Витей. Сочинением является последовательность слов (непустых последовательностей из строчных ла- тинских букв), записанная через пробел. Например, «aba caba» или «kek» — сочинения, а «Oh yeah! » или «wrong answer» — нет. Для получения зачета нужно, во-первых, обязательно написать n ключевых слов: s 1 , s 2 , . . . , s n Во-вторых, нужно соблюдать k правил вида (a i , b i ) — если в сочинении встречается слово a i , то после него в сочинении должно обязательно встретиться слово b i , не обязательно сразу за a i . Если все эти правила соблюсти, то за сочинение гарантирован зачет. Вите сложно это запомнить, поэтому Валя предложил ему обратиться к Вам за помощью. Помо- гите составить кратчайшее сочинение, которое гарантированно будет зачтено. Если среди кратчай- ших по длине возможно несколько вариантов, выберите лексикографически меньший (см. приме- чание). Учтите: возможно, что не существует ни одного сочинения, которое гарантированно будет зачтено. Формат входных данных В первой строке вводятся целые числа n и k — количество ключевых слов и правил, соответ- ственно (1 6 n, k 6 100 000). В следующих n строках вводятся по одному в строке ключевые слова s 1 , s 2 , . . . , s n . Гарантиру- ется, что все ключевые слова различны. В последних k строках вводятся по одному в строке правила: в i-й строке записано через пробел два слова a i b i , обозначающие правило вида (a i , b i ) . Гарантируется, что никакие два правила не совпадают, то есть для любых i 6= j верно или a i 6= a j , или b i 6= b j Гарантируется, что суммарная введённая длина всех слов не превышает 2 000 000. Формат выходных данных В единственной строке выведите ответ на задачу: самое короткое (а среди всех самых коротких — лексикографически минимальное) сочинение, если такое существует, или −1, если не существует. Вывод проверяется строго: между словами следует ставить единственный пробел, а вывод сочи- нения следует завершить единственным символом — переводом строки. Примеры стандартный ввод стандартный вывод 2 3 atan tan atan ate atan tabular zzz atan atan ate tabular tan 1 3 a a b b c c a -1 Страница 3 из 13 Уральская командная олимпиада по программированию 2021 Екатеринбург, Россия, 7 ноября 2021 года Замечание Сочинение p = p 1 p 2 . . . p a (p 1 , p 2 , . . . , p a — символы: буквы или пробелы) лексикографически меньше сочинения q = q 1 q 2 . . . q b (q 1 , q 2 , . . . , q b — тоже символы), если выполнено одно из двух: • a < b и p 1 = q 1 , p 2 = q 2 , . . . , p a = q a • Существует такое i, что для всех j < i выполняется p j = q j , но символ p i стоит в алфавите раньше, чем символ q i . Считается, что пробел стоит в алфавите раньше всех букв латинского алфавита. Например p = aba лексикографически меньше сочинения q = ac, потому что p 1 = q 1 = a , но p 2 = b стоит в алфавите раньше, чем q 2 = c Страница 4 из 13 Уральская командная олимпиада по программированию 2021 Екатеринбург, Россия, 7 ноября 2021 года Задача D. Гигант-вандал Имя входного файла: стандартный ввод Имя выходного файла: стандартный вывод Ограничение по времени: 1 секунда Ограничение по памяти: 256 мегабайт Скоро зима... Окна офиса компании «NAUMEN» покрылись инеем в своём уникальном стиле. Каждый рисунок — невероятное творение природы. Но почему же на некоторых окнах соседне- го жилого дома нет вообще никаких узоров? Неужели это опять работа гиганта-вандала? Да, на нескольких этажах дома выбиты окна, на такое способны только гиганты-вандалы, но кто из них? Вначале нужно определить минимальный рост преступника. Пусть в здании N этажей, пронуме- рованных снизу вверх от 1-го до N-го. Если гигант-вандал ростом с K этажей, то он может выбить окна любого этажа с 1-го по K-й просто находясь на земле, а затем залезть в выбитое им же окно. Если же этот же гигант-вандал находится на M-м этаже, то он может выбить окна любого этажа с (M + 1) -го по (M + K)-й, затем так же забраться на этот этаж. Ваша задача помочь жильцам дома найти минимальный возможный рост гиганта-вандала, вы- бившего им окна. Формат входных данных Вам дан вид жилого дома с улицы. Каждый этаж описывается двумя строками по три символа в каждой. Этаж с сломанным окном описывается так: --- | | Этаж с окном, покрытым инеем, описывается так: --- |c| Где «c» - это любой символ с кодом от 33 до 126. Ввод заканчивается строкой === В вводе используются символы «-» (код 45), «|» (код 124), «=» (код 61), « » (код 32), а также любой символ с кодом от 33 до 126 для обозначения рисунка. Гарантируется, что в доме этажей не меньше 1 и не больше 10 5 , и что выбито хотя бы одно окно. Формат выходных данных Выведите минимальный возможный рост гиганта-вандала, выбившего окна. Пример стандартный ввод стандартный вывод --- |A| --- | | --- |*| --- |h| --- | | === 3 Страница 5 из 13 Уральская командная олимпиада по программированию 2021 Екатеринбург, Россия, 7 ноября 2021 года Задача E. Игра в кальмара Имя входного файла: стандартный ввод Имя выходного файла: стандартный вывод Ограничение по времени: 1 секунда Ограничение по памяти: 256 мегабайт Наконец-то начался 2-й сезон «Игры в кальмара» в Китае. В текущей игре ведущий загадал перестановку длины n, то есть, последовательность чисел от 1 до n, записанных в любом порядке без повторов. Участникам в начале игры выдали число и листочек. Участнику под номером 22 Йокаю достался листок в линеечку с m строчками. Ему нужно угадать выбранную ведущим перестановку. Йокай должен выписать на листок m пар индексов от 1 до n, индексы в каждой паре должны быть раз- ными. Затем ассистент ведущего для каждой пары индексов говорит, под каким индексом число из перестановки больше. После этого участник угадывает перестановку. Если он не угадал, то его убивают. У вас есть листочек Йокая. Скажите гарантированно ли он выживет? То есть, правда ли, что при любой загаданной перестановке, ответам ассистента на запросы Йокая удовлетворяет только она. Формат входных данных В первой строке вводятся целые числа n и m — размер перестановки и число строк на листке (2 6 n 6 10 5 , 1 6 m 6 10 5 ). В следующих m строках вводятся целые числа x i , y i — индексы, которые записал Йокай (1 6 x i , y i 6 n, x i 6= y i ). Формат выходных данных Если существует 2 перестановки, такие что для них одинаковы ответы на все вопросы Йокая, то в единственной строке выведите «NO» (без кавычек). Иначе, выведите «YES» (без кавычек). Примеры стандартный ввод стандартный вывод 2 1 1 2 YES 2 2 1 2 1 2 YES Страница 6 из 13 Уральская командная олимпиада по программированию 2021 Екатеринбург, Россия, 7 ноября 2021 года Задача F. Мета-условие Имя входного файла: стандартный ввод Имя выходного файла: стандартный вывод Ограничение по времени: 2 секунды Ограничение по памяти: 256 мегабайт ...Затем Вадим переставил задачи, как ему нужно было и... Самое трудное в работе жюри кроме придумывания задач, написания корректных решений, создания чекеров, валидаторов, тестов, условий и разборов — это расставление задач между собой в уже готовом комплекте. Никто не знает, как это правильно делать, поэтому для этого используется древняя техника. Это тайное знание состоит в одном простом алгоритме: 1. Вначале каждая задача из комплекта сортируется по сложности, самой сложной из них при- сваивается 1, второй по сложности — 2, и так далее. 2. Затем берётся шаблон — какая-то перестановка чисел от 1 до N, где N — количество задач в контесте, которая отвечает за расстановку задач по сложности. 3. После этого ищется левый подшаблон и правый подшаблон. Для этого в шаблоне находится позиция самой сложной задачи. Тогда левый подшаблон — это шаблон, отвечающий за все те задачи, которые находятся до самой сложной (если самая трудная задача была первой в шаблоне, то он становится пустым), а правый подшаблон — это шаблон, отвечающий за все те задачи, которые находятся после самой сложной (если самая трудная задача была последней в шаблоне, то он становится также пустым). 4. Два шаблона называются эквивалентными, если они оба пустые, либо позиция самой трудной задачи у них совпадает, их левые подшаблоны эквивалентны, и их правые подшаблоны также эквивалентны. 5. И финальный шаг для расставления задач в контесте — это выбрать произвольный эквива- лентный шаблон к данному вначале. Проблема в этом одна. Жюри всегда брали один и тот же древний шаблон, и настало время его поменять, но для этого нужно посчитать количество эквивалентных ему шаблонов. Жюри сейчас занято перестановкой задач в другом контесте и ответами на вопросы участников, поэтому эта задача достаётся Вам. Формат входных данных В первой строке вводится одно целое число N — количество задач в комплекте (1 6 N 6 10 5 ) Во второй строке вводятся N целых чисел p i через пробел — описание проверяемого Вами шаб- лона (1 6 p i 6 N , все p i различные). Формат выходных данных Выведите количество шаблонов, эквивалентных данному, по модулю 10 9 + 7 . То есть, найдите остаток при делении количества шаблонов на 1 000 000 007. Примеры стандартный ввод стандартный вывод 3 2 1 3 2 12 12 5 3 11 2 8 4 9 1 6 10 7 34650 Замечание В первом примере существуют только два эквивалентных шаблону из ввода шаблона — (2, 1, 3) и (3, 1, 2). Страница 7 из 13 Уральская командная олимпиада по программированию 2021 Екатеринбург, Россия, 7 ноября 2021 года Задача G. Mount & Blade Имя входного файла: стандартный ввод Имя выходного файла: стандартный вывод Ограничение по времени: 1.5 секунд Ограничение по памяти: 256 мегабайт «Добро пожаловать в славный город Правен, столицу королевства Свадии и просто лучшее место во всей Кальрадии!» — громогласно сообщает на въезде в крепость человек короля Харлауса, облачённый в роскошные шелка. Оно и понятно — успешная военная кампания против Хергитского ханства сильно озолотила королевство, а по этому поводу было решено провести рыцарский турнир, чтобы выявить лучшего воина на всём континенте. Подходя к списку участников, Вы видите, что на турнир записалось n человек. Вам известно о каждом из них, каким оружием он оснащён, а также Вы знаете по достоверным слухам о богатстве каждого из них. Рядом со списком висят и правила турнира. Они гласят следующее: • Каждый из рыцарей сойдётся в парном бою на копьях и щитах с другим. • Рыцаря сокрушили в бою, если величина прочности его щита не превосходит атаки копья соперника. • Рыцарь побеждает в бою, если его противник был сокрушен, а он сам — нет. • Рыцарь объявляется абсолютным победителем турнира, если он победил всех соперников. Далеко не по слухам Вам известно, что каждый рыцарь очень сильно хочет стать абсолютным победителем , поэтому они готовы вложить все свои деньги в улучшение снаряжения. Благо сейчас, чтобы усилить мощь копья или увеличить прочность щита на одну условную единицу, нужна лишь одна золотая монета, а их у рыцарей скопились горы после успешной войны. Вас интересует лишь один вопрос — есть ли рыцарь, который может стать абсолютным побе- дителем при правильном оснащении независимо от действий других, ведь тогда можно сделать хорошую ставку. Учтите, что до поединка рыцари не знают, как именно готовятся их соперники. Формат входных данных В первой строке заданы одно целое число n — количество рыцарей, принявшее участие в турнире(1 6 n 6 10 5 ). В следующих n строках записано по тройке целых чисел a i , d i , g i — сила атаки копья, прочность щита и количество золотых монет у i-го рыцаря (0 6 a i , d i , g i 6 10 9 ). Формат выходных данных В единственной строке выведите число i — номер рыцаря, который является абсолютным побе- дителем турнира. Если же такого не оказалось, то число -1. Рыцари пронумерованы от 1 до n в том порядке, в котором они описаны во входных данных. Примеры стандартный ввод стандартный вывод 2 100 4 5 1 2 8 -1 3 5 2 2 4 1 10 10 4 0 2 Замечание В первом примере рыцарь номер 1 не может победить. Даже если он вложит все свои деньги в защиту, она будет равна 9, а второй рыцарь может улучшить свою атаку также до 9. В таком случае первый рыцарь сокрушён, несмотря на то, что и его соперник тоже. Страница 8 из 13 Уральская командная олимпиада по программированию 2021 Екатеринбург, Россия, 7 ноября 2021 года Задача H. Графомания Имя входного файла: стандартный ввод Имя выходного файла: стандартный вывод Ограничение по времени: 2 секунды Ограничение по памяти: 256 мегабайт Валя был очень занят подготовкой контестов по программированию, поэтому ему теперь везде мерещатся задачи. Смотря на расписание автобусов, он видит массив из N чисел. Глядя на сидящих в автобусе людей, он замечает задачу на динамическое программирование. А на схеме маршрута он видит только неориентированный граф. Даже в массиве чисел он видит графы. В спортивном программировании обычно используются простые неориентированные графы без петель и кратных рёбер. Такие графы, как правило, зада- ются массивом рёбер. Формально, граф из N вершин и M рёбер задаётся последовательностью из 2 + 2 · M целых чисел: сначала идёт число N, затем число M, затем M пар чисел, обозначающих рёбра. Каждое ребро задаётся номерами вершин, которые оно соединяет. Вершины нумеруются от 1 до N. В графе нет повторяющихся рёбер, а также нет рёбер, соединяющих одну вершину саму с собой. Граф из 0 вершин не считается корректным. Вот и сейчас, посмотрев на массив из K чисел, Валя ищет там неориентированные графы, за- данные именно таким форматом. Посчитайте, сколько непрерывных подпоследовательностей чисел в этом массиве задают граф вышеуказанным способом. Формат входных данных В первой строке дано целое число K — количество чисел в массиве (1 6 K 6 100 000). Во второй строке дан массив из K целых неотрицательных чисел, записанных через пробел. Числа не превосходят 1 000 000 000. Формат выходных данных Выведите целое число — количество подотрезков массива, которые задают корректный граф по правилам, описанным в условии. Пример стандартный ввод стандартный вывод 12 2 2 2 2 1 1 2 1 2 1 0 0 3 Замечание В примере из условия есть три корректных записи графа: «2 1 1 2», «2 1 2 1» и «1 0». Первые две записи соответствуют графу с двумя вершинами и одним ребром, третья запись — пустому графу с одной вершиной. Страница 9 из 13 Уральская командная олимпиада по программированию 2021 Екатеринбург, Россия, 7 ноября 2021 года Задача I. Собеседование Имя входного файла: стандартный ввод Имя выходного файла: стандартный вывод Ограничение по времени: 1 секунда Ограничение по памяти: 256 мегабайт Летом Вася стажировался в компании «Яндекс». На финальном собеседовании ему дали следу- ющую задачу. Есть некоторая прямоугольная матрица с n строками, m столбцами. Значения в клетках — неотрицательные целые числа. Про нее известны суммы чисел по строкам — r i и столбцам — c j , а сами значения в клетках неизвестны. В матрице выбрали клеточку в a-й строке и b-м столбце и просят узнать: сколько возможных значений в ней может быть написано? Но так как это финальное собеседование, то задача конечно же проверяет, что кандидат не верит всему, что попало. Так и в этой задаче матрицы с такими значениями r i и c i может не существовать. Тогда, естественно, ответ на задачу 0. Как вы понимаете, Вася справился с этой задачей. А вы сможете? Формат входных данных В первой заданы целые числа n и m — число строк и столбцов в матрице (1 6 n, m 6 10 3 ). Во второй строке заданы целые числа a и b — номер строки и столбца выбранной клетки (1 6 a 6 n, 1 6 b 6 m). Строки нумеруются от 1 до n, столбцы — от 1 до m. В третьей строке через пробел перечислено n целых чисел r 1 , . . . , r n , где r i — сумма чисел в i-й строке матрицы (0 6 r i 6 10 9 ). В четвертой строке через пробел перечислено m целых чисел c 1 , . . . , c n , где c j — сумма чисел в j -м столбце матрицы (0 6 c j 6 10 9 ). Формат выходных данных Выведите единственное число — количество возможных значений в выбранной клетке. Примеры стандартный ввод стандартный вывод 1 2 1 1 15 5 10 1 2 2 2 2 10 15 12 13 11 Страница 10 из 13 Уральская командная олимпиада по программированию 2021 Екатеринбург, Россия, 7 ноября 2021 года Задача J. Букмекер Имя входного файла: стандартный ввод Имя выходного файла: стандартный вывод Ограничение по времени: 1 секунда Ограничение по памяти: 256 мегабайт Вы будете удивлены, но в мире существуют турниры по игре «Четыре в ряд». Её правила доволь- но просты: в неё играют два игрока на поле размером 7×9 с 7 строками и 9 столбцами, которое стоит на столе вертикально. Игроки по очереди кидают фишки своего цвета в один из девяти столбцов, эта фишка падает на самую низкую незанятую позицию в столбце. Когда в столбце будут нахо- диться все семь фишек, в этот столбец нельзя больше ничего закинуть, но можно пропустить ход, условно делая ход в этот столбец, на что тратится одна фишка. Игра заканчивается в тот момент, когда после хода одного из игроков найдутся четыре позиции в одном столбце, в одной строке или по диагонали подряд с фишками одинакового цвета, тогда игрок, который ходил последним, явля- ется победителем. Если же все 63 фишки оказались потраченными, однако не один из игроков не победил, то результатом этой игры становится либо ничья, если заполнено всё поле, либо открытый конец, если остались свободные поля. Профессионалы игры «Четыре в ряд» играют очень быстро, а чтобы провести необходимый анализ игры после, на каждом матче присутствует писарь, который записывает каждый ход игроков. Понятно, что в любой момент игры возможно сделать не больше девяти возможных ходов, каждый из которых в записи обозначается номером столбца, куда была кинута фишка или где был пропущен ход. А для удобства писари пишут все ходы игроков в одну строку. В финале чемпионата мира играют два величайших игрока поколения — Парвиз и Воропше. Начинающий букмекер Вадим принимает ставки только на победу одного из двух игроков, при победе Парвиза, который будет начинать, он отдаст все деньги в пропорциональном отношении тем, кто поставил на него, при победе Воропше — тем, кто поставил на него, а при ничьей весь банк остаётся у букмекера. Профессиональная игра не может закончиться открытым концом, так как при этом оба игрока дисквалифицируются. К сожалению, Вадим проспал этот матч, а деньги нужно возвращать. Или не нужно? Вадим нашёл запись матча писарем, но она оказалась очень странной. Каким-то образом писарь записал в одну строку как все матчи и разминки, которые проводились в этот день, так и просто случай- ные ходы заскучавших игроков. Чтобы правильно распорядиться деньгами, Вадиму нужно срочно определить, сколько подстрок этой строки являются записями победы одного из игроков, и сколько являются записями ничьих. Его не интересует, кто победил при этом в матче, потому что при побе- де все деньги уйдут изначальным бетторам, а при ничьей Вадим хорошо заработает. Также ему не интересны игры с открытыми концами, потому что их не могло произойти в этом матче. Помогите Вадиму, и, быть может, он поделится с Вами кусочком пирога. Или торта. Формат входных данных В единственной строке даётся строка длины N из цифр от «1» до «9» без пробелов — запись всех ходов писарем (1 6 N 6 10 4 ) Формат выходных данных Выведите два целых числа через пробел — количество подстрок данной записи, являющихся победой одного из игроков, и количество подстрок данной записи, являющихся ничьёй. Пример стандартный ввод стандартный вывод 34353637 2 0 Замечание В игре «3435363» побеждает первый игрок, выстроив 4 фишки подряд в третьем столбце; в игре «4353637» также побеждает первый игрок, выстроив 4 фишки подряд в нижней строке; никакая другая подстрока не является законченной игрой. Страница 11 из 13 Уральская командная олимпиада по программированию 2021 Екатеринбург, Россия, 7 ноября 2021 года Задача K. Обер-форшнейдер Имя входного файла: стандартный ввод Имя выходного файла: стандартный вывод Ограничение по времени: 1 секунда Ограничение по памяти: 256 мегабайт Вадим обожает треугольники так сильно, что при виде любого выпуклого многоугольника он разрезает его на треугольники, поэтому он называет себя современным обер-форшнейдером. Поре- зать многоугольник на треугольники можно невероятно большим количеством способов, но самые элегантные из них — это те, в которых все разрезания — это непересекающиеся диагонали исходного многоугольника. Сегодня у мамы Вадима день рождения, в честь чего он подарил ей торт, который является выпуклым многоугольником. Сразу же Вадим вызвался поработать ножом, чтобы элегантно разде- лить весь торт на кусочки-треугольники. Поскольку Вадим не любит сладкое, в конце он выберет себе самый маленький по площади кусочек, однако он не хочет, чтобы кто-то это заметил. Для этого современному обер-форшнейдеру нужно подобрать такой способ элегантно разделить торт, чтобы часть, которая достанется ему, была наибольшего размера. Помогите Вадиму найти эту площадь. Формат входных данных В первой строке дано единственное целое число N — количество вершин многоугольника (3 6 n 6 200). В каждой из следующих N строк через пробел даны по целых два числа x i , y i — координаты вершин многоугольника в порядке обхода против часовой стрелки (−10 8 6 x i , y i 6 10 8 ). Гарантируется, что многоугольник выпуклый. Формат выходных данных В единственной строке выведите искомую площадь кусочка Вадима. Ответ будет засчитан, если абсолютная или относительная погрешность числа не превосходит 10 −9 . Формально, пусть ваш ответ равен x, а ответ жюри равен y. Ваш ответ считается правильным, если |x−y| max(1,|y|) 6 10 −9 Пример стандартный ввод стандартный вывод 4 0 0 5 -1 8 3 0 4 11.5 Страница 12 из 13 Уральская командная олимпиада по программированию 2021 Екатеринбург, Россия, 7 ноября 2021 года Задача L. Круглый стол Имя входного файла: стандартный ввод Имя выходного файла: стандартный вывод Ограничение по времени: 1 секунда Ограничение по памяти: 256 мегабайт Сидели за круглым столом с пометкой царь и три его сына: старший, средний и младший. И сказал царь, что в наследство он отдаст половину своего царства тому из сыновей, который сидит ближе всего к нему, а если два сына сидят на одинаковом расстоянии от него, то старшему из них. Оставшуюся половину царь решил поделить пополам между двумя остальными сыновьями. Кому же достанется половина царства? Формат входных данных В четырёх строчках вводятся четыре целых числа 0 6 k, o, m, y 6 359 — размер ориентированно- го угла в градусах против часовой стрелки от пометки через центр стола до короля, старшего сына, среднего сына и младшего сына. Гарантируется, что все числа во вводе различные. Формат выходных данных Выведите «Oldest», если половина царства достанется старшему сыну, «Middle», если достанется среднему и «Youngest», если младшему. Пример стандартный ввод стандартный вывод 180 120 225 90 Middle Замечание Пояснение к примеру: Страница 13 из 13 |