Блог пользователя KAN

Автор KAN, история, 8 лет назад, По-русски
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
  • Проголосовать: нравится
  • +77
  • Проголосовать: не нравится

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

задача 729E — Подчинённые Что делать с нулями если их будет больше одного

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

    Просто заменить 0 на n, кроме стартовой конечно

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

      СПАСИБО

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

      5 1 0 0 1 1 1

      Заменяя второй ноль на 5 в данном случае мы имеем 5 1 0 5 1 1 1 итого ответ будет 2, Хотя можно было заменить на 1 или 2 и ответ был бы 1.

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

        замены 0 на n не нужно прибавлять к ответу. мы меняем просто для удобства, они потом поменяются на что иное

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

Очень надеюсь, что "Скоро будет!" — не пустые слова. По поводу задачи F первого дивизиона.

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

Обьясните кто-то решение Д, я что-то не понял написаного в разборе

  • »
    »
    8 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +12 Проголосовать: не нравится

    Мне понравилась вот эта идея.

    То есть сперва мы приводим состояние поля к такому, что в него не возможно поместить корабли вообще. После этого мы потихоньку удаляем наши выстрелы по одному, пока на поле не поместится a - 1 кораблей.

    22390165

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

"Will be translated soon": Waiting for translation...

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

should be inside the maximum function.

Similarly, for zhenya.

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

Any idea why my submission for 729C http://mirror.codeforces.com/contest/737/submission/22410492 is exceeding time limit (on test #9). Please help to check.

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

Can someone please suggest some reading materials for learning graph matching? =)

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

For problem C, I do not understand the following statement:

if x ≤ f, then it is possible to ride in the fast mode min(x, f - x) kilometers.

How did you obtain the expression min(x,f-x) kilometers?

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

    Let the number of km in fast mode be k. Then the number of km in slow mode in x — k. So, we have the equation: Fuel used = 2*k + (x — k) <= f -> k + x <= f. Therefore, k <= f — x. Also, k <= x because we stop when we reach the next station. Therefore, k = min(x, f-x).

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

I had some trouble understanding Div2 D solution, so I'll explain it in more details.

The solution is actually an application of the pigeonhole principle.

Let s be the maximum number of positions where you can place a ship (of course, already considering those k misses of the input). The trick: reduce the problem to its complement! In other words: what is the maximum number of misses we can still make? The answer: m = s - a. If we shoot m ship slots once, an additional shot will hit some slot a second time (by the pigeonhole principle), or will hit a ship. So if we choose m + 1 distinct ship slots to be shot once, at least one of the shots will hit a ship.

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

In Financiers Game, shouldn't the "difference between the sum" mean the absolute value of the differences?