STRAWB - Magic Strawberries

no tags 

Andreina the Hobbit was walking in a big yard when he saw a huge path of strawberries, Andreina ran, looking where to found her friend, Teresa (Everybody knows that Teresa LOVES strawberries), Teresa then looked the giant path of strawberries, having some amount of strawberries in a single meter, but she soon noticed that in the end of the path there was a HUGE pot of strawberries, full of this delicious fruit, Teresa, grabbed the first strawberry, but she was sent some amount of spaces ahead! However, she grabbed another strawberry and she was sent out of the range of the pot.

 

She was a little confused, but, the Hobbit noticed that she was sent exactly Ai meters, the same exact amount of strawberries that were on the floor.

 

Now, Teresa likes a lot this fruits and wants to reach the pot, however, she doesn't want to repeat the experience of magically sent out away from the pot! Teresa won't leave any fruits in a single square if she decides to grab it.

 

Andreina the Hobbit called you, and you, the only programmer in Rainbowland must solve the problem... Andreina will give you the amount of meters to reach the pot and the number of strawberry meters that Teresa wants to pick as maximum (she has a little trauma as she was sent out of the pot range). Andreina then explains you:

 

“Teresa can grab all the strawberries in a single square, but, if she does so, she will be transported “Ai” meters ahead, being Ai the number of strawberries she grabbed. Else, Teresa will decide to skip the strawberry meter, she doesn't like this, so, give me the minimum strawberry meters Teresa should skip.”

 

INPUT:

The input will consists on T test cases, then, 3 lines will follow, the first line contains two numbers N and K, being N the number of meters and being K the maximum numbers of strawberries Teresa wants to pick, in the next line there will be N integers, giving the number of strawberries in each tile, the last number (Nn) will always be a 0, this represents the pot Teresa wants to go. Finally, the third line is a blank line.

 

OUTPUT:

The output starts with “Scenario #i:” where “i” is the test case of evaluation starting by 1, in the next line, you should output “Teresa will skip N strawberries” where N is the minimum number of strawberries Teresa will skip, if Teresa should skip all the strawberries, you should output “Teresa will skip all the strawberries”

 

Sample Input:

3

7 2

1 1 1 1 1 1 0

 

7 2

3 2 1 3 2 1 0

 

7 1

7 6 5 4 3 2 0

 

Sample Output:

Scenario #1:

Teresa will skip 4 strawberries

Scenario #2:

Teresa will skip 0 strawberries

Scenario #3:

Teresa will skip all the strawberries

 

Explanation of the second sample test:

Teresa takes the first strawberry at the 1st tile, moves 3 tiles to the right (4th tile), then she grabs the strawberry (3) and moves 3 more tiles, arriving then to the tile 7 where is the pot.

 

CONSTRAINTS:

2<=N<=1000

0<=K<=N

1<=Ni<=N


hide comments
itskamee: 2020-11-23 08:10:29

AC using microsoft powerpoint

smso: 2019-09-13 06:51:08

Use Devil People

richardks3647: 2018-08-04 06:07:50

AC using notepad

pigpork: 2018-06-02 08:29:50

快要死了

Last edit: 2018-06-02 08:30:20
goodwilllion: 2018-02-24 07:43:55

Easy AC using MICROSOFT CAMERA

rubenkresna22: 2017-12-15 05:54:19

ac in 1 go using calculator

kshubham02: 2017-12-05 15:22:48

1. Time limit is strange. O(n*k) solution - TLE, O(n*k) with fast i/o and inline function instead of regular - AC.
2. Description is confusing. K signifies the maximum number of strawberry piles you can collect. Hence, if there are 10 piles, and k is 1, then you HAVE TO SKIP 9 piles at least.

Last edit: 2017-12-05 15:26:03
hodobox: 2016-01-28 00:45:23

K represents the maximum amount of PILES of strawberries Teresa wants to take from, not the maximum sum of A[i] of the piles she can take from, i.e. regardless of A[i], if she decided to pick up strawberries at square i while willing to pick up X more strawberries, she will be now willing to take another X-1.

Daniel Ampuero: 2012-03-29 19:28:53

I hate printing strings on a problem...


Added by:david_8k
Date:2012-03-20
Time limit:0.100s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Own Problem