А. Футбол.
Эту задачу можно решить, не расходуя лишнюю память, а заведя лишь две строки для хранения названий первой и (возможно) второй команд и две целочисленные переменные для хранения количества голов, забитых первой и второй командами. Считываем название первой команды, запоминаем в первой строке и идем циклом до 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).
Comments (0)
