UVa 10798
From Algorithmist
Contents |
[edit] 10798 - Be Wary of Roses
[edit] Summary
This is an exhaustive search problem, with the aid of some memoization.
[edit] Explanation
Looking carefully at the search space, we note that for any N, the most roses we need to trample is simply 
:
RRRRRRRRRRR RRRRRRRRRRR RRRRRRRRRRR RRRRRRRRRRR RRRRRRRRRRR RRRRRPRRRRR RRRRRRRRRRR RRRRRRRRRRR RRRRRRRRRRR RRRRRRRRRRR RRRRRRRRRRR
Since the field is full of roses (this is the worst case), we can't do worse than going in a straightline - and step on roses. Also, since 
, we can simply try all direction, and keep track (and then memoize the number of roses we would've stepped on, if we were looking that way. This gives us 6 dimensions to memo on, but since the numbers are so small, this should run in time.
[edit] Input
11 ........... ........... ........... ........... ....RRRRRR. ....RPRRRR. ....RRRRRR. ....RRRRRR. ....RRRRRR. ....RRRRRR. ........... 5 .RRR. R.R.R R.P.R R.R.R .RRR. 5 RR.RR RR.RR ..P.. RR..R RRR.R 9 RRRR.R.RR RRRR.R.RR R..R.R.RR RRRR.R.RR RRRRPRRRR RR.RRRRRR RR.RR.... RR.RRRRRR RR.RRRRRR 9 RRRR.R.RR RRRR.R.RR R.RR.R.RR RRRR.R.RR RRRRPRRRR RR.RRRRRR RR.RR.... RR.RRRRRR RR.RRRRRR 9 RRRR.R.RR RRRR.R.RR R.RR.R.RR RRRR.R.RR RRRRPRRRR RR.RRRRRR RR.RR.... RR.RRRRRR RR.RRRRRR 21 RRRRRRRRRRRRRRRRRRRRR R...................R R...................R R...................R R...................R R...................R R...................R R...................R R...................R R...................R R.........P.........R R...................R R...................R R...................R R...................R R...................R R...................R R...................R R...................R R...................R RRRRRRRRRRRRRRRRRRRRR 9 RRRR.RRRR RRRR..RRR RRRRR.RRR R.....RRR ..R.P.R.. RRR.....R RRR.RRRRR RRR..RRRR RRRR.RRRR 1 P 13 RRRRRR.RRRR.R ....R.R...R.R RRRRR..RRRRRR R.RRRRRR.RR.R R.R..RR...RRR R.RR....RR.RR .R.R.RP.RRR.. R.RRR.R.RRRRR ..RR.R.R..R.R R.RR.R.R.RR.R R.RRRR.RRRRRR R.R...R...... R.RRRRRR.RRRR 21 RRRRRRRR.RRRRRRRRRRRR RRRRRRRR..RRRR...RRRR RRRRR...R..RR..R.RRRR RRRRR.R..R....R..RRRR R...R..R..RRRR..RRRRR R.R..R..R..RR..R...RR R..R..R..R....R..R.RR RR..R..R..RRRR..R..RR RRR.RR.RR..RR..R..R.. RRR.RR.RRR.R..R..R..R RR..R..R..P..R..R..RR R..R..R..R.RRR.RR.RRR ..R..R..RR..RR.RR.RRR RR..R..RRRR..R..R..RR RR.R..R....R..R..R..R RR...R..RR..R..R..R.R RRRRR..RRRR..R..R...R RRRR..R....R..R.RRRRR RRRR.R..RR..R...RRRRR RRRR...RRRR..RRRRRRRR RRRRRRRRRRRR.RRRRRRRR 21 RRRRRRRR.RRRRRRRRRRRR RRRRRRRR..RRRR...RRRR RRRRR...R..RR..R.RRRR RRRRR.R..RR...R..RRRR R...R..R..RRRR..RRRRR R.R..R..R..RR..R...RR R..R..R..R....R..R.RR RR..R..R..RRRR..R..RR RRR.RR.RR..RR..R..R.. RRR.RR.RRR.R..R..R..R RR..R..R..PR.R..R..RR R..R..R..R.RRR.RR.RRR ..R..R..RR..RR.RR.RRR RR..R..RRRR..R..R..RR RR.R..R....R..R..R..R RR...R..RR..R..R..R.R RRRRR..RRRR..R..R...R RRRR..R....R..R.RRRRR RRRR.R..RR..R...RRRRR RRRR...RRRR..RRRRRRRR RRRRRRRRRRRRRRRRRRRRR 21 RRRRRRRR.RRRRRRRRRRRR .RRRRRRR..RRRR...RRRR ..RRR...R..RR.RR.RRRR ...RR.RRRR....RRRRRRR ....R..RR.RRRR..RRRRR .....R..R..RR..R...RR ......R..R....RR.RRRR .......R..RRRR..R..RR ........R..RR.RR..R.. .........R.R..R..R..R ..........P..R..R..RR .........R.RRR.RR.RRR ........RR.RR..RR.RRR .......RRRR..R..R..RR ......RRR..R..R..R..R .....R.RRR..R..RR.RRR ....R..RRRR..R..R...R ...R..RR...RR.R.RRRRR ..RR.R..RR..R...RRRRR .RRR.R.RRRR..RRRRRRRR RRRRRRRRRRRR.RRRRRRRR 21 .................R.R. RRRRRRRRRRRRRRRRRR.R. .................R.R. RRRRRRRRRRRRRRRR.R.R. .R.............R.R.R. .R.RRRRRRRRRRR.R.R.R. .R.R.........R.R.R.R. .R.R.RRRRRRR.R.R.R.R. .R.R.R.....R.R.R.R.R. .R.R.R.RRR.R.R.R.R.R. .R.R.R.R..P..R.R.R.R. .R.R.R.R.R.RRR.R.R.R. .R.R.R.R.R.....R.R.R. .R.R.R.R.RRRRRRR.R.R. .R.R.R.R.........R.R. .R.R.R.RRRRRRRRRRR.R. .R.R.R.............R. .R.R.RRRRRRRRRRRRRRRR .R.R................. .R.RRRRRRRRRRRRRRRRRR .R.R................. 21 .................R.R. RRRRRRRRRRRRRRRRRR.R. .................R.R. RRRRRRRRRRRRRRRR.R.R. ...............R.R.R. ...RRRRRRRRRRR.R.R.R. .............R.R.R.R. .....RRRRRRR.RRRRRRR. .....R.....R.R.R.R.R. .......RRR.R.R.R.R.R. ..........P..R.R.R.R. .........R.RRR.R.R.R. .........R.....R.R.R. .......R.RRRRRRR.R.R. .......R..R......R.R. .......RRRRRRRRRRR.R. .....R....R........R. .....RRRRRRRRRRRRRRRR ..................... ...RRRRRRRRRRRRRRRRRR .R.R................. 21 .................R.R. RRRRRRRRRRRRRRRRRR.R. ................RR.R. RRRRRRRRRRRRRRRRRR.R. ...............RRRRR. ...RRRRRRRRRRR.RRRRR. .............R.RRR.R. .....RRRRRRR.RRRRRRR. .....R.....R.R.R.R.R. .......RRR.R.R.R.R.R. ..........P..R.R.R.R. .........R.RRR.R.R.R. .RR......R.....R.R.R. .RR....R.RRRRRRR.R.R. .RR....R..R......R.R. .RR....RRRRRRRRRRR.R. .RR..R....R........R. .....RRRRRRRRRRRRRRRR .....RR.............. ...RRRRRRRRRRRRRRRRRR .R.R................. 21 RRRRRRRRRR.RRRRRRRRRR RRRRRRRRRR..RRRRRRRRR RRRRRRRRRR.RRRRRRRRRR RRRRRRRRRR..RRRRRRRRR RRRRRRRRRR.RRRRRRRRRR RRRRRRRRR.RRRRRRRRRRR RRRRRRRRRRRRRRRRRRRRR RRRRRRRRR.RRRRRRRRRRR RRRRRRRRRRRRRRRRRRRRR R.R.RRRRR...R.R.RRRRR RRRR......P......RRRR RRRRR.R.R...RRRRR.R.R RRRRRRRRRRRRRRRRRRRRR RRRRRRRRRRR.RRRRRRRRR RRRRRRRRRRRRRRRRRRRRR RRRRRRRRRRR.RRRRRRRRR RRRRRRRRRR.RRRRRRRRRR RRRRRRRRR..RRRRRRRRRR RRRRRRRRRR.RRRRRRRRRR RRRRRRRRR..RRRRRRRRRR RRRRRRRRRR.RRRRRRRRRR 0
[edit] Output
At most 4 rose(s) trampled. At most 2 rose(s) trampled. At most 1 rose(s) trampled. At most 2 rose(s) trampled. At most 3 rose(s) trampled. At most 3 rose(s) trampled. At most 1 rose(s) trampled. At most 0 rose(s) trampled. At most 0 rose(s) trampled. At most 3 rose(s) trampled. At most 0 rose(s) trampled. At most 1 rose(s) trampled. At most 2 rose(s) trampled. At most 0 rose(s) trampled. At most 2 rose(s) trampled. At most 3 rose(s) trampled. At most 4 rose(s) trampled.
