SPOJ.com - Problem TEMPTISL

TEMPTISL - 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:

a) The student can only travel from vertex to vertex (backwards or forwards) along the polygonal fence.

b) 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.

c) 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 enrolment 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)
-1 -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⁶³ - 1. Output 0 if there are no solution.

Example

Input:
8 5
1 4
-1 -1

Output:
6

Submit solution!

hide comments

< Previous 1 2 3 Next >

	seastian: 2020-06-13 21:58:05 1 step back and 1 step front are counted as different even if they result in same position
	aman_sachin200: 2018-06-16 11:00:24 Easy One!!Just remember that you can reach the destination vertex any number of time but take into consideration only those ones which reach the destination in k moves!!!
	nadstratosfer: 2017-09-28 03:30:14 Top-down with memo passes comfortably with Python, always fun to encounter problem allowing such an elegant solution. Had no problem with the statement or implementation, surprising given the problem rating and comments. Guess everyone has a different nemesis ;) Cheers guys below for warning about the blanklines, making my input reading idiot-proof prevented a lot of frustrating RE's.
	prasoonbatham: 2017-08-03 06:42:31 Beware of blank lines in input. Cost me 2 nzec. Used java.
	devbishnoi: 2016-11-03 16:21:01 think easy dp structure got AC in one go
	dwij28: 2016-10-08 22:40:08 Easy DP but horrible problem statement, It would have been very difficult to comprehend had I not read the comments.
	Shashank Tiwari: 2015-11-06 18:50:13 Okay , Here's is what this problem says : Assume numbers 1 to N on a circle. You have to move only 'K' moves either clockwise or anticlockwise or mixture of both to reach from 'A' to 'B' where A and B are any 2 of those numbers on circle. There can be many possible paths for this. You have to print the number of paths possible. If no path possible , Print 0. Here are few points for better understanding : 1. Numbers on circle are placed in order from 1,2,3... , till n . You can move clockwise or anticlockwise each step. 2.Let me define what a path is : Suppose you begin from 'A' (Given to u) And traverse Numbers n1 , n2 ,n3 ,... and so on to reach 'B' , let us define path as a tuple T1 = (A,n1,n2,.... ,B) . Similarly , let say there is another path T2 from 'A' to 'B' traversing b1, b2,... so on vertices , then T2 = (A,b1,b2,...,B). 2 Paths T1 and T2 are said to be different if tuples T1 != T2 . 3. Length of path has to be 'K' . Lentgh of path is nothing but circular arcs you traverse from A to B. ex: A=1 , B= 4 , then (1,2,3,4) has length 3 and not 4. Example : if A=1 , B=4 , k=5 , N=8 total paths are 6 as shown below : 1. (1,2,1,2,3,4) 2. (1,2,3,2,3,4) 3. (1,2,3,4,3,4) 4. (1,8,1,2,3,4) 5. (1,2,3,4,5,4) 6. (1,8,7,6,5,4) Note tuple or Path have 6 elements but length is 5 . Refer Above Point 3. Take Long to save number of paths. Also Input output format is : First N , K is given . Then A,B is given. Then again N,k is give . New lines might be present . BE careful . Then A,b is given . . . . This input ends when N,k is given as -1 -1. Hope it clears the problem statement. :)
	s1306: 2015-09-26 00:02:42 nice question,the standard way to solve such questions goes with this one too...but one can take a different approach,the important catch is that for a given k,if \|a-b\| is constant for all :1<=a,b <=n ;ans is same..hence dont include any vertex in your state,source or destination. Last edit: 2015-09-26 14:51:12
	Hussain: 2015-08-13 12:29:47 Problem statement is a disaster!! Read @sanky's comment to understand input format.
	Sumit Paroothi: 2015-08-04 16:01:42 beware of indexing!!!

Submit solution!

Added by:	JaceTheMindSculptor
Date:	2009-04-08
Time limit:	0.5s-1s
Source limit:	50000B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Languages:	All except: C99 ERL JS-RHINO
Resource:	Woburn Challenge 2001