AC in 0.015 is possible without any precalculations. Make a function that returns the quiet days until day N The answer is F(r) - F(l). The is a special case if l has to be counted - that happens if F(l) != F(l-1) (in other words F(l) is part of the sequence we are looking for) If l=1, just return F(r) The implementation of F(n) can be simple if you find the right approach. It's simple to count how many days remain in the sequence after eliminating each 2nd, then each 3rd, and so on. Count numbers X and Y of quiet days for vacations given by intervals [1;r] and [1;l-1]. The answer to the problem would be ANS=X-Y. How to count X and Y? In the first step, we eliminate every 2th. That is, CNT_0=r and and CNT_1=r//2 In the second step, CNT_2=CNT_1//3. And so on. Until CNT > 0. Last non-zero CNT is the answer. Yes, but you should prove that the number of steps is short enough. Here is some sketch of the proof. After deleting all 2nd numbers we are with $\frac{n}{2}$ numbers, after erasing all 3rd numbers we are with $\frac{2}{3}\cdot \frac{n}{2} = \frac{n}{3}$ numbers, after erasing all 4th numbers we are with $\frac{3}{4}\cdot \frac{n}{3} = \frac{n}{4}$ numbers and so on, after erasing every $k$-th number we are left with $\frac{n}{k}$ numbers, and we stop when $\frac{n}{k} < (k+1)\implies k \approx \sqrt{n}$, so after $O(\sqrt{n})$ steps the algorithm stops. Edited by author 02.01.2021 20:07 Edited by author 02.01.2021 20:07 Edited by author 02.01.2021 20:09 Can you give me some tests, please? I don't understand why WA. 1 10^9 should be 35682 (apparently? i might be wrong) If you have a few spare gigabytes of RAM, you can simulate the thing by yourself. Initially we have 1 2 3 ... 10^9, after 1st step 1 3 5 etc (+2 +2 +2 etc), after 2nd step it's 1 3 7 9 13 15 (+2 +4 +2 +4 +2 +4 etc), after 3rd step it's 1 3 7 13 15 19 25 27 31 (+2 +4 +6 +2 +4 +6 +2 +4 +6 etc). Only on 4th step it becomes complicated and loses pattern. So for further simulation, you need 1 array of 10^9 / 2 / 2 + 1 4-byte integers from 3rd step (1 and [+2 +4 +6 cycle]), which is ~1GB, and another ~1GB array to copy elements into. I also found the sequence on OEIS: https://oeis.org/A000960, but still, i can't quite understand some things. For example: «To get n-th term, start with n and successively round up to next 2 multiples of n-1, n-2, ..., 1 (compare to Mancala sequence A002491). E.g.: to get 11th term: 11->30->45->56->63->72->80->84->87->90->91; i.e., start with 11, successively round up to next 2 multiples of 10, 9, .., 1. - Paul D. Hanna, Oct 10 2005» — what is this even? I have a hard time understanding what exactly is done here... It means to get n-th number you need to increase n step-by-step. At each step you increase your current number twice to the nearest number divisible by n - 1, n - 2, ..., 1 depending on each step you are now. Example: n = 11, nearest to 11 divisible by 10 is 20, next one is 30. nearest to 30 dibisible by 9 is 36 and next one is 45. And so on 11->30->45->56->63->72->80->84->87->90->91 1 10^9 should be 35682 (apparently? i might be wrong) If you have a few spare gigabytes of RAM, you can simulate the thing by yourself. Initially we have 1 2 3 ... 10^9, after 1st step 1 3 5 etc (+2 +2 +2 etc), after 2nd step it's 1 3 7 9 13 15 (+2 +4 +2 +4 +2 +4 etc), after 3rd step it's 1 3 7 13 15 19 25 27 31 (+2 +4 +6 +2 +4 +6 +2 +4 +6 etc). Only on 4th step it becomes complicated and loses pattern. So for further simulation, you need 1 array of 10^9 / 2 / 2 + 1 4-byte integers from 3rd step (1 and [+2 +4 +6 cycle]), which is ~1GB, and another ~1GB array to copy elements into. I also found the sequence on OEIS: https://oeis.org/A000960, but still, i can't quite understand some things. For example: «To get n-th term, start with n and successively round up to next 2 multiples of n-1, n-2, ..., 1 (compare to Mancala sequence A002491). E.g.: to get 11th term: 11->30->45->56->63->72->80->84->87->90->91; i.e., start with 11, successively round up to next 2 multiples of 10, 9, .., 1. - Paul D. Hanna, Oct 10 2005» — what is this even? I have a hard time understanding what exactly is done here... Thank you! Your explanation is much more clear. Original should probably have "the 2nd closest multiple" instead of "next 2 multiples", would make more sense. 10 18 => 1 666 999 => 6 13 100000 => 354 123456789101112 12345678910111213 => 112837915 1 1000000000 => 35682 1 1000000000000 => 1128378 Edited by author 10.07.2016 18:37 Thanks a lot!!! I got AC. 10 18 => 1 666 999 => 6 13 100000 => 354 123456789101112 12345678910111213 => 112837915 1 1000000000 => 35682 1 1000000000000 => 1128378 Edited by author 10.07.2016 18:37 Why isn't wrong? 10 18 => 1 Edited by author 20.03.2017 20:45 Please help!!! Getting WA 22 |
|