Блог пользователя ivan.popelyshev

Автор ivan.popelyshev, 14 лет назад, По-русски
Начнём с конца.

Задача С. Commentator problem

Пусть R это расстояние из точки А до какой-то окружности с центром в О и радиусом r. Тогда из точки окружность видна под углом .
Таким образом три стадиона видны под одним углом если R1 / r1 = R2 / r2 = R3 / r3.
Возьмём две различные точки A, B. Множество точек C таких что AC / BC = const является либо прямой - серединным перпендикуляром AB, либо окружностью с центром где-то на прямой AB, которую легко вычислить по двум точкам лежащим на прямой AB для которых выполняется условие на AC / BC.
Положим X1 это множество точек из которых под одним углом видны стадионы 1 и 2, а X2 определим аналогично только для стадионов 2 и 3. Понятно что ответ принадлежит пересечению X1 и X2. Поскольку центры всех трёх стадионов не лежат на одной прямой то кол-во точек в пересечение X1 и X2 будет конечным.

Проверим их все: искомая точка должна быть ближайшей к какому-либо из стадионов. Так как стадионы не пересекаются, то такая точка не будет лежать внутри стадиона.
Как получить большую окружность для множества X1: поместим центры стадионов в точки находящиеся далеко, например (0, 0) и (1000, 0). Отношение радиусов стадионов должно быть как можно близким к 1, например . центр и радиус новой окружности будут иметь порядок 106 Ответ надо знать с точностью до 10 - 5. Грубо говоря, нужно 11 знаков, типа double точно хватит.

Очень интересно узнать на чём валились решения этой задачи.

Задача B. Наименее круглый путь

Решим задачу для случаев где матрица вся положительная.
Пусть в конце мы получили положительное число N = 2k· 5m·(другие простые). Количество нулей на конце N равно min(k, m). С помощью динамики найдём наименьшее возможное значение k (пусть это k1 ) и наименьшее значениe m (соответственно m1), а также пути приводящие к этим значениям. если k1 < m1 то выберем путь соответствующий k1, иначе m1.
Таким образом, min(k, m) это верхняя оценка ответа. Докажем что это и нижняя оценка. Пусть существует путь приводящий к числу с количеством нулей меньшим чем min(k, m). Тогда в разложении получившегося числа либо показатель степени при двойке k < k1 либо показатель степени при пятёрке k < k2. Получили противоречие.
Значит, достаточно получить показатели степеней 2-ек и 5-ок в каждом числе и прогнать на двух получившихся матрицах динамику.

В случае если в матрице присутствуют нули, надо отдельно посчитать пути проходящие через них и не проходящие.
Заменим все 0 на 10 и используем метод описанный выше, при этом для путей проходящих через нули мы будем получать результат с как минимум одним ноликом на конце. Если метод вернул путь с результатом без ноликов на конце, то он является ответом. Иначе можно взять любой путь проходящий через нолик.

Итого сложность алгоритма зависит только от сложности динамики, то есть это O(N· M).

Задача А. Победитель

Простая задача на реализацию.
За первый проход считаем сумму очков каждого игрока в конце игры. Пусть M - максимум среди сумм. Далее заново проходим по конам. Если в каком-то кону очки игрока X стали не меньше M и в конце игры X будет иметь M очков то выводим ответ и выходим из программы.
Следующий тест иллюстрирует тот факт что игрок может набрать больше M очков, затем слить часть очков а в конце победить.
Input:
Masha 12
Masha -5
Sasha 10
Masha +3
Output:
Masha


Разбор задач Codeforces Beta Round 2
  • Проголосовать: нравится
  • +12
  • Проголосовать: не нравится

14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Спасибо, Иван. Переведешь?
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Раз уж взялся, то переведу сегодня или завтра, но я ещё редактировать её буду.
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    а есть ли теперь смысл переводить? :)
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Переведи, я его тоже на главную поставлю - у вас с Андреем тексты вполне себе различаются.
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Кто там ответственен за ТеХ? почему у меня полразбора курсивом выделено? :(
14 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
Excellent tutorial !! Would like to see more from you... 
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Can somebody help me?
I have WA 2 in problem C
Please, give me some test :) thanks
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Test: #2, time: 30 мс., память: 1312 Кб, exit code: 0, checker exit code: 1, verdict: WRONG_ANSWER 
    Ввод 
    0 0 10 
    100 100 10 
    200 0 20 
    Вывод 
    72.57081 27.42919 
    Ответ 
    60.76252 39.23748 
    Checker Log 
    wrong answer Wrong position
  • 13 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится
    If you click number in line of your submission you can see testing log.
»
11 лет назад, # |
  Проголосовать: нравится -17 Проголосовать: не нравится

task B, submission #3726143, I got:

Test: #31, time: 3421 ms., memory: 172 KB, exit code: 0, checker exit code: 1, verdict: WRONG_ANSWER
...
Checker Log
wrong answer Jury has better answer: ja=1 vs pa=2974

Can I see what concrete input was in this test to find the reason? And who is Yuri? ))

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

could someone help me with the problem B, please ?

here's my code: http://ideone.com/1Juljl

thanks in advance :)

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

why problem B is O(n*m)? isn't it o(n*n)?

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
»
4 года назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

[Solved]

»
4 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

In problem B if the input is

3

1 2 3

4 5 6

7 8 9

can one solution could be RRDD too?

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Yes, I think so. Usually in the problem statement, it says "if there are more than one such path, print any possible path." I don't know why they didn't say it in this problem.

»
3 года назад, # |
Rev. 4   Проголосовать: нравится +10 Проголосовать: не нравится

Problem A)

Failing test case 10 W.A Can anybody please help me ?

my submission link is here — https://codeforces.com/contest/2/submission/94976880


int n; map<string, int> score_board; map<int, vector<string>> rev_board; void solve() { cin >> n; for(int i=0; i<n; ++i) { string name; int score; cin >> name >> score; score_board[name] += score; rev_board[score_board[name]].push_back(name); } auto it=rev_board.end(); --it; cout << it->second[0]; }