Alexander Malinov



Дата18.12.2018
Размер16.87 Kb.
ТипЗадача



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






Поделитесь с Вашими друзьями:


База данных защищена авторским правом ©obuch.info 2019
отнасят до администрацията

    Начална страница