Емблема центру  www.olymp.vinnica.ua     netoi.org.ua
Центр олімпіад школярів в Iнтернеті
Likt-PMG17
м.Вiнниця


Годинник
 
Palway

Задача Palway. Задано квадратну таблицю n × n, що складається з натуральних чисел. Роз­гля­да­ти­ме­мо шля­­­хи з лі­­­вої верхньої комірки таблиці у праву нижню, які до­ві­льним чи­ном ідуть по ко­мір­ках таблиці праворуч та донизу (але ніколи ліворуч або вгору). Уз­довж кож­ного такого шляху розташовано 2n - 1 число. Якщо для пев­ного шляху даний набір чисел є «симетрич­ним», тобто читається у зворот­но­му порядку так само, як і у прямому, називати­ме­мо вибраний шлях па­лін­дро­міч­ним. За заданою таблицею встановіть загальну кількість на ній палін­дро­міч­них шляхів.

Технічні умови. Програма Palway читає з пристрою стандартного введення ціле число n (2 <= n <= 100) – розмір таблиці. У наступних n рядках файлу записано по n нату­ра­ль­них чисел, що не перевищують 10 000 та задають таблицю. Програма виводить на пристрій стандартного виведення єдине число - остачу від ділення на 101 кі­ль­кості паліндромічних шляхів на заданій таблиці.

Введення

Виведення

1

3
7 10 5
5 8 10
8 5 7

4

2

6
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1

50

Приклади

 

Коментар

У першому прикладі є чотири паліндромічних шляхи:

  1. праворуч — праворуч — донизу — донизу (7–10–5–10–7);
  2. праворуч — донизу — праворуч — донизу (7–10–8–10–7);
  3. донизу — праворуч — донизу — праворуч (7–5–8–5–7);
  4. донизу — донизу — праворуч — праворуч (7–5–8–5–7).

У другому прикладі кожен з 252 можливих шляхів є паліндромічним, тож за умовою слід вивести остачу від ділення 252 на 101 — число 50.

 


© Всеукраїнський віртуальний центр олімпіад школярів "ОЛІМП"