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

Автор caustique, 14 лет назад, По-русски

А. Футбол.


Эту задачу можно решить, не расходуя лишнюю память, а заведя лишь две строки для хранения названий первой и (возможно) второй команд и две целочисленные переменные для хранения количества голов, забитых первой и второй командами. Считываем название первой команды, запоминаем в первой строке и идем циклом до n - 1. На каждом шаге если считанная строка совпадает с уже имеющейся (первой строкой - она всегда есть, так как мы ее заранее (до цикла) считали), то увеличиваем счет этой команды, иначе запоминаем название второй команды и увеличиваем ее счет. В конце делаем целочисленное сравнение и выводим одну из строк.
Заметим, что даже если вторая строка останется неинициализированной, ничего плохого не произойдет, так как мы к ней никогда не общаемся, кроме случая, когда победила вторая команда (значит, у нее ненулевое количество голов и строку мы все-таки инициализировали).

B. Письмо.


Известно, что символы из таблицы ASCII, к которым относятся все (строчные и заглавные) латинские буквы и пробел, имеют коды от 0 до 127. Значит, достаточно завести два массива на 128 символов (можно узнать требуемую память точнее, но char занимает 1 (или 2 байта в Java), поэтому это непринципиально), инициализированных нулями, и заполнить каждый из них следующим образом: идем циклом по строке, получаем код текущего символа строки, элемент массива с таким индексом (кодом символа) увеличиваем на единицу. Таким образом получим два массива - один для первой строки и один для второй. Чтобы составить вторую строку, нужно, чтобы выполнялось условие b[i] <= a[i] для всех i от 0 до 127, кроме (char)i == ' '. Пробелы вырезать ненужно, поэтому для них неравенство может не выполняться.

С. Счастливые билеты.


Признак делимости на три говорит нам, что натуральное число делится на три тогда и только тогда, когда сумма его цифр делится на 3. Для каждого кусочка билетика мы можем посчитать остатки от деления этого числа на 3 - 0, 1 или 2. Обозначим количество билетов первого типа - a, второго типа -  b, третьего - с. Счастливые билетики можно составить двумя способами: либо соединить кусочки с остатками от деления 0 и 0, либо - 1 и 2. Тогда сумма чисел на получившемся билетике будет 3, что и требуется. Ответом будет число a / 2 + min(b, c). Оставшиеся a % 2 + max(a, b) - min(a, b) билетиков придется выкинуть, так как для них нет соответствующей пары.

D. Путешествие


Сперва заметим, что в оптимальном решении может быть не более одного телепорта. Таблицу n * m можно обойти несколькими способами, перемещаясь только по соседним клеткам - например, змейкой или спиралью. Далее, из последней клетки, в которую мы пришли при обходе таблицы, можно телепортироваться в первую.
В этой задаче нужно было рассмотреть 4 случая:
1. n * m = 2 - тогда ответ легко выписать вручную
2. n = 1, m > 2; n > 2, m = 1 - идем по полоске до конца, а из последней клетки ((1, m) или (n, 1)) телепортируемся в первую
3. оба n и m нечетные (ни одно из чисел не равно 1) - тогда нужна одна телепортация: обходим доску одним из предложенных способов: змейкой (вверх-вниз или вправо-влево) или по спирали - а из последней клетки телепортируемся
4. хотя бы одно из чисел четное, а другое не равно единице - тогда идем вдоль четной стороны до края таблицы, а оставшуюся часть обходим змейкой + делаем один завершающий ход.
Для пояснения пункта 4, рассмотрим пример.
Пусть n - четное, m - нечетное (не равное 1). Тогда идем вдоль края таблицы из клетки (1, 1) в клетку (n, 1). Дальше возвращаемся в клетку (1, 2) следующим образом: если текущая строка i четная - идем вправо от 2 до m, иначе идем влево от m до 2. Заметим, что последней строкой, которую мы так пройдем, будет первая (по номеру), то есть мы действительно закончим в клетке (1, 2). Осталось сделать только заключительный ход в (1, 1).
Разбор задач Codeforces Beta Round 42 (Div. 2)
  • Проголосовать: нравится
  • -1
  • Проголосовать: не нравится

14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Может 42
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
В задаче D в пункте 2, если я не ошибаюсь, четность n или m не важна.
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Да, действительно. Ну вообще это помещается в ниже описанный случай 3, но я исправлю)
»
12 лет назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

== Утверждение оказалось ошибочным :-( Разбор по С неправильный. Там нужно учитывать куски с нулями в начале. Например из 05 и 04 билетика не составишь

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

    Почему не составишь?

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

      Упс... Сдал без нулей — не прошло, потом добавил нули — прошло. Но оказалось — ошибка не в этом.

      Сорри.