I'm tried to solve it many times and this problem dont need strong. There is no need to count a lot, compare numbers, check so that all the money can be divided, all you need is to take all the powers of three and check for each that in sum with n it also gives the sum of the powers of three. That is, t is the sum of degrees, if t+n too, then output the answer immediately! Just calculate all possible sums. Then try to find some sum-n in this sums A programmer has a set of banknotes valued 1, 3, 9 ..., 3^k,... one each. He has to pay N in a restaurant (provided) He must pay that much M so: M can be paid with banknotes the programmer has, i.e. he cannot pay 5, because he does not have 2 bank notes with value of 1; and M-N must be represented the same way, i.e. if N is 4, M cannot be 9, because 5 cannot be represented as a sum of 3^K, one or less for each K. So if asked 4, a programmer must pay 13, 13=9+3+1, 13-4=9. I hope you will understand this clumsy explanation. Thanks for the explanation. here 4 can be represented as 1+3^1 . why i have to pay 13 ? I failed to understand the problem ? 708591 179659 (or 531444 2512) 387600148 708591 (or 387423001 531444) 19686 324 These answers are right too: 528932 => 531480 2548 386891557 => 387686170 794613 19362 => 19723 361 What is number N = ? and what to output? Not only that. "Waiters like to get the sum of money that can be presented" in fact means "Waiters like to get the *tip* that can be presented", rather than "Waiters like to get the *total payment* that can be presented" -- which is the natural interpretation. I can't take a[0..25000000]of boolean; Memore Limit? Why? This Massive is only max 15 mb No, because boolean variables are represented as a size of 1 byte memory locations. So size of your array is nearly 25Mb. Nothing to wonder: log_3(2^32) < 21, thus you need to test at most 2^21 possibilities. can anyone please tell me what to output if N=1 is given? well, when I added to code: if N=1 then begin writeln('0'); halt; end; I've got WA on test 1. With out such code I've got WA on test 7. So, test 1 - N=1. But I'm not sure in correct solution: my program outputs 4 3. But 4 can be got only like: 4 = 1 + 3; So, then change is already included in paying. Smth strange, don't you think so? I had WA1 with output 0 for N=1. With 4 3 I passed 1st test but failed with WA9 which is something like 12 or 81. So, amount of tips must be POSITIVE. Edited by author 01.08.2008 00:48 why when n=1 answer 4 3? i think it must be 3 2!! 2 can't be representeted of sum numbers(3^n, where every N can be used _1 time_). 1. In a few words: you should find x1 and x2, such that: a) x1 - x2 = N b) x1 and x2 has only '0' and '1' numbers in ternary number system. c) x1 & x2 = 0. x1 and x2 are written in ternary number system. '&' means logical AND operation [0 & 0 = 0, 0 & 1 = 0, 1 & 0 = 0, 1 & 1 = 1], which is applied to the corresponding pairs of digits from the x1 and x2 (in ternary number system). 2. I recommend you to write a) and b) conditions for all digits of the x1 and x2 in ternary number system, and then in decimal number system. 3. You should differ only two variants: if N has only '0' and '1' numbers in ternary number system and the opposite variant. 4. If you need some other hints, you can write me shellkunchik<at>yandex<point>com. Tell me, please, what is the Output for 1) N=4 2) N=10 3) N=3^m (For example, N=27) Please, help... Thanks a lot. Here are my answers but they are not unique I think 4 13 9 10 37 27 9 36 27 27 108 81 81 324 243 Thanks A Lot! I've got AC!!! What formalization? N=a-b; b>0; a and b have no digit 2 in 3-system? Edited by author 30.06.2007 13:50 Edited by author 30.06.2007 13:51 Why 10 37 27? a = 10(10)=101(3) b = 3(10) =010(3) a+b = 13(10)=111(3) IMHO, right ansver is 10 13 3 Excuse me, I've found a bug and ACed this problem. Edited by author 23.07.2006 20:36 Edited by author 23.07.2006 20:36 I tried many times Please help!!!!!! I don't remember exactly, I've solved this problem more than a year ago... But as I ramember it's easy to solve it if transform the numer in base of 3 format. P.S. Sorry for my poor english. must we use array I did. simply pre-generate all numbers that are sums of different powers of 3: 1. array <- 0 2. for item in array: array <- 3 + item 3. for item in array: array <- 9 + item 4. for item in array: array <- 27 + item 5. for item in array: array <- 81 + item ... until current power of 3 becomes larger than N * 3 + 1 (so it works for N = 1). You should prove that there's no use to check any powers of 3 that are larger than N * 3 + 1. Use the fact that 1 + 3 + 9 + 27 + .. + 3 ^ k = 3 ^ (k + 1) / 2, which means that no number in interval (3^k / 2, 3^k - 1) can be represented in that fashion. P.S. Note that the generated array will be sorted already, so no need to perform a sorting if input 100!!! what output? For example, 100 = 112 - 12. 112 and 12 have only digits 0 and 1 in 3-base record. Good luck! Man where you take 112? asked me plz! I've solved in the following way: 1. i've found the representation of the given number in the 3-base system as the result - array of coefficients from the set [0, 1, 2] 2. every coef =2 converted to 3 (or +1 for the next coef). if you still have questions mail to p_s_@list.ru
I had the same idea dut got WA1, with this code: Var n,k,z,i : word; sum,x : int64; a :array[1..10000] of byte; BEGIN Read(n); z := n; k := 1; while n <> 0 do Begin a[k] := n mod 3; n := n div 3; Inc(k); End; For n := 1 to 10000 do Begin if a[n] = 2 then Begin a[n] := 0; Inc(a[n+1]); End; if a[n] > 2 then Begin Inc(a[n+1],a[n] div 3); a[n] := a[n] mod 3; End; End; sum := a[1]; For n := 2 to k+10 do Begin if a[n] <> 0 then Begin x := 1; For i := 1 to n-1 do x := x*3; Inc(sum,x*a[n]); End; End; if sum <> z then Writeln(sum,' ',sum - z) Else Write(0); END. Give same tests. When output 0 Please. {584156 09:52:24 18 Apr 2004 Evil Cheater 1261 Pascal Accepted 0.031 373Kb} Begin writeln(output,'14348908 14348907'); End. I think the judge must chech this things: 1.- pay > check. 2.- pay and tip must be only 1 and 0 in base 3. 3.- pay = check + tip. Maybe the judge checks 1 and 2, but not 3. {584156 09:52:24 18 Apr 2004 Evil Cheater 1261 Pascal Accepted 0.031 373Kb} Begin writeln(output,'14348908 14348907'); End. I think the judge must chech this things: 1.- pay > check. 2.- pay and tip must be only 1 and 0 in base 3. 3.- pay = check + tip. Maybe the judge checks 1 and 2, but not 3. The method is wrong,but gamble!!! |
|