removed1's blog

By removed1, 14 years ago, In Russian

Так получилось, что пока я писал это, Иван уже выложил свой. Я тогда тоже выложу -- может быть кому-то будет полезно.

Задача А.

В общем решение достаточно прямолинейно, нужно только внимательно выполнить то, что написано в условии. Ситуация осложняется наличием отрицательных выигрышей за кон (т.е. кто-то может получить большое количество очков, а потом проиграть). Проще всего с этим справиться, пройдясь два раза по данным. В первый заполним структуру вида
map<string,int> finalscore;
и найдем количество очков у победителя. Во второй раз обновляем структуру
map<string,int> currentscore;
и как только у кого-то с finalscore[id]==winner_score станет currentscore[id]>=winner_score, то он победил.
Ничьих не бывает.

Задача В.

Десятичная запись числа содержит один ноль, если это число само равно нулю, в противном случае -- минимальное из количеств двоек и пятерок в разложении его на простые множители. (2*5=10, а остальные множители нас не интересуют).
Если матрица содержит ноль, то он всегда достижим из начальной клетки, а все пути, содержащие ноль, одинаково оптимальны (1).
Поэтому, отметив наличие ноля, мы можем избежать отдельного рассмотрения этой клетки в общем случае -- назначив "штраф" -- достаточно заменить ноль десяткой: если мы и пройдем через место, где должен быть нуль, а есть десятка, не можем получить более оптимальный маршрут. Сами пути без нулей сложнее. Прямое применение динамического программирования в лоб к успеху не приведет, т.к. по пути может попасться до 1999*12 пятерок или до 1999*29 двоек, и массивы слишком велики. Решение за O(N^2) достигается, если найти отдельно путь, минимизирующий число двоек, и путь, минимизирующий число пятерок, и выбрать из них лучший. Докажем что это так. Пусть минимизируя число двоек, получили путь с 'a' двоек и 'b' пятерок, а минимизируя число пятерок, получили 'c' двоек и 'd' пятерок (мы не считаем на самом деле множители, которые не минимизируем, это надо только для доказательства). Если a<=d, то 'b' не влияет на ответ: в силу минимальности 'd' выполняется b>=d и таким образом b>=a, ответ: 'a'. Случай d<=a полностью симметричен.

Каждый путь находится с массивом
m[строка][столбец]=количество двоек(пятерок), которые мы "собрали" по пути в клетку с данными координатами.
Т.к. памяти достаточно, то можно завести отдельный массив, в котором для клетки хранится направление, по которому мы в эту клетку пришли -- это значительно упростит код составления маршрута.

Задача С.

Угол, под которым виден стадион, равен 2*asin(r/rho), где r - радиус стадиона, rho -- расстояние от точки взора до центра стадиона (окружности). Поэтому, задачу меняем на эквивалентную: отношения расстояний от искомой точки до стадионов должны быть пропорциональны радиусам стадионов => квадраты расстояний пропорциональны квадратам радиусов стадионов. Если все радиусы равны, то мы получаем задачу нахождения центра окружности по трем точкам. Если нет -- рассмотрим множество точек, отношения расстояний от которых до двух данных (соответственно (0,0) и (d,0) ) постоянно:
((x - d)^2 + y^2 )/ r1^2 = (x^2 + y^2) / r2^2
Обычно это окружность со сдвинутым центром. Она окружает тот стадион, у которого радиус меньше. Если r1==r2, то это прямая -- вырожденный случай окружности :-) Таким образом три стадиона порождают три окружности (одна или три из которых могут быть прямыми), а ответ -- если он существует -- является пересечением этих трех фигур. Проще анализировать пересечение двух фигур, а получив две точки, нужно проверить их правильность -- подстановкой; если обе корректны, то выбрать ту, которая ближе к любому стадиону. Чтобы не писать отдельно случай пересечения линии с окружностью, можно всегда выбрать (поменяв индексы) пересечение двух окружностей. Две окружности в общем случае либо не пересекаются (тогда ответа нет), либо пересекаются в двух точках. Случай, когда они совпадают, невозможен (условие задачи), а если они касаются -- то мы по формулам получим две точки.




  • Vote: I like it
  • +1
  • Vote: I do not like it