1804C.md (3690B)
1 Source: https://codeforces.com/problemset/problem/1804/C 2 3 C. Pull Your Luck 4 5 time limit per test 6 7 1 second 8 9 memory limit per test 10 11 512 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 While James is gone on business, Vesper takes her time and explores what the legendary Casino Royale has to offer to people who are fond of competitive programming. 22 23 Her attention was grabbed by the very new "Pull Your Luck" roulette which functions in a pretty peculiar way. The roulette's wheel consists of $n$ sectors number from $0$ to $n - 1$. There is no ball and the winning sector is determined by a static arrow pointing to one of the sectors. Sectors' indexes go in the natural order and the wheel always spins in the direction of indexes increment. That means that sector $i + 1$ goes right after sector $i$ for all $i$ from $0$ to $n - 2$, and sector $0$ goes right after sector $n - 1$. 24 25 After a bet is made, the player is allowed to pull the triggering handle herself and cause the wheel to spin. If the player's initial pull is made with the force equal to positive integer $f$, the wheel will spin for $f$ seconds. During the first second it will advance $f$ sectors, the next second it will advance $f - 1$ sectors, then $f - 2$ sectors, and so on until it comes to a complete stop. After the wheel comes to a complete stop, the sector which the arrow is pointing to is the winning one. 26 27 The roulette's arrow currently points at sector $x$. Vesper knows that she can pull the handle with any integer force from $1$ to $p$ inclusive. Note that it is not allowed to pull the handle with force $0$, i. e. not pull it all. The biggest prize is awarded if the winning sector is $0$. Now Vesper wonders if she can make sector $0$ win by pulling the triggering handle exactly once? 28 29 Input 30 31 The first line of the input contains a single integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases. Then follow $t$ lines containing one test description each. 32 33 Each test description consists of three integers $n$, $x$ and $p$ ($3 \leq n \leq 10^5$, $0 \leq x \lt n$, $1 \leq p \leq 10^9$). They are the number of sectors on the wheel, the current sector the arrow points at, and the maximum force that Vesper can pull the handle with, respectively. 34 35 It is guaranteed that the sum of $n$ over all test cases doesn't exceed $2 \cdot 10^5$. 36 37 Output 38 39 Print $t$ lines, the $i$-th line should contain the answer for the $i$-th test case. If it is possible to pull the handle with the integer force from $1$ to $p$ in order to make sector $0$ win, print "Yes". Otherwise, print "No". 40 41 You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses. 42 43 Example 44 45 Input 46 47 ``` 48 7 49 50 5 2 1 51 52 5 2 2 53 54 10 0 100 55 56 11 7 100 57 58 3 1 1000 59 60 31 0 10 61 62 100 49 7 63 ``` 64 65 Output 66 67 ``` 68 No 69 Yes 70 Yes 71 Yes 72 No 73 No 74 No 75 ``` 76 77 Note 78 79 In the first example, the only possible way to pull the handle is with force $1$. That is not enough to make the arrow point at sector $0$, at least force $2$ is required to do so. 80 81 In the second example, Vesper can pull the handle with the force $2$ so the wheel will spin $2 + 1 = 3$ sectors ahead and the arrow will point at sector $0$. 82 83 In the third example, Vesper can pull the handle with the force $4$ so the wheel will spin $4 + 3 + 2 + 1 = 10$ sectors and will point at sector $0$ again. 84 85 In the fourth example, Vesper can pull the handle with the force $5$ so the wheel will spin $5 + 4 + 3 + 2 + 1 = 15$ sectors. That will make the wheel make one full turn plus $4$ more sectors. 86 87 In the fifth example, whatever force Vesper chooses to pull the handle with, she can only make sectors $1$ and $2$ win.