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

Discussion of Problem 1289. One Way Ticket

Who can prove his algo?
Posted by Furtuna Dan Emanuel 13 Apr 2005 23:36
I solved it even without any calculations. But who can prove a formula for this task? I'm realy curios.
I can :) (+)
Posted by Michael Rybak (accepted@ukr.net) 10 Feb 2006 07:49
First you need to prove that digit root of A > 0 is A mod 9 (but not in [0..9), but in [1..9]).

After this we look at number of n/2-digit numbers with square root  equal to 0, 1, .. 9, and sum squares of those numbers, because for every left part the right part may become any value with same digit root.

Obviously, there's only 1 n/2 digit number with 0 square root - that's 000..00 (n/2 times).

As for any other Q square root, we calculate the number of items in the following sequence: Q, Q+9, Q+18, .. Qi, such that Qi < 10^n and i is maximal.

Easy to see, this is (10^(n/2) - 1 - Q) div 9 + 1, and this value doesn't depend on Q (for 1 <= Q <= 9) and is equal to (10^(n/2) - 1) div 9 = 111..11 (n/2 times); let's denote this value with W and don't forget that we take squares, not numbers themselves;

This leads to the formula: F(0)+F(1)+..+F(9) = F(0) + 9 * W * W = 1 + 9 * sqr((10^(n/2) - 1) div 9)