SPOJ.com - Problem RPLI

RPLI - Ignore the bounds

Luis is seeing his son playing, he ask him gently in what the game consists, the boy replies “It's like this, you have a big number, a bound and a “mod” (the remainder of a division between a number and “mod”), the goal of the game is to discover the maximum sub-number you can create following this rules:”

The sequence must not decrease lower from the first digit taken.
The sequence chosen must not reach the bound. By example, if the first digit is 'd' and a bound 'k', the range you can take is between [d, min(d+k, 9)]
You can start from any digit of a number.
For any given start point, you should look for the sub-numbers making the maximum sum applied to the mod operation.

Luis, astonished by the explanation, request his son to give him an example, the boy then continues: “Suppose a number like this: 56789, a bound of 2, and a mod 10. you start with 5, being the bound of 2, this mean you can take up to the digit 7 (this means that you can always collect as many fives, sixes and sevens following the rules explained). The sub-number formed is of “5+6+7”, following the rules, we will have all others sub-numbers: “6+7+8”, “7+8+9”, “8+9” and “9”, after applying the operation, you will find that the maximum remainder of the sub-numbers sum will be of “9”, made by the sub-number “9”.

Luis is a former programmer now and he does not have the same ability he had years ago, please, help him in his task following the game previously defined.

Input

The first line of input will contain an integer T denoting the T test cases, then, T cases will follow. Each of the following cases will contain a line with an integer L, a big number N in the range [10^(L-1),(10^L)-1], an integer K denoting the bound and the M that will be the mod of the whole operation.

Output

Output the string “Scenario #i: “ where i is the test case you are analyzing followed by the maximum sum of the sub-sequence that can be formed.

Example

INPUT

OUTPUT

7 1235678 2 10

7 1235678 2 3

3 679 2 20

4 3457 2 10

Scenario #1: 8

Scenario #2: 2

Scenario #3: 16

Scenario #4: 9

Constraints

1<=L<=100000

10^(L-1)<=N<(10^L)-1

1<=K<=8

1<=M<=45

Submit solution!

Added by:	david_8k
Date:	2012-05-05
Time limit:	0.100s
Source limit:	50000B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Languages:	All except: ASM64
Resource:	Own Problem used for the RPL contest

hide comments



2017-09-11 14:21:37 Rocker3011 why 6+7+8 is not a solution for test case number 1?
2016-02-22 07:56:32 [Rampage] Blue.Mary The problem requires an O(n) algorithm. O(nlogn) algorithm will surely get TLE. However, I think setting n to 10^6 (or even larger) with longer TL (rather than n=10^5 with TL=100ms) will be a proper choice.
2014-10-25 20:36:01 Samuel Nacache @Jacob Plachta thanks :)
2014-08-29 19:23:16 Jacob Plachta It turns out that, indeed, the sub-number must extend as far as possible from the starting digit. So, in the example "5 56789 2 10", "6+7" is not valid.
2013-03-14 01:28:22 Samuel Nacache In the example "5 56789 2 10" can the sequence "6+7" be a valid sub-number? Or the sub-numbers construction must stop when it finds a greater number than its bound, or reaching a decreasing number?