시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
40 초 (추가 시간 없음) | 1024 MB | 16 | 12 | 9 | 69.231% |
Alice and Bob are playing a new virtual reality team game - Street Checkers. The game is set on an insanely long street divided into tiles which are numbered from 0 to 109(inclusive of both). At the start of the game, Alice and Bob are standing on tile number 0 and are given a random number X in range [L, R] (both ends are inclusive). Alice only jumps to odd numbered tiles, while Bob only jumps to even numbered tiles. If the number on the tile divides X, then the player landing on it has to color it with their favorite color. The game is over after tile X has been colored.
A game is considered interesting by both the players if the absolute difference between the number of tiles painted by each is not greater than 2. Help Alice and Bob find how many numbers in the interval [L, R] could make for an interesting game.
The first line of the input gives the number of test cases, T. T lines follow each containing two integers L and R, the start and end of the interval used to generate the random number X.
For each test case, output one line containing Case #x: y
, where x
is the test case number (starting from 1) and y
is the count of numbers in interval [L, R] which results in an interesting game for Alice and Bob.
2 5 10 102 102
Case #1: 5 Case #2: 1
For the first sample case, let us look at all the possible number in range [5, 10]:
Thus, the answer for this test case is 5.
In the second sample case, we have only one number 102. Alice would paint 4 tiles : {1, 3, 17, 51} while Bob would paint 4 tiles : {2, 6, 34, 102}. The game would be interesting since the absolute difference is 0.
Contest > Google > Kick Start > Google Kick Start 2019 > Round E C번