CCC '07 J5 - Keep on Truckin' - DMOJ: Modern Online Judge

CCC '07 J5 - Keep on Truckin'

View as PDF

Submit solution

All submissions

Best submissions

Points: 7 (partial)

Time limit: 1.0s

Memory limit: 256M

Problem type

Canadian Computing Competition: 2007 Stage 1, Junior #5

A truck driver is planning to drive along the Trans-Canada highway from Vancouver to St. John's, a distance of $7000$ $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:

Copy

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:

the trucking company insists that the driver travels a minimum distance of $A$ $A$ km per day,
the law sets a maximum distance of $B$ $B$ km per day, and
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$ $A = 1$ and $B = 500$ $B = 500$ , then it is impossible to make the trip, i.e., the number of options is 0. If $A = 970$ $A = 970$ and $B = 1030$ $B = 1030$ then there is one way to make the trip, but if $A = 970$ $A = 970$ and $B = 1040$ $B = 1040$ then there are four ways to make the trip. There are two ways to make the trip if $A = 970, B = 1030$ $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$ $A$ and the maximum distance $B$ $B$ ( $1 \le A \le B \le 7000$ $1 \leq A \leq B \leq 7000$ ), both of which are integers. The third line of the input is an integer $N$ $N$ ( $0 \le N \le 20$ $0 \leq N \leq 20$ ), followed by $N$ $N$ lines, each giving the location $m$ $m$ of an additional eligible motel ( $0 < m < 7000$ $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

Copy

1
500
0

Sample Output 1

Copy

Sample Input 2

Copy

970
1030
0

Sample Output 2

Copy

Sample Input 3

Copy

970
1040
0

Sample Output 3

Copy

Sample Input 4

Copy

Sample Output 4

Copy

Comments

0

Crakxinator commented 70 days ago

I'm getting TLE for case 6 and 7, idk what im doing wrong here

0

Compro72 commented 38 days ago ← edited →

Hmm I tried submitting your code using pypy as it is faster but it still fails: https://dmoj.ca/submission/6985494

The intended solution for this is to use dynamic programming but you could try using deque() in your code because it has faster appends and pops.

28

mistleutoe commented on Dec. 30, 2021, 1:15 a.m.

motel = [0, 990, 1010, 1970, 2030, 2940, 3060, 3930, 4060, 4970, 5030, 5990, 6010, 7000]

30

Evanhyd commented on Aug. 27, 2020, 12:13 a.m. ← edited →

Important tips:

With the new cases 6 and 7, you need to use long to store some important values instead of int, else it will get overflow and cause WA.

0

cz52013141834 commented on Feb. 3, 2022, 9:06 p.m.

Thank you!! This helps a lot!

4

kevze commented on May 8, 2020, 6:57 p.m.

Why am I getting WA for case 6?

Also, if you don't output a new line after your total it gives you Presentation Error.

2

JohnstonLiu commented on Feb. 12, 2020, 4:38 a.m.

You can do the problem without recursion if that's what you are looking for.

19

31501357 commented on April 14, 2019, 3:58 p.m.

Should have specified you needed long integers!

16

666245 commented on April 14, 2019, 4: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.

4

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

can they move backwards

4

Riolku commented on Jan. 14, 2019, 9:46 p.m.

no

2

TimothyW553 commented on Dec. 17, 2018, 12:43 a.m.

What happened?

3

Kirito commented on Dec. 17, 2018, 5:07 a.m. ← edited →

New testcases were added by xiaowuc1.

Edit: xiaowuc1 claims credit should go to d.

8

zys5945 commented on Oct. 14, 2015, 4:40 p.m. ← edited →

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

34

kobortor commented on Oct. 14, 2015, 5:04 p.m.

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

100

zys5945 commented on Oct. 15, 2015, 3:38 p.m.

I guess it's time for me to get glasses