CCC '17 J4 - Favourite Times - DMOJ: Modern Online Judge

CCC '17 J4 - Favourite Times

Points: 5 (partial)

Time limit: 1.0s

Memory limit: 256M

Problem type

Canadian Computing Competition: 2017 Stage 1, Junior #4

Wendy has an LED clock radio, which is a 12-hour clock, displaying times from $\tt 12:00$ $12 : 00$ to $\tt 11:59$ $11 : 59$ . The hours do not have leading zeros but minutes may have leading zeros, such as $\tt 2:07$ $2 : 07$ or $\tt 11:03$ $11 : 03$ .

When looking at her LED clock radio, Wendy likes to spot arithmetic sequences in the digits. For example, the times $\tt 12:34$ $12 : 34$ and $\tt 2:46$ $2 : 46$ are some of her favourite times, since the digits form an arithmetic sequence.

A sequence of digits is an arithmetic sequence if each digit after the first digit is obtained by adding a constant common difference. For example, $1,2,3,4$ $1, 2, 3, 4$ is an arithmetic sequence with a common difference of $1$ $1$ , and $2,4,6$ $2, 4, 6$ is an arithmetic sequence with a common difference of $2$ $2$ .

Suppose that we start looking at the clock at noon (that is, when it reads $\tt 12:00$ $12 : 00$ ) and watch the clock for some number of minutes. How many instances are there such that the time displayed on the clock has the property that the digits form an arithmetic sequence?

Input Specification

The input contains one integer $D$ $D$ $(0 \le D \le 1\,000\,000\,000)$ $(0 \leq D \leq 1 000 000 000)$ , which represents the duration that the clock is observed.

For 4 of the 15 available marks, $D \le 10\,000$ $D \leq 10 000$ .

Output Specification

Output the number of times that the clock displays a time where the digits form an arithmetic sequence starting from noon ( $\tt 12:00$ $12 : 00$ ) and ending after $D$ $D$ minutes have passed, possibly including the ending time.

Sample Input 1

Copy

Sample Output 1

Copy

Explanation for Sample Output 1

Between $\tt 12:00$ $12 : 00$ and $\tt 12:34$ $12 : 34$ , there is only the time $\tt 12:34$ $12 : 34$ for which the digits form an arithmetic sequence.

Sample Input 2

Copy

Sample Output 2

Copy

Explanation for Sample Output 2

Between $\tt 12:00$ $12 : 00$ and $\tt 3:00$ $3 : 00$ , the following times form arithmetic sequences in their digits (with the difference shown):

$\tt 12:34$ $12 : 34$ (difference 1),
$\tt 1:11$ $1 : 11$ (difference 0),
$\tt 1:23$ $1 : 23$ (difference 1),
$\tt 1:35$ $1 : 35$ (difference 2),
$\tt 1:47$ $1 : 47$ (difference 3),
$\tt 1:59$ $1 : 59$ (difference 4),
$\tt 2:10$ $2 : 10$ (difference -1),
$\tt 2:22$ $2 : 22$ (difference 0),
$\tt 2:34$ $2 : 34$ (difference 1),
$\tt 2:46$ $2 : 46$ (difference 2),
$\tt 2:58$ $2 : 58$ (difference 3).

Comments

2

Idkhmm293 commented 42 days ago

I wasted so long because I thought the digits could go like 1, 0, 9 with the difference being -1. Dont be a silly billy like me

0

SillyBilly27 commented 33 days ago

you know who is a sillybilly???

1

PHo3NIX commented 57 days ago

be careful if the imput is larger than 720, lol.

3

zhuxilai142857 commented on Oct. 10, 2022, 6:23 a.m.

How can I fix the TLE problem?

6

volcano commented on Oct. 10, 2022, 3:31 p.m.

How many such arithmetic sequences appear in the 12-hour (720-minute) cycle?

If the input exceeds 720, do we really need to compute all the arithmetic sequences? Won't that take too long?

This is why you TLE.

0

MrBloc01 commented on Jan. 20, 2022, 11:58 p.m.

can anybody check my latest submission

1

Spitfire720 commented on Jan. 21, 2022, 1:22 a.m.

Test cases like 900, 3600 and 6969 fail

0

Haoyun commented on Feb. 1, 2022, 6:06 p.m. ← edit 5 →

What would be the answer, mine is 42, 156 and 309 and DMOJ says mine is wrong┭┮﹏┭┮

0

bloomfield commented on May 14, 2022, 3:56 p.m. ← edited →

D:

8

Dav_Did commented on Feb. 3, 2021, 3:19 a.m.

What a shame "6:66" isn't a thing.

7

herro commented on Feb. 10, 2020, 9:58 p.m.

Wow! 2017 was filled with Math questions! Interesting.

-4

BLYAT commented on May 25, 2019, 12:51 a.m.

I keep getting tle at start of batch#3 help

7

Plasmatic commented on May 25, 2019, 5:13 a.m.

D has a max value of 1 billion. Looping through all values is too slow

33

Dordor1218 commented on June 23, 2018, 6:46 p.m. ← edited →

The perfect way to describe this question: observing a clock for up to 1901 years. Hmmm... Not bad ill just see how many times my favourite number comes on! Oh btw my favourite number are only patterns how sad

3

MrBloc01 commented on Jan. 19, 2022, 11:39 p.m. ← edit 2 →

lol, imagine doing that

2

TimothyW553 commented on Sept. 2, 2017, 12:35 a.m.

No j5?

19

wleung_bvg commented on Sept. 2, 2017, 12:52 a.m. ← edited →

J5 is the same question as S3 https://dmoj.ca/problem/ccc17s3