SPOJ.com - Problem BEANGAME

BEANGAME - Help MR BEAN

no tags

Mr. Bean loves to play games. For this he wastes lots of money so Mrs. Bean made a hurdle game for him. Now in the game we have 3 tracks and for moving up to next level he will have to cross some hurdles. Each time he changes the track he gets some drink to increase his energy level by that amount. The drink that he gets is the one which is in between the present track and the adjacent track and in the direction of movement (adjacent track may or may not be the track on which he is targeting to move). Now if at any moment his energy becomes negative his game will be over. So you have make him win this game with maximum energy being available with him at last. He will move in the form of 'L' and 'R' between adjacent tracks with 'L' making him move one step left of the present position and 'R' moving him right. Movement between different level will be separated by '-' and if there is no change of track between adjacent levels then print 'U' at its corresponding move .

Input

First line will have 3 integers Il, Ie, Ns where Il is the initial track on which he is standing, Ie is the initial energy he is having and Ns is the number of levels in the game. Then it would be followed by 5 lines where the first three will have the values of the hurdles present at each level on each track. Fourth line will have Ns-1 integers representing the energy obtained by him on drinking the energy drink between continuous levels between track 1 and 2 and similarly fifth line will have Ns-1 values for drinks between tracks 2 and 3.

Output

Print "DONE IT!" in first line and the steps taken by him in second line following the path which leads to maximum energy available with Mr. Bean beyond final track. If it is not possible print "GAME OVER!".

Constraints

Every integer, intermediate values will fit in 32-bit integer.

Example

Input:
1 6 5
3 2 9 16 3
4 0 7 26 1
1 7 3 30 9
8 19 8 3
10 3 6 4

Output:
DONE IT!
RR-LL-RR-LL-R

Submit solution!

hide comments

< Previous 1 2 Next >

	Oleg: 2023-07-07 01:26:47 If we can get same score by visiting tracks "start-1-2-1-3-finish" and "start-1-2-2-1-finish" we should prefer first way since in first difference we visited track 1. in both your examples I also get U-R and L-R.
	Simes: 2023-07-05 17:54:37 Thanks for the clarification @Oleg. I took the statement "Each time he changes the track he gets some drink..." to mean that since going from track 1 to 3 requires two R moves, it was two changes of track, and so he got two drinks. Could you clarify your comment about preferring track 1? With the case below, I can either start in track 1 (U-R), or finish in track 1 (R-L), (as well as many other valid paths of course) but which is the preferred? 1 4 2 2 2 2 2 2 2 1 1 Similarly the case below could be L-R (prefer track 1 initially), or U-L to finish in track 1. 2 4 2 2 2 2 2 2 2 1 1 I give U-R and L-R respectively, but still get WA.
	Oleg: 2023-07-04 23:35:27 @Simes, btw your understanding is pretty much correct with exception of drinks. We can grab only a single drink even if we change track from 3 to 1. Description kind of mentions it.
	Simes: 2023-07-04 20:21:00 Congratulations @Oleg, first AC since 2017!
	Oleg: 2023-07-04 19:41:19 Warning: it can be ties and description doesn't specify how to resolve them. in case of tie you should prefer track 1 first, then track 2, then track 3. For example for 3 3 1 2 2 2 answer should be DONE IT! LL Last edit: 2023-07-04 19:43:22
	Simes: 2019-11-27 21:14:20 This is my understanding: * The image shows there are Ns+1 levels. The first is level 0, where the player starts, the last is level Ns where the player finishes. * The player can move left and right on level 0, but there are no energy drinks to collect. * When jumping to the final level, there's no "-" for the final move. * If there are no track changes between levels, does the U replace the absent L and R moves? Or is the U an alternative to the - in this case? * There's nothing to say the player cannot move left and right on a level to collect all the energy drinks, before going to the next level via the smallest hurdle, but I suspect this isn't the desired behaviour. * The answer for the above grid is given as RR-LL-RR-LL-R. The player starts at level 0, track 1 (L0T1) with 6 energy. He moves R twice to L0T3, but collects no energy drinks, before going to L1T3 over the 1 hurdle, bringing his energy down to 5. He moves L twice, collecting drinks 10 and 8, bringing his energy to 23, before hurdling the 2, making his energy 21 at L2T1. He moves R twice, collecting drinks 19 and 3, bringing his energy to 43, before hurdling the 3, making his energy 40 at L3T3. He moves L twice, collecting drinks 6 and 8, bringing his energy to 54, before hurdling the 16, making his energy 38 at L4T1. He moves R to gain drink 3, bringing his energy to 41, before hurdling the 1 to finish with energy 40. Where am I going wrong? Last edit: 2020-06-16 21:34:52
	mohit rathi: 2015-03-17 18:10:09 Finally AC. Note : Game will be over if energy gets 0 at any point. (not clearly pointed in problem statement)
	John Snow: 2014-05-17 00:28:20 please explain the test case and how does his energy reduces?
	Dhinesh Dharman: 2014-05-17 00:28:20 @Jayendra Thanks! Got AC. Awesome question.

Submit solution!

Added by:	Mrs. Bean
Date:	2012-12-17
Time limit:	1s-2s
Source limit:	50000B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Languages:	All except: ASM64
Resource:	Own Problem