Submit | All submissions | Best solutions | Back to list |
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 263 - 1. Output 0 if there are no solution.
Example
Input: 8 5 1 4 -1 -1 Output: 6
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 |
hide comments
|
||||||
2015-05-18 03:12:01 Sahil Sharma
The indexing shouldn't matter right? Since all that matters is the 'distance' between a and b. So distance between 1 and 4 is same as that between 0 and 3. |
||||||
2014-12-20 17:13:11 Mauro Persano
The problem statement is awful. |
||||||
2014-08-16 12:15:17 Garima
Sanky's comment helps in understanding input type. Also for the test case: 2 3 1 2 the answer given by my AC program is 4. Could someone explain how?? EDIT: Okay the program is AC but still weird. It calculates the same path multiple times. I don't know how I got AC. As soon as I came across this test case I thought I'll get WA. This question's solution is just sad. :/ EDIT: Okay my bad it is polygonal so n!=2 and this multiple counting problem will not arise. Sorry. Last edit: 2014-08-16 12:28:55 |
||||||
2014-06-23 08:55:41 ayush
Extremely simple , I was over thinking unnecessarily |
||||||
2013-11-24 09:16:47 Zhouxing Shi
couldn't understand the problem statement.. >_< |
||||||
2013-07-23 10:46:22 conioh
A may be less than grater than or equal to B..costed me 2 WA |
||||||
2013-07-09 13:24:18 Codeblooded
nice and easy dp :) |
||||||
2013-06-15 18:56:07 nagato
simple dp....:) |
||||||
2013-01-23 13:57:00 Anmol
easy dp but tricky initialistions got many wa bcoz of that |
||||||
2012-01-31 13:03:52 Paul Redman
There may be blank lines between the cases. So the input looks like: n1 k1 a1 b1 n2 k2 a2 b2 ... |