TopCoder SRM 473. Уроки

Сегодня ночью была очередная SRM’ка. Как водится, я узнал сам про себя много нового. Например, я изобрел совершенно уникальный и доселе невиданный метод решения линейной системы из двух уравнений.

Итак, по порядку. Дивизион 2, 75 минут, 3 задачи + 10 минут после на взлом (challenge) чужих решений.

Задача номер 1.

Есть набор куриц и коров. У каждой курицы две ноги и одна голова. У коровы четыре ноги и одна голова. Даны два числа: количество ног и количество голов (каждое число от 1 до 10^6). Надо ответить на вопрос: возможно ли существования некоторого количества куриц и коров при заданном количестве ног и голов.

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

Все просто. Но! В два часа ночи я родил иной подход: перебор! (для системы-то из двух линейных уравнений). Я даже помню ход свох мыслей: так как количество только 10^6, значит можно перебрать все возможные значение количество куриц. Для каждого значения вычислить количество коров, исходя их количество ног и из количество голов. Полученные значения сравнить, и если совпадают, значит найдено возможное решение.

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

Кстати, решение в итоге не прошло системных тестов. И к лучшему.

Задача номер 2.

Дано неограниченное поле, в некоторой точке которого стоит робот. Дана программа для робота – строка, каждый символ которой – команда: «S» - шаг вперед на какую-то константную величину, «L» - поворот налево, «R» - поворот направо. Требуется сказать, будет ли траектория робота, двигающего по этой программе, ограничена конечной окружностью, или робот будет постоянно удалятся от исходной точки. Длина программы для робота до 250 символов.

Как один из вариантов решения: можно прогнать 4 итерации программы, и если хотя б после одной, робот вернется в исходную точку, то траектория робота ограничена.

Решение есть. Теперь его надо запрограммировать. Надо было сделать имитацию выполнения программы, то есть команды робота «вперед», «влево» и «вправо».

Приведу фрагмент программы, которую родил мой воспаленный мозг ночью:

...
      if (cmd == 'S') { 
        x += dx; 
        y += dy; 
      } else { 
        if (cmd == 'L' && dx ==  0 && dy ==  1) dx = -1, dy =  0; 
        else if (cmd == 'R' && dx ==  0 && dy ==  1) dx = +1, dy =  0; 
        else if (cmd == 'L' && dx ==  1 && dy ==  0) dx =  0, dy =  1; 
        else if (cmd == 'R' && dx ==  1 && dy ==  0) dx =  0, dy = -1; 
        else if (cmd == 'L' && dx ==  0 && dy == -1) dx =  1, dy =  0; 
        else if (cmd == 'R' && dx ==  0 && dy == -1) dx = -1, dy =  0; 
        else if (cmd == 'L' && dx == -1 && dy ==  0) dx =  0, dy = -1; 
        else if (cmd == 'R' && dx == -1 && dy ==  0) dx =  0, dy =  1; 
...

Даже сейчас я не могу смотреть на это без содрогания. Надо то было всего:

...
int dx[4] = { 0, 1, 0, -1 };
int dy[4] = { 1, 0, -1, 0 };
int d = 0;
...
if (cmd == ‘S’) {
  x += dx[d];
  y += dy[d];
} if (cmd == ‘L’)
  d = (d + 4 - 1) % 4;
else if (cmd == ‘R’)
  d = (d + 1) % 4;
...

И все!

Но увы. Когда время ограничено, на ум приходят странные решения.

Хотя мое решение прошло системные тесты, от его вида как-то грустно.

Задача 3.

Дано определение числа Y: Y = X/D(X). X – натуральное число, D(X) – сумма цифр в десятичной записи числа Х. Если Y получается целым, то читается, то Y есть «предок» числа X. Дан интевал чисел от «а» до «b» (каждое от 0 до 10^9), но «a-b» всегда не более 10000.

Спрашивается, сколько есть на данном интервале есть числе Y, у которых нет предка (то есть нет такого Х, чтобы Y был целым).

Итак, для решение перебираем все значения Y от «а» до «b» (их не более 10000). Для каждого Y числа надо проверить, если ли у него «предок». Ясно, что заменатель D(X) принимает только значения от 1 до 81 (число с максимальной суммой цифр – это 999999999, а их сумма 81). Итак, делаем внутренний цикл от 1 до 81, и вычисляем X как X=Y*i (i от 1 до 81). Далее по факту равенста i и D(X) (надо вычислить сумму цифр, составляющих текущее X) можно понять, если ли у текущего Y предок или нет.

Всего итераций будет максимум 10^4 * 81 * 9 ~= 10^6 = 1000000, что вполне реально.

Но эту задачу я засабмитить уже не успел, хотя ее решение у меня было в голове.

Итак, выводы.

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

Заснуть под утро я так уже не смог. Все думал.