CCC '13 S2 - Bridge Transport

View as PDF

Submit solution

Points: 5
Time limit: 2.0s
Memory limit: 64M

Problem type
Canadian Computing Competition: 2013 Stage 1, Senior #2

A train of railway cars attempts to cross a bridge. The length of each car is 10m but their weights might be different. The bridge is 40m long (thus can hold 44 train cars at one time). The bridge will crack if the total weight of the cars on it at one time is greater than a certain weight. The cars are numbered starting at 11, going up to NN, and they cross the bridge in that order (i.e., 11 immediately followed by 22, which is immediately followed by 33, and so on).

What is the largest number TT of railway cars such that the train of cars 1 \dots T1 \dots T (in order) can cross the bridge?

Input Specification

The first line of input is the maximum weight WW (1 \le W \le 100\,0001 \le W \le 100\,000) that the bridge can hold at any particular time. The second line of input is the number NN (1 \le N \le 100\,0001 \le N \le 100\,000) which is the number of railway cars that we wish to move across the bridge. On each of the next NN lines of input, there will be a positive integer w_iw_i (1 \le i \le N1 \le i \le N, 1 \le w_i \le 100\,0001 \le w_i \le 100\,000) which represents the weight of the i^{th}i^{th} railway car in the sequence.

Output Specification

Your output should be a non-negative integer representing the maximum number of railway cars that can be brought across the bridge in the order specified.

Sample Input 1

100
6
50
30
10
10
40
50

Output for Sample Input 1

5

Explanation of Output for Sample Input 1

The first four railway cars have total weight 50 + 30 + 10 + 10 = 10050 + 30 + 10 + 10 = 100, which is not greater than what the bridge can hold. When the first railway car leaves, and the next comes on, we have a total weight of 30 + 10 + 10 + 40 = 9030 + 10 + 10 + 40 = 90, which is not greater than what the bridge can hold. The last four cars would cause the bridge to break, since 10 + 10 + 40 + 50 = 11010 + 10 + 40 + 50 = 110 which is greater than the bridge can hold. So, only the first 55 railway cars can be taken across the bridge.

Sample Input 2

100
3
150
1
1

Output for Sample Input 2

0

Explanation of Output for Sample Input 2

When the first railway car enters the bridge, its weight of 150150 will exceed the maximum weight the bridge can hold. Thus, we cannot bring any railway cars across the bridge.


Comments


  • 0
    christine123  commented on May 7, 2021, 3:52 p.m. edited

    NVM I DID IT.


  • 1
    Apurva  commented on Feb. 16, 2021, 11:12 a.m. edited

    I'm not sure why test cases 2, 3 and 4 keep giving me a wrong answer...any suggestions?


    • -1
      16_bit_D  commented on Feb. 16, 2021, 12:56 p.m.

      the bridge can be any length - so a car can pass, and a new one can enter - look at this again: "The first four railway cars have total weight 50+30+10+10=100, which is not greater than what the bridge can hold. When the first railway car leaves, and the next comes on, we have a total weight of 30+10+10+40=90, which is not greater than what the bridge can hold. The last four cars would cause the bridge to break, since 10+10+40+50=110 which is greater than the bridge can hold. So, only the first 5 railway cars can be taken across the bridge."


  • -9
    granpanis222  commented on Oct. 17, 2020, 1:15 a.m.

    This comment is hidden due to too much negative feedback. Click here to view it.