Задачи Южно-Уральского командного чемпионата 2010

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

Если Алиса выпьет `K` капель из найденного на стеклянном столике пузырька, то ее рост уменьшится в `K` раз, а если она откусит `L` кусочков от пирожка из коробочки под столом, то ее рост увеличится в `L` раз. Алиса может попасть в сад, только если ее рост будет строго больше `P_1/Q_1` и строго меньше `P_2/Q_2`.

Напишите программу, определяющую по ограничениям на рост, сколько капель нужно выпить Алисе из пузырька и сколько кусочков пирожка нужно съесть, чтобы попасть в сад. Начальный рост Алисы равен 1.

Первая строка ввода содержит 4 целых числа `P_1`, `Q_1`, `P_2`, `Q_2` (`1\ ≤\ P_1,\ Q_1,\ P_2,\ Q_2\ ≤\ 10^9`, `P_1/Q_1\ <\ P_2/Q_2`) – ограничения на рост Алисы.

Вывести два целых числа `K` и `L` – наименьшее возможное количество капель (ведь "Алиса отлично помнила, что если выпьешь слишком много из бутылки, на которой нарисованы череп и кости и написано "Яд!", то почти наверняка тебе не поздоровится") и количество кусочков пирожка. Если существует несколько вариантов для значения `L`, то вывести наименьшее из них.

27 161 28 160

23 4

Увидев улыбающегося кота, Алиса очень удивилась. Еще больше она удивилась, увидев, как Чеширский Кот исчез, оставив свою улыбку. Свое удивление от этой встречи Алиса записала с помощью фразы-палиндрома "Was it a cat I saw?", расположив буквы в форме квадрата, повернутого на 45 градусов, как показано на рисунке. Фразу "Was it a cat I saw" здесь можно прочитать несколькими способами, двигаясь от любой буквы W на границе к соседней букве слева, справа, снизу или сверху, от нее – к следующей, пока не дойдем до буквы C в центре квадрата, а затем двигаясь назад к границе. Разрешается при чтении фразы проходить дважды по одной и той же букве. К сожалению, когда Алиса рисовала квадрат с фразой, она поставила несколько клякс, скрывших некоторые буквы.

Напишите программу, определяющую число способов прочитать фразу "Was it a cat I saw" на рисунке Алисы без использования букв, скрытых кляксами.

Ввод содержит 13 строк, в формате, показанном в примере. Буквы, которые невозможно разобрать из-за клякс, заменены символом '*'.

Выведите одно целое число – количество способов прочтения фразы-палиндрома.

      W
     WAW
    WASAW
   WASIS*W
  WASITISAW
 WASI*ATISAW
WASITACATISAW
 WA**TATISAW
  WASITISAW
   WASISA*
    WASAW
     WAW
      W

23104

Чтобы убить время перед чаепитием, Мартовский Заяц и Болванщик играют в следующую игру. Игра идет на части квадрата размером `N\ times\ N` клеток, разрезанного по диагонали. В диагональных клетках записаны некоторые числа. В левый нижний угол доски помещается фишка. Игроки по очереди двигают фишку на соседнюю клетку вверх, вправо или по диагонали вверх-вправо, пока фишка не окажется на диагонали квадрата. Игрок, достигший клетки на диагонали квадрата, получает выигрыш, равный числу, записанному в этой клетке (отрицательное число в этой клетке означает проигрыш игрока).

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

Первая строка содержит одно целое число `N` (`2\ ≤\ N\ ≤\ 1000`) – размер доски, вторая строка – `N` целых чисел в диапазоне от `-10^6` до `10^6` – числа на диагонали.

Вывести одно целое число – максимальный выигрыш первого игрока.

7
7 1 4 9 -3 9 2

3