| ENG RUS | Timus Online Judge |
Discussion of Problem 1289. One Way Ticketurusant A misprint in statement // Problem 1289. One Way Ticket 19 May 2014 10:56 The second word should be "crowd", according to the Russian translation. Maigo Akisame (maigoakisame@yahoo.com.cn) What should I do if N is odd? What's the first 'half' and the second 'half' in this case? [4] // Problem 1289. One Way Ticket 20 Sep 2004 20:24 Dmitry 'Diman_YES' Kovalioff N is always even - see russian version :) (-) [3] // Problem 1289. One Way Ticket 20 Sep 2004 21:42 Vladimir Yakovlev (USU) I correct english version. // Problem 1289. One Way Ticket 21 Sep 2004 13:00 Maigo Akisame (maigoakisame@yahoo.com.cn) But I'm sorry I don't know Russian. [1] // Problem 1289. One Way Ticket 21 Sep 2004 20:13 AYUBXON UBAYDULLAYEV TUIT Re: But I'm sorry I don't know Russian. // Problem 1289. One Way Ticket 22 Nov 2012 13:00 manishmmulani those who want hint [1] // Problem 1289. One Way Ticket 4 Jan 2008 01:44 for N, ####...N/2times ####...N/2 times consider first half N/2 digits sum(digit root) will always be from 0 to 9 it will be 0 only if all digits are 0's and it'll will 1,2,3 .... ,9 in other cases... for N=4 first half will have 2 digits ( total 100 numbers ) 1 number(00) will have digit root = 0 99 numbers will have digit root other than 0 ( i.e 11 numberes --> digit root 1 , 11 numbers ---> digit root 2 etc ) so for N=4 , case i : first half = 00 second half =00 -----> n1 = 1 case ii: first half --> 99 ways , second half --> 11 ways n2= 99*11 total number = n1+n2 = 99*11 + 1 similarly for N=6 , we have 999*111 + 1 N=8 , 9999*1111 + 1 so on... ASK Hint // Problem 1289. One Way Ticket 17 Mar 2010 15:17 Do not use BigInteger to calculate. Let k = n/2, then the result is 10 for k=1; otherwise it is a concatenation of "1"x(k-1), "0", "8"x(k-2), and "90": 1 10 2 1090 3 110890 4 11108890 5 1111088890 6 111110888890 7 11111108888890 8 1111111088888890 9 111111110888888890 tbtbtb How to slove it?? [3] // Problem 1289. One Way Ticket 30 Apr 2004 16:50 Tratata (barssimfi@mail.ru) Re: How to slove it?? [1] // Problem 1289. One Way Ticket 27 Jul 2004 21:50 It is very simple problem. Just generate first 5-10 answers. Than U will see how to solve it :-) Edited by author 27.07.2004 21:51 Peter Ivanov Re: How to slove it?? // Problem 1289. One Way Ticket 27 Aug 2006 04:12 I don't consider this explanation for a reasonable one. If it is so easy - you are to prove it! Otherwise solving it in your way won't help to better understanding the theory behind this concrete problem. TIA (Lyceum #165) Re: How to slove it?? // Problem 1289. One Way Ticket 7 Feb 2008 23:17 This problem is easy. Just count number of numbers with the same digit root of its half where digit root is equal to 0,1,2,3,4,5,6,7,8,9. Number where digit root is equal to 0 is 0. Use /dev/brain to count the other numbers P.S. digit root(n)=digit root(n+9) kkkkk what's answer for 3?Who can tell me? [1] // Problem 1289. One Way Ticket 26 Aug 2004 18:48 and what for 5?for 8? TIA (Lyceum #165) Re: what's answer for 3?Who can tell me? // Problem 1289. One Way Ticket 7 Feb 2008 23:12 Read carefully: N is even dimozzz I don't understand why It's true???? // Problem 1289. One Way Ticket 27 Apr 2007 21:35 if(n == 2){ System.out.println("10"); return; } for(i = 0;i < n / 2 - 1;i ++){ System.out.print("1"); } System.out.print("0"); for(i = 0;i < n / 2 - 2;i ++){ System.out.print("8"); } System.out.println("90"); PSV Strange!! Help me please // Problem 1289. One Way Ticket 23 Dec 2006 18:52 I think that I must ouput some amount of 1 then 0 and then one smaller than 1 I output 8 and then 90. Amount of 1 and 8 depends on n. But if its right formula I have no time to output answer => TLE1 test!! Help please, what's wrong Furtuna Dan Emanuel Who can prove his algo? [1] // Problem 1289. One Way Ticket 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. Michael Rybak (accepted@ukr.net) I can :) (+) // Problem 1289. One Way Ticket 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) Alexandru Popa I get WA and I don't know why ? Can you give me the result for n = 20 or n = 30 [1] // Problem 1289. One Way Ticket 30 Jan 2005 23:06 Victor Barinov (TNU) My AC program sayd: (+) // Problem 1289. One Way Ticket 30 Jan 2005 23:33 n = 20; 11111111108888888890 n = 30; 111111111111110888888888888890 PW what's answer for 4?-->>1000? [1] // Problem 1289. One Way Ticket 28 Aug 2004 21:07 Danica Porobic Re: what's answer for 4?-->>1000? // Problem 1289. One Way Ticket 28 Aug 2004 22:15 1090
|