|
bul.“Alexander Malinov“ №33., Sofia, 1729, Bulgaria
academy.telerik.com
|
|
Задача 2 – Шестоъгълник
„Тази задача не е трудна!“ - казал си Алекс като прочел условието. Всичко, което трябва да направите е да броите възможности. Вие се намирате в полето на картинката, или по-точно в клетка с номер A. На всяка секунда задължително трябва да се преместите в съседна клетка. Напишете програма, която намира по колко различни пътя след T секунди да стигнете в клетка с номер B.

По-късно Алекс видял, че има още текст към условието и го прочел. За съжаление във V на брой момента в някоя клетка удря гръмотевица. Ако в една клетка са ударили нечетен брой такива, то при стъпване на нея вие умирате. Помогнете на Алекс да напише програма, която намира по-колко начина можете да стигнете от A до B с T на брой стъпки, оставайки живи.
Входни данни
На първия ред на стандартния вход се въвеждат числата A, B, T и V. На следващите V реда се въвеждат по две числа – момент, клетка ( кога и къде има гръмотевица ).
Изходни данни
Да се изведе търсения отговор по модул 1 000 000 007.
Ограничения -
0 < T <= 100 000 000
-
0 <= V <= 100
-
Гръмотевици няма да удрят в момент 0 и момент T.
-
В един момент няма по повече от една гръмотевица в една и съща клетка.
-
Позволено време за работа на програмата: 0.1 секунда. Позволена памет: 16 MB.
Примери
Вход
|
Изход
|
5 15 3 0
|
6
|
5 15 3 1
1 10
|
2
|
5 15 3 1
2 10
|
4
|
10 10 40 2
10 10
30 10
|
874996341
|
|
Telerik Algo Academy 2015
|
of
|
facebook.com/TelerikAcademy
|
Сподели с приятели: |