Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Buckets of Water

By tanimahossain · Limits 1s, 512 MB

In Abby’s area the water is available in the tap only from 6AM to 8AM. So, Abby thought she would store water during that time. But to store water Abby needs some buckets, thus, she went to the bucket section in the supermarket.
There were a lot of shelves in the bucket section. There were different sizes of buckets in different shelves. Every bucket in the same shelf has the same size. Abby saw a ladder leaning on the shelves and climbed up to reach the topmost shelf. After reaching the topmost shelf, she suddenly realized she can hold only one bucket at a time on one hand because she needs to use the other hand to hold on to the ladder and climb down. Note that, she can not climb up using one hand because she is not that strong and once she climbs all the way down she can’t climb up the ladder again cause a lot of people are waiting to use the ladder as well.
Abby might not be strong, but she is intelligent in deed. She thought of an idea using which she can pick as many buckets as possible in such a way that she won’t have to hold more than one bucket.

  • She will pick a Bucket from any shelf and climb a shelf down
  • if the current shelf has the larger size of buckets than Abby is holding right now, she can put the bucket she is holding into the bucket on the shelf and then pick that bucket up or She can also choose to skip the shelf if she wants.
    Remember as it was said before Abby is not much strong. As the larger the buckets are the heavier. So the total size of all the buckets she picked up can’t exceed a value ‘K’(this value will be given in the input) Now, can you tell what is the maximum number of buckets Abby can pick?
  • Input

    First line of the input there is an integer T, the number of test cases.
    In each test case, there are two integers N,K, the number of shelves and the maximum total size abby can hold. In the next line there are N integers ith denotes the size of buckets on ith shelf. Note that the 1st shelf is closest to the ground and the N-th bucket is the top most one.

    Subtasks

    Subtask #1 (10 points)
    1 ≤ T ≤ 10
    0 ≤ K ≤200
    0 < N ≤20
    1 ≤ bucket size ≤ 100

    Subtask #2 (30 points)
    1 ≤ T ≤ 10
    0 ≤ K ≤ 200
    0 < N ≤ 100
    1 ≤ bucket size ≤ 100

    Subtask #3 (60 points)
    1 ≤ T ≤ 1000
    0 ≤ K ≤ 1018
    0 < N ≤103
    1 ≤ bucket size ≤ 1012
    summation of all N among all test case doesn’t exceed 2x104

    Output

    For each testcase output a line “Case $X: Y” where X is the case number and Y is the maximum number of buckets picked by Abby.

    Sample

    InputOutput
    2
    9 14
    6 4 2 5 7 5 3 4 1
    5 9
    4 3 5 2 1
    
    Case $1: 4
    Case $2: 3
    

    In the 1st test case, Abby can pick
    Bucket of size 1 from 9th shelf, skip 8th shelf and climb down
    Put the Bucket of size 1 into the Bucket of size 3 and pick it up from 7th shelf, skip the 6th,5th,4th and 3rd shelves and climb down
    Put the Bucket of size 3 into the Bucket of size 4 from 2nd shelf skip, pick it up, climb down
    Put the Bucket of size 4 into the Bucket of size 6 from 1st shelf
    Total number of buckets is 4. Total size=1+3+4+6=14 ≤ K

    In the 2nd test case, Abby can pick
    Bucket of size 1 from 5th shelf and climb down
    Put the Bucket of size 1 into the bucket of size 2 from 4th shelf pick it up and skip 3rd shelf climb down
    Put the Bucket of size 2 into the bucket of size 3 from 2nd shelf and climb down
    Total number of buckets is 3. Total size=1+2+3=6 ≤ K

    Discussion

    Statistics


    20% Solution Ratio

    EgorKulikovEarliest, 1M ago

    EgorKulikovFastest, 0.6s

    EgorKulikovLightest, 296 MB

    EgorKulikovShortest, 21493B

    Submit

    Login to submit