UVa 264

From Algorithmist
Jump to: navigation, search

264 - Count on Cantor[edit]

Summary[edit]

No point in brute forcing this thing 10^7 will take a long time :)

Explanation[edit]

  • We can generalize this pattern in order to figure out the fraction.
  • Try to sum up all the numbers sequentially until you have figured out the range in which your number will belong.
  • Once we establish the range, you can simply figure out the distance from the current position and finish off the problem.
  • Follow this general algorithm. Pre-compute an array of summations 4500 in length. Binary search to find exactly what diagonal in the matrix would be referenced. Next, note the when to add/subtract from the numerator and denominators. Easy solution from there.

fzort: This problem also has a O(1) solution. It's easy to compute the index d of the diagonal a given number n is in. The number of elements before diagonal d is

n={\frac  {d(d+1)}{2}}

, so the number n is in diagonal

d=\left\lfloor {\frac  {1+{\sqrt  {1+8n}}}{2}}\right\rfloor

Input[edit]

1
3
14
7
10000000

Output[edit]

TERM 1 IS 1/1
TERM 3 IS 2/1
TERM 14 IS 2/4
TERM 7 IS 1/4
TERM 10000000 IS 2844/1629

Solutions[edit]

References[edit]