DMOPC '15 Contest 5 P4 - Steins;Number - Olympiads Online Judge

DMOPC '15 Contest 5 P4 - Steins;Number

Points: 12 (partial)

Time limit: 1.0s

Memory limit: 64M

Author:

Problem type

"I am mad scientist, Hououin Kyouma!" - Okabe Rintarou

Most computer scientists are obsessed with powers of 2 and the binary number system. However, as a mad scientist, Okabe is instead obsessed with the powers of 3. He is especially passionate about the set of numbers that he refers to as Steins;Numbers. According to Okabe's definition, a number is a Steins;Number if it can be written as the sum of distinct powers of 3, including 1.

For example, 12 and 31 are both Steins;Numbers.

$\displaystyle 12 = 3^1 + 3^2$ $$\displaystyle 12 = 3^1 + 3^2$$

$\displaystyle 31 = 3^0 + 3^1 + 3^3$ $$\displaystyle 31 = 3^0 + 3^1 + 3^3$$

Okabe just boasted to Kurisu that he knows all the Steins;Numbers. Kurisu didn't believe him, so she asked him $Q$ ~Q~ queries of the following form:

Given numbers $L$ ~L~ and $R$ ~R~, how many Steins;Numbers are between $L$ ~L~ and $R$ ~R~, inclusive?

Okabe is nervous about making a mistake in his calculations. Wanting to impress Kurisu, he turned to you for help.

Constraints

Subtask 1 [20%]

$1 \le Q \le 100$ ~1 \le Q \le 100~

$1 \le L \le R \le 10^9$ ~1 \le L \le R \le 10^9~

Subtask 2 [80%]

$1 \le Q \le 10\,000$ ~1 \le Q \le 10\,000~

$1 \le L \le R \le 10^{18}$ ~1 \le L \le R \le 10^{18}~

Input Specification

The first line of input will contain $Q$ ~Q~. Each of the next $Q$ ~Q~ lines will contain a query of the form L R.

Output Specification

Output the answer to each query on a separate line.

Sample Input

1
9 12

Sample Output

Explanation

9, 10, and 12 are the three Steins;Numbers in the given range.

Comments

0

JeffreyZ commented on Feb. 11, 2016, 5:58 a.m. ← edited →

Hey, I've submitted the same code here and here, and got two different results. I was able to reproduce this in following submissions as well (189005 and 189006). It seems that every other time I submit, I fail the pretest. Is this intended?

0

jeffreyxiao commented on Feb. 11, 2016, 11:50 p.m.

I'm guessing that using double creates inconsistent behavior. Try long double?

0

JeffreyZ commented on Feb. 12, 2016, 12:17 a.m. ← edited →

Doesn't seem to fix it. Also, I just did ten submissions and the pattern is consistent: every other submission gets WA on the pretest.

EDIT: Converting the argument of log() to long double fixed it, though I'm still curious as to why only every other submission had the problem.

0

jeffreyxiao commented on Feb. 12, 2016, 1:33 a.m.

There are more than one judge so it might be alternating between them.