NALP's blog

By NALP, 12 years ago, In Russian

257A - Sockets

Очевидно, что выгоднее использовать сетевые фильтры с наибольшим количеством розеток на них. Поэтому сначала отсортируем их по убыванию этой величины. Теперь переберем ответ, то есть, сколько фильтров мы будем использовать, пусть это значение равно p, а фильтры имеют a1, a2, ..., ap розеток. Очевидно, что если соединить эти фильтры, то итого будет доступно k - p + a1 + a2 + ... + ap розеток. Это значение надо сравнить с m и выбрать минимальное подходящее p. Если ни одно значение p не подходит, то следует вывести  - 1.

257B - Playing Cubes

Для начала переберем цвет первого кубика, который поставит Петя. Вася следующим ходом захочет поставить кубик противоположного цвета, затем Петя захочет поставить кубик такого же цвета, как и поставленный Васей и т.д. Так мы можем проэмулировать всю последовательность ходов обоих мальчиков и найти их счет.

Единственное, что может изменить Петя в игре – это цвет первого кубика, и он его поставит так, чтобы его счет был как можно больше.

257C - View Angle

Сначала давайте избавимся от координат точек, а именно, заменим все точки лучами от (0, 0) до каждой из точек.

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

Отдельный случай — когда все точки лежат на одном луче, в этом случае ответ равен 0.

257D - Sum

У нас есть последовательность переменных a1, a2, …, an. Возьмем две переменные с максимальными значениеми (допустим, i и i + 1), удалим их и вставим в последовательность новую переменную x = ai + 1 - ai так, чтобы сохранилось свойство неубывания последовательности. Так будем делать до тех пор, пока не останется единственное число s, которое и будет искомой суммой. Очевидно, что если мы будем разворачивать последовательность замен с учетом знаков, то в итоге узнаем, какой знак стоит у каждой из начальных переменных так, чтобы их сумма была равна s.

Теперь осталось понять, почему число s подходит под ограничения 0 ≤ s ≤ a1. Очевидно, что оно не может быть отрицательным, так как при всех заменах мы из большего числа вычитаем меньшее. Также несложно понять, что при всех заменах минимальное число в последовательности не может увеличиваться, значит, оно до последней замены будет максимум a1. Аналогично, второе число в последовательности также не может перед последним шагом быть больше a2 и так далее. Несложно понять, что при последней замене мы получим s ≤ a2 - a1 ≤ a1.

257E - Greedy Elevator

Эта задача решается классическим методом – событиями во времени. Событиями являются: «человек встал в очередь к лифту», «человек вошел в лифт», «человек вышел из лифта».

Будем поддерживать множество будущих событий, текущее время T и текущее положение лифта x.

В каждый момент времени будем выполнять следующие действия:

  1. если есть люди, которые в текущее время T пришли к лифту, то поставим их в очередь на их стартовом этаже;
  2. если на текущем этаже есть люди, то посадим их в лифт, таким образом очередь на этом этаже опустеет;
  3. если в лифте есть люди, которые должны выйти на текущем этаже, то высадим их и запомним для них ответ – текущее время T;
  4. найдем количество людей, которые ждут выше этажа x или которые едут выше, а также найдем количество людей, которые ждут ниже этажа x или едут ниже, и согласно условию выберем направление движения.

Однако если мы на каждой итерации будем увеличивать текущее время T лишь на единицу, то решение будет работать слишком долго. Надо научиться переходить сразу к следующему моменту времени, когда появится какое-либо новое событие, и лифт передвигать сразу на несколько этажей вверх или вниз. Очевидно, что между событиями направление движения лифта не меняется.

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

Это можно сделать с помощью структуры «множество» с операциями «найти следующее число в множестве после данного» и «найти предыдущее число в множестве перед данным». Это умеет стандартные структуры set в С++ или TreeSet в Java.

Также для действия номер 4 нам понадобятся две структуры данных, которые умеют находить сумму чисел на определенном отрезке в массиве, для этого можно использовать, например, деревья отрезков или деревья Фенвика. Одна из структур хранит, сколько людей ждут лифта на каждом из этажей, а вторая – сколько людей в лифте хочет выйти на каждом из этажей. В принципе, эти две структуры можно объединить в одну.

Таким образом, для каждого из людей мы будем обрабатывать ровно по три события, и итоговое время решения будет равно O(n·log(n)).

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

»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can you check my solution for problem C? http://mirror.codeforces.com/contest/257/submission/2892972 I have wa6, but don't understand whats wrong. Thanks a lot.

»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi, the answer of problem B is max(red,blue)-1 and min(red,blue), how to prove it ? thx !

  • »
    »
    11 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    petya first turn is only wasted, in all the later turns both will keep on taking points but when any one of the color dice is over , vasya cannot win points anymore. Indeed later every turn will give points to petya, since there is only single color dice. NOTE: only first dice is wasted

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think this is wrong as it fails on the test 2 3
    The final sequence looks like this: RBBRB so answer should be 1 3 whereas by your algo answer would be 2 2

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      No, the final sequence looks like BRRBB and the answer is indeed 2 2

»
12 years ago, # |
  Vote: I like it +1 Vote: I do not like it

English , please...

  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    In fact, you can translate the whole page into English by using http://translate.google.com

    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

      google translate: "We have a series of variables a1, a2, ..., an. Take two variables with the highest znacheniemi (say, i and i + 1)..."

      znacheniemi?

      • »
        »
        »
        »
        12 years ago, # ^ |
          Vote: I like it +14 Vote: I do not like it

        It means "values" but the original word is written incorrectly in Russian.

        P.S. The first time I see when illiteracy can really make harm.

»
12 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

257C - Угол обзора Can somebody tell me, how will I know, is this ray neighbor with something else?

  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    sort by angle

    • »
      »
      »
      12 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      I understood how decide this problem, but how will I know, is this ray neighbor with something else? Maybe between first and second rays will be others rays? So, this picture. 'alpha'- is the biggest angle, but it's wrong answer.

      • »
        »
        »
        »
        12 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        You should check all pairs of neigbors and choosethe best one.

        • »
          »
          »
          »
          »
          12 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I understood, that you said, but how i must check it, that be sure, that between this two rays i haven't others, as at the picture the rays between l1 and l2?

          • »
            »
            »
            »
            »
            »
            12 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            If ray A between B and C, then B and C aren't neighbors?

            • »
              »
              »
              »
              »
              »
              »
              12 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Yeah, if we have the other rays, that is neighbors with C and B. Maybe i just must to search the least angle for all rays, then pick the biggest from these. Is it correct?