ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
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:

1
10
100
1000
10000
100000
...
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.
regards,
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.