Задача Bracket.   В складних математичних виразах доводиться інколи ставити багато дужок. Часто  буває важко порахувати, скільки дужок відкрито і скільки закрито. Аби спростити запис, крім круглих дужок “(“ і “)”, застосовується права квадратна дужка “]”. , яка закриває усі відкриті на даний момент дужки, якщо такі є  (якщо відкритих дужок до правої квадратної немає, вираз є помилковим). Правильним  «дужковим» виразом будемо називати рядок символів, отриманий  з правильного виразу після викреслювання з нього усіх символів, крім дужок “(“, “)” и “]”.

Наприклад, правильними «дужковим»  виразом є (()(()(()](), ((((((], (())(). А ось приклади неправильних «дужкових» виразів:())((((] – помилка у третьому  символі, (())] – квадратній дужці нічого закривати,((])) – дужка, що йде за квадратною, не має відкритої пари. Порожній  рядок є правильним «дужковим» виразом.  Напишіть програму, яка для даного рядка, що містить лише  символи “(“, “)” и “]”, визначить, скільки є способів викреслити якусь кількість (можливо 0) символів так, аби ті, що залишились, утворили правильний «дужковий» вираз.

 Технічні умови. Програма  Bracket читає з клавіатури рядок із символів "(“, “)” або “]”. Кількість дужок у рядку – від 1 до 768. Програма виводить на екран єдине число – шукану величину по модулю 1 000 007

Приклади

Задача TETRIS365

Є набір пластинок 5-ти типів, кожна з яких складається з 4-х однакових квадратиків (див. малюнок). Фігурки можна повертати, перевертати, але не можна ламати. Дано однакову кількість пластинок кожного з типів.  Скільки різних за розмірами прямокутників можна скласти із усіх наявних пластинок (прямокутники m*n та  n*m вважаються однаковими)? Для кожного з прямокутників потрібно використовувати всі наявні плитки. Зрозуміло, що кожна клітинка прямокутника повинна бути покрита рівно одним квадратиком.

Технічні  умови. Програма TETRIS365 читає з клавіатури натуральне число N (1<=N<=10¹²) - кількість наявних пластинок  кожного типу і  виводить  на екран кількість прямокутників, які можливо скласти з даних пластинок.

Приклад

Ввведення

2

Виведення

2

Коментар. З набору, що складається з 10 фігурок по 2 кожного типу, можна скласти  прямокутники 4*10 та 5*8.

Задача Traceroute. Локальна мережа являє собою N серверів. Деякі пари серверів з’єднані виділеними лініями. Для кожної виділеної лінії відомий час проходження інформації (однаковий в обидва боки). Зрозуміло, що інформація між будь-якими серверами завжди передається якнайшвидше. Адміністратор мережі планує профілактичні роботи, тому кожного дня рівно одна виділена лінія буде від’єднана від мережі. Допоможіть користувачам визначити час отримання інформаціі під час робіт.

Технічні умови.

Програма Traceroute читає з клавіатури через пропуск кількість серверів N, номери серверів, з якого і на який передається інформація A, B (2≤N≤2000,1≤A,B≤N,A<>B). Наступні N рядків містять опис локальної мережі. У i-му рядку на j-й позиції записано час проходження інформації від i-го до j-го сервера – натуральне число від 1 до 100000. Якщо між i-м та j-м серверами немає виділеної лінії, записується 0. Наступний рядок містить натуральне число K (2≤K≤N) – кількість вершин у найкоротшому шляху, далі через пропуск K чисел a=v[1], v[2], … ,v[K]=b – найкоротший шлях. Програма виводить на екран через пропуск K-1 число – час отримання інформації, якщо виділену лінію від v[i] до v[i+1] буде відключено (1≤i<K). Якщо користувач не зможе отримати інформацію, вивести  -1.  

Приклад Введення 5 1 5 0 1 0 0 0 1 0 3 0 100 0 3 0 3 5 0 0 3 0 3 0 100 5 3 0 4 1 2 3 5 Виведення -1 101 10
	Малюнок до прикладу

Задача Garden365.  Згідно з земельним кодексом,  кожен мешканець Країни Дурнів має право на землю. На останній сесії парламент прийняв поправки, згідно яких:

1. Громадянин має право лише на одну ділянку землі;
2. Кожна ділянка має форму чотирикутника;
3. Земельний комітет призначає громадянину довжини  сторін ділянки;

Фермер подав заявку на землю і хоче визначити, яку максимальну площу може мати його ділянка.  Допоможіть земельному комітету підрахувати цю площу.

Технічні умови. Програма Garden365 читає з клавіатури 4 дійсних числа, на менших 1 і не більших 1000000. Програма виводить на екран шукану площу. Якщо ділянки з заданими сторонами не існує, вивести 0.

Приклади

Введення

1.0 2.0 1.0 2.0

Виведення

2.00000000

Введення

1 2 3 6

Виведення

0.00000000

Введення

1 2 4 10

Виведення

0.00000000

Задача Rook. На нескінченному  аркуші в клітинку, у якому деякі клітинки можуть бути вирізані, розміщено шахова тура. Рядки і стовпчики аркуша пронумеровано по порядку цілими числами. Стовпчики пронумеровані зліва направо, а рядки – знизу вверх. Тура одним ходом може переміщуватись на будь-яку іншу невирізану клітинку, що знаходиться в одному рядку чи стовпчику з початковою. Тура не може перестрибувати через вирізані клітинки. За яку найменшу кількість ходів тура може перейти з одного вказаного поля на інше (якщо це можливо)?

Технічні умови. Програма Rook читає з клавіатури чотири цілих числа x1, y1, x2, y2, розділені пропусками: x1 (номер стовпчика) і y1 (номер рядка) - координати клітинки, де тура знаходиться спочатку, а x2 (номер стовпчика) і y2 (номер рядка)  - координати клітинки, куди тура повинна потрапити. Далі програма читає кількість вирізаних клітинок n (0<=n<=1000) і n пар цілих чисел x (номер стовпчика), y (номер рядка) – координати вирізаних клітинок. Всі вирізані клітинки різні, початкова і кінцева клітинки не вирізані, координати всіх клітинок не перевищують за абсолютною величиною 1000000000. Програма виводить на екран шукану мінімальну кількість ходів тури або -1, якщо перейти неможливо.

Приклади

Введення                            

1 –1 5 -4 4 1 1 5 –5 2 –4 4 –1

Виведення

3

Введення

10 11 5001 -4733 5 5001 -4732 5001 –4734 1 1 5000 –4733 5002 –4733

Виведення

-1