Всем привет
Сегодня автор большинства задач - Дмитрий Жуков, за что ему огромное спасибо.
Так же хочу поблагодарить Михаила Мирзаянова за выбор задач на раунд и организацию контеста и Юлию Сатушину за перевод условий.
Удачи!
UPD:
- Задачи
- Результаты
- Победитель: saeedreza.seddighin
задача
основная / главная задача — the main / chief task
очередная задача — immediate task / goal
поставить задачу перед кем-л — set / give smb a task
(по)ставить перед собой [себе] задачу (+ инф.) — set oneself the task (of ger); undertake (+ to inf); undertake the task (of ger); take it upon oneself (+ to inf)
цели и задачи — objectives and goals
нелёгкая задача — not an easy job to do
тактическая задача (учебная) — tactical scheme
решить задачу — solve a problem; (арифметическую) do a sum
задача на сложение [вычитание, деление, умножение] — addition [subtraction, division, multiplication] sum
научная задача — scientific problem
-First , construct a full graph .
-Then remove a random Edge from the current graph . Two vertices of this edge have a degree of n-2, and the remaining edges have a (n-1)-degree. So we have the answer.
Да, мне тоже задача С показалась очень интересной, и я, к сожалению, ее не решил. Еще, немного обидно, что задача В оказалась чисто математической (или у нее есть еще алгоритмическое решение?). Там кода получается меньше, чем в А, в то время как по сложности они, по-моему, не сравнимы. А остальные, судя по таблице результатов, оказались намного труднее.
Но вообще, понятное дело, что составлять задачи не так-то просто; куда проще говорить, понравились они или нет) Так что в любом случае большое спасибо за контест. Так или иначе, было интересно)
sigh , I was trapped in Problem B for a long time
It seems so hard for me!!!
Почему нет разброса-то во времени у контестов, я хочу написать хоть один :о) Давайте попозже проведем на часик парочку :о)
Задача Е мне понравилась и C.
А D сдается тернаркой? Или там нормально можно все посчитать?
Lets number the midpoints 0, 1 and 2 and assume that 0 is the midpoint of the side that is equal to both of its neighbors. We know that we have a polygon vertex lying on the symetral of 0, 1. I do binary search for this point A. For each candidate I do symmetry according to 0 and thus get point B. I have made the obvious observation that initially the points on the symetral of 0, 1 give us points B that are further away from 2 than 0, and then they become closer to 2. we are in fact interested in the moment in which the distances to 0 and 2 get equal. This allows us to make binary search.
After we finish the binary we have two of the vertices of our polygon. What is left is to do 2 more symmetries and check whether the obtained polygon complies to all requirements.
As a final note - in the beginning we assumed 0 is the center of the mid equal segment but in fact every of the three vertices can be that one. So we need to try all three possibilities to make sure no solution exists.