| ENG RUS | Timus Online Judge |
Обсуждение задачи 1261. Чаевые👑TIMOFEY👑 aaa this is easyy problem // Задача 1261. Чаевые 26 авг 2022 09:04 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! 👾_challenger128_[PermSU] Stupid brute force gives AC // Задача 1261. Чаевые 8 мар 2021 18:51 Just calculate all possible sums. Then try to find some sum-n in this sums CNEinstein I don't under the meaning of this problem.Could somebody explain? [4] // Задача 1261. Чаевые 17 апр 2004 20:36 Vesper Re: I don't under the meaning of this problem.Could somebody explain? [3] // Задача 1261. Чаевые 21 апр 2004 17:46 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. CNEinstein Thanks you for your help! I got AC. // Задача 1261. Чаевые 21 апр 2004 21:34 Edric Mao Re: I don't under the meaning of this problem.Could somebody explain? // Задача 1261. Чаевые 25 окт 2011 19:49 Thanks for the explanation. Ahmmed Jubayer Rumman Re: I don't under the meaning of this problem.Could somebody explain? // Задача 1261. Чаевые 28 июл 2020 19:57 here 4 can be represented as 1+3^1 . why i have to pay 13 ? I failed to understand the problem ? esbybb answers for 528932, 386891557, 19362 [1] // Задача 1261. Чаевые 28 май 2016 22:08 708591 179659 (or 531444 2512) 387600148 708591 (or 387423001 531444) 19686 324 Combatcook Re: answers for 528932, 386891557, 19362 // Задача 1261. Чаевые 17 сен 2016 22:57 These answers are right too: 528932 => 531480 2548 386891557 => 387686170 794613 19362 => 19723 361 Stas WA 21 // Задача 1261. Чаевые 19 мар 2016 13:35 What is number N = ? and what to output? Huang Yuanhe I think the word "water" in the text should be "waiter"! poor english.... [1] // Задача 1261. Чаевые 6 апр 2004 09:05 tyomitch Re: I think the word "water" in the text should be "waiter"! poor english.... // Задача 1261. Чаевые 26 фев 2013 20:26 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. Roman Furko What's up?=( [1] // Задача 1261. Чаевые 20 окт 2010 22:46 I can't take a[0..25000000]of boolean; Memore Limit? Why? This Massive is only max 15 mb KALO Re: What's up?=( // Задача 1261. Чаевые 20 окт 2010 23:13 No, because boolean variables are represented as a size of 1 byte memory locations. So size of your array is nearly 25Mb. Cat36 Brute-force - AC 0.015 [1] // Задача 1261. Чаевые 2 ноя 2008 06:54 ASK Re: Brute-force - AC 0.015 // Задача 1261. Чаевые 18 мар 2010 21:30 Nothing to wonder: log_3(2^32) < 21, thus you need to test at most 2^21 possibilities. unlucky [Vologda SPU] WA 6 // Задача 1261. Чаевые 12 фев 2010 02:38 Test: 8 Ans 9 1 teamSaratov what to output if N=1 [4] // Задача 1261. Чаевые 1 авг 2006 13:37 can anyone please tell me what to output if N=1 is given? teamSaratov Re: what to output if N=1 [3] // Задача 1261. Чаевые 1 авг 2006 13:47 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? Denis Koshman Re: what to output if N=1 [2] // Задача 1261. Чаевые 1 авг 2008 00:42 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 Bobur Re: what to output if N=1 [1] // Задача 1261. Чаевые 26 окт 2008 19:34 why when n=1 answer 4 3? i think it must be 3 2!! unlucky [Vologda SPU] Re: what to output if N=1 // Задача 1261. Чаевые 11 фев 2010 21:58 2 can't be representeted of sum numbers(3^n, where every N can be used _1 time_). Leonid (SLenik) Andrievskiy Hint or If you don't know how to solve... // Задача 1261. Чаевые 22 июл 2009 04:32 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. Alexey What is the Output for n=4? [5] // Задача 1261. Чаевые 26 апр 2006 18:32 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. Cybernetics Team Re: What is the Output for n=4? [4] // Задача 1261. Чаевые 27 апр 2006 21:53 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 Alexey Thanks a lot! // Задача 1261. Чаевые 28 апр 2006 20:14 Thanks A Lot! I've got AC!!! svr Re: What is the Output for n=4? [1] // Задача 1261. Чаевые 30 июн 2007 13:46 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 Denis Koshman Re: What is the Output for n=4? // Задача 1261. Чаевые 1 авг 2008 00:49 Yes. vetas Re: What is the Output for n=4? // Задача 1261. Чаевые 1 апр 2009 13:47 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 The Punisher Why WA on test 1 Help me,please // Задача 1261. Чаевые 23 июл 2006 20:27 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 Dulat_TKTL it seems so easy but can't solve it; [5] // Задача 1261. Чаевые 30 янв 2006 15:14 I tried many times Please help!!!!!! Sid Re: it seems so easy but can't solve it; [4] // Задача 1261. Чаевые 1 фев 2006 23:35 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. Dulat_TKTL Re: it seems so easy but can't solve it; [3] // Задача 1261. Чаевые 2 фев 2006 14:15 must we use array Michael Rybak (accepted@ukr.net) Re: it seems so easy but can't solve it; [2] // Задача 1261. Чаевые 3 фев 2006 19:05 I did. Aybek_TKTL Re: it seems so easy but can't solve it; [1] // Задача 1261. Чаевые 3 фев 2006 19:58 how? Michael Rybak (accepted@ukr.net) писал(a) 3 февраля 2006 19:05 I did. Michael Rybak (accepted@ukr.net) Re: it seems so easy but can't solve it; // Задача 1261. Чаевые 3 фев 2006 21:50 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 Tolstobrov_Anatoliy[Ivanovo SPU] if input 100!!! what output? plz help [6] // Задача 1261. Чаевые 8 июн 2005 02:17 if input 100!!! what output? Sandro Re: if input 100!!! what output? plz help [5] // Задача 1261. Чаевые 12 июн 2005 23:19 For example, 100 = 112 - 12. 112 and 12 have only digits 0 and 1 in 3-base record. Good luck! Tolstobrov_Anatoliy[Ivanovo SPU] Re: if input 100!!! what output? plz help [4] // Задача 1261. Чаевые 23 июн 2005 22:45 Man where you take 112? asked me plz! Protsenko Sergey[Ivanovo SPU] Re: if input 100!!! what output? plz help [3] // Задача 1261. Чаевые 26 июн 2005 23:40 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 Tolstobrov_Anatoliy[Ivanovo SPU] Re: if input 100!!! what output? plz help // Задача 1261. Чаевые 13 авг 2005 20:05 Protch I DO it. ZiV Re: if input 100!!! what output? plz help [1] // Задача 1261. Чаевые 10 янв 2006 13:53 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. ACM.Krupko_Victor[Ivanovo SPU] I help you give me your email // Задача 1261. Чаевые 11 янв 2006 13:41 Tolyan_PP need mass help!!! [1] // Задача 1261. Чаевые 24 апр 2005 18:14 Give same tests. When output 0 Please. Виктор Крупко 1<=n<=10^2003 // Задача 1261. Чаевые 26 апр 2005 01:17 Evil Cheater An AC problem that does NOT work. [3] // Задача 1261. Чаевые 18 апр 2004 10:01 {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. 黄源河 Re: An AC problem that does NOT work. [1] // Задача 1261. Чаевые 22 апр 2004 18:38 Evil Cheater писал(a) 18 апреля 2004 10:01 {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!!! Maigo Akisame (maigoakisame@yahoo.com.cn) Why must tip be all 1 and 0 in base 3? // Задача 1261. Чаевые 23 сен 2004 20:01 Vladimir Yakovlev (USU) Fixed. // Задача 1261. Чаевые 23 апр 2004 13:59
|