Codeforces Beta Round #1 Разбор

Правка ru1, от Simple_Genius, 2016-01-25 16:15:58

Пожалуйста, сообщайте о любых ошибок.

1А — Театральная площадь

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

Неприятности в этой задаче заключались в основном с типизацией и приоритетом вычислений, что очень сильно зависит от стиля кодирования и языка.

A : Solution by C++

1B — Электронные таблицы

Отождестим буквенную запись столбца с числом в системе счисления с основанием 26. ('A' = 0, 'B'=1, 'Z' = 25). Тогда при переводе из буквенного обозначения в цифровое нужно к значению дополнительно добавить количество всех вариантов, имеющих меньшую длину, плюс один (ради формализма можно считать, что вариантов нулевой длины -- один, и отказаться от добавления единицы).

При переводе из цифрового обозначения в буквенное нужно сначала найти, сколько знаков понадобится и из числа вычесть количество обозначений меньшей длины (для чего последовательно вычитаем из числа количество обозначений, имеющих длину 0, потом количество имеющих длину 1, 2, и т.п., пока число не станет меньше, чем количество обозначений, имеющих текущую длину и следующее вычитание привело бы к появлению отрицательного числа), переводим в систему счисления 'A'..'Z'.

Возможна интерпретация, реализуемая более компактно, но там сложнее не допустить ошибку при реализации.

B : Solution by C++

1C — Древнеберляндский цирк

Можно разбить на две подзадачи: найти центр правильного многоугольника и найти число углов.

Центр многоугольника обязан быть на одинаковом расстоянии от трех вершин. Можно воспользоваться обычным методом нахождения центра окружности, построенной по трем точкам. Напишу метод, которым воспользовался я. Для двух отрезков (x1,y1 — x2,y2) , (x2,y2 — x3,y3) находим среднюю точку, строим перпендикуляры, пересечение их даст искомый центр. Из подводные камни здесь: некоторые формулы в некоторых частных случаях дают деление на ноль. Лежать на одной прямой три точки из условия не могут (т.к. гарантируется корректность входных данных), а оставшийся плохой случаи можно устранить поворотом всей системы (т.е. всех трех точек) на случайно выбранный угол.

Нахождение числа углов

Поскольку при равном расстоянии от центра до вершины площадь правильного многоугольника возрастает монотонно с ростом N, можно просто перебирать все N, начиная с 3, и при нахождении первого подходящего печатать ответ и прекращать работу. Нужно, следовательно, для данного N уметь определять, могут ли данные вершины быть вершинами N-угольника -- критерий прост: углы между отрезками от центра до вершин должны быть кратны 2*pi/N. Воспользуемся свойством синуса: sin(x)=0, если аргумент кратен пи. Или можно с перебором написать ! Условие кратности угла между двумя отрезками заменяется при этом на следующее:

C : Solution by C++

Теги разбор задач, codeforces beta round #1

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
ru2 Русский Simple_Genius 2016-01-25 16:37:28 51
ru1 Русский Simple_Genius 2016-01-25 16:15:58 3239 Первая редакция (опубликовано)