CCC '07 J5 - Keep on Truckin'

View as PDF

Submit solution

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

Problem type

A truck driver is planning to drive along the Trans-Canada highway from Vancouver to St. John's, a distance of 7000 km, stopping each night at a motel. The driver has been provided with a list of locations of eligible motels, with the respective distance of each motel, measured in km, from the starting point in Vancouver. Some of the motel locations are:

0, 990, 1010, 1970, 2030, 2940, 3060, 3930, 4060, 4970, 5030, 5990, 6010, 7000

but more motel locations may be added just before the trip begins.

Determine if it is possible to complete the journey if:

  1. the trucking company insists that the driver travels a minimum distance of A km per day,
  2. the law sets a maximum distance of B km per day, and
  3. each night, the driver must stay at an eligible motel (from the above list or the additional locations described below).

The driver is interested in different options when making the trip, and you are to write the program to calculate how many different options there are.

For example, if no new motel locations are added, A = 1 and B = 500, then it is impossible to make the trip, i.e., the number of options is 0. If A = 970 and B = 1030 then there is one way to make the trip, but if A = 970 and B = 1040 then there are four ways to make the trip. There are two ways to make the trip if A = 970, B = 1030, and we add one stop at 4960.

Input Specification

The first two lines of the input are the minimum distance A and the maximum distance B (1 \le A \le B \le 7000), both of which are integers. The third line of the input is an integer N (0 \le N \le 20), followed by N lines, each giving the location m of an additional eligible motel (0 < m < 7000).

You should note that no two motels are located at the same distance from Vancouver.

Output Specification

Output the number of different ways the driver can choose the motels to make the trip, under the given constraints.

Sample Input 1

1
500
0

Sample Output 1

0

Sample Input 2

970
1030
0

Sample Output 2

1

Sample Input 3

970
1040
0

Sample Output 3

4

Sample Input 4

970
1030
1
4960

Sample Output 4

2

Comments


  • 0
    31501357  commented on April 14, 2019, 11:58 a.m.

    Should have specified you needed long integers!


    • -2
      666245  commented on April 14, 2019, 12:12 p.m. edited

      the new testcases added by certain pretentious people who think by adding test cases w/ long or even making 400+ testcases makes them look cool.


  • 1
    explosion  commented on March 3, 2019, 9:37 p.m.

    Any tips for making code faster aaaaa TLE on case 6

    :(


  • 0
    Asorn  commented on Feb. 16, 2019, 11:58 a.m.

    I keep on TLE'ing on test case 6, could somebody give a me a hint on how to fix it? Ty in advance


  • 1
    discoverMe  commented on Jan. 14, 2019, 1:01 p.m.

    can they move backwards


    • -2
      Riolku  commented on Jan. 14, 2019, 4:46 p.m.

      no


  • 2
    TimothyW553  commented on Dec. 16, 2018, 7:43 p.m.

    What happened?


  • 0
    septence123  commented on Nov. 20, 2016, 5:41 p.m.

    The grader shows a syntax error for python 2, it does not show syntax error when I submit the sample inputs on python idle.


    • 0
      Kirito  commented on Nov. 20, 2016, 9:20 p.m.

      Are you sure that your IDE is in Python 2? Your syntax is perfectly valid in Python 3.


      • 0
        septence123  commented on Nov. 21, 2016, 7:43 p.m.

        Yes, my IDE is python 2 (2.7.11) and I put python 3 when I submitted my solution, it worked perfectly(even though it was python 2), but this does not usually happen.


        • 0
          Kirito  commented on Nov. 22, 2016, 8:19 a.m. edit 2

          TL;DR It was a problem with the data which has been fixed.


  • 2
    zharry  commented on Feb. 7, 2016, 11:52 a.m.

    May I point out that in the sample inputs there are trailing spaces.


    • 0
      cheesecake  commented on Feb. 7, 2016, 1:53 p.m.

      Fixed, thanks.


  • 1
    zys5945  commented on Oct. 14, 2015, 12:40 p.m. edited

    if A = 970 && B = 1030, doesn't that mean: 0 -> 1010 -> 2030 -> 3060 -> 4060 -> 5030 -> 6010 -> happy ending?


    • 13
      kobortor  commented on Oct. 14, 2015, 1:04 p.m.

      And the output agrees with you, there is 1 way to get there.


      • 30
        zys5945  commented on Oct. 15, 2015, 11:38 a.m.

        I guess it's time for me to get glasses