ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
back to board

Discussion of Problem 1209. 1, 10, 100, 1000...

another hint
Posted by So Sui Ming 16 Jan 2024 19:23
Stack 1,10,100,1000,10000,100000,... vertically:

the cumulative sums of digits from the top are:
1,3,6,10,15,21,... which are in the form of combination(N,2) = N*(N-1)/2

checking whether one is at Kth digit is the same as finding if there is integer solution to:
N*(N-1)/2 = K-1

one way is to solve the quadratic equation for N (in double) and cast N to integer and check the above relation.
So Sui Ming

Edited by author 16.01.2024 19:27

Edited by author 16.01.2024 19:27
Re: another hint
Posted by Pedro[UFES] 15 May 2024 06:02
Great solution, So Sui Ming, I did not think about that one in particular.

I just use prefix sums and binary search.

If you write down the sequence and it's index starting from 1.

You will notice that if you do prefix sum ( half interval way , so starting from 0, the first element, first element + second element, etc. ) up till  sum <= MAX ( 2^31 - 1 ), you will get 65535 numbers in a sorted way.

In this way, notice, that the numbers in this prefix_sum array are all index s.t. digit = 1.

You still need to +1 in every position of prefix_sum array, because of 1-index of input.

Now you read input number K and do binary search on the prefix sum array.

If you did find, great! It is 1.
Otherwise, it is 0.