### Woburn Challenge 2001 - Suicidal

## Tuesday - Temptation Island

On Monday, the number of frosh were reduced in half. To further reduce the number of engineers to a manageable number, the following challenge was devised for the second day. Each of the students would have to take this challenge individually.

Each student would be placed at a vertex of perimeter fence of Waterloo (oh yeah, some background: to keep UofT’s engineering Lady Godiva band out of Waterloo, a fence was erected surrounding the university. The fence just happens to be an `N`-gon). At some other vertex along the fence would be located a temptation so seductive that no Waterloo student could resist – an extra-credit assignment. The challenge of each student is to go from his starting vertex to the vertex with the prize. There are, however, 3 rules:

- The student can only travel from vertex to vertex (backwards or forwards) along the polygonal fence.
- The student has to make contact with exactly
`K`vertices (the vertex he starts at doesn’t count unless he returns to it). The`K`vertices need not be unique. The final vertex has to be the one with the prize. - If the student cannot reach the prize and make contact with exactly
`K`vertices, he fails the test and is kicked out of the university.

Of course, no Waterloo student is satisfied with only 1 solution to any problem. Therefore, inevitably, each student determines all ways that he/she can win. Note that there may be no solution to the problem (the astute student has figured out that this will result in a class size of 0 – this is entirely allowable as the variable used to quantify enrollment was incorrectly defined as a whole number instead of a natural number).

### Input

`N` `K` (`N`, `K` ≤ 50)

`A` `B` (`A` = the starting vertex number, `B` = destination vertex number)

There will be multiple test cases, one after another: a case where `N` = -1, `K` = -1 terminates input.

### Output

The total number of ways of reaching the destination from the starting point by following the above rules. The total number of ways will be less than 2,147,483,647 (ie. a longint). Output 0 if there are no solutions.

### Sample Input

`8 5`

1 4

-1 -1

### Sample Output

`6`

All Submissions

Best Solutions

**Point Value:** 10

**Time Limit:** 2.00s

**Memory Limit:** 16M

**Added:** Dec 05, 2008

**Languages Allowed:**

C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

## Comments (Search)

qinhaotianon Dec 11, 2008 - 11:16:25 pm UTC Re: Re: related to mathNo wonder you got -4 rating -.-

dAedaLon Dec 11, 2008 - 11:24:43 pm UTC Re: Re: Re: related to mathand I didn't use a math formula.

Although it seems like there is one for some reason.

hansonw1on Dec 11, 2008 - 11:42:47 pm UTC Re: Re: Re: Re: related to math(It involves N choose K)

It probably isn't easier than the 'regular' way.

qinhaotianon Dec 11, 2008 - 4:07:06 am UTC related to mathhansonw1on Dec 06, 2008 - 5:15:32 pm UTC ClarificationN and K are different every time.

taimla101on Dec 05, 2008 - 4:07:23 pm UTC are they all on the same vertex...hansonw1on Dec 05, 2008 - 4:11:26 pm UTC Re: are they all on the same vertex...There is only one student trying to get from the start to the end. The 'other students' are irrelevant.