| Show all threads Hide all threads Show all messages Hide all messages |
| aaa this is easyy problem | 👑TIMOFEY👑 | 1261. Tips | 26 Aug 2022 09:04 | 1 |
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! |
| Stupid brute force gives AC | 👾_challenger128_[PermSU] | 1261. Tips | 8 Mar 2021 18:51 | 1 |
Just calculate all possible sums. Then try to find some sum-n in this sums |
| I don't under the meaning of this problem.Could somebody explain? | CNEinstein | 1261. Tips | 28 Jul 2020 19:57 | 5 |
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 ? |
| answers for 528932, 386891557, 19362 | esbybb | 1261. Tips | 17 Sep 2016 22:57 | 2 |
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 |
| WA 21 | Stas | 1261. Tips | 19 Mar 2016 13:35 | 1 |
WA 21 Stas 19 Mar 2016 13:35 What is number N = ? and what to output? |
| I think the word "water" in the text should be "waiter"! poor english.... | Huang Yuanhe | 1261. Tips | 26 Feb 2013 20:26 | 2 |
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. |
| What's up?=( | Roman Furko | 1261. Tips | 20 Oct 2010 23:13 | 2 |
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. |
| Brute-force - AC 0.015 | Cat36 | 1261. Tips | 18 Mar 2010 21:30 | 2 |
Nothing to wonder: log_3(2^32) < 21, thus you need to test at most 2^21 possibilities. |
| WA 6 | unlucky [Vologda SPU] | 1261. Tips | 12 Feb 2010 02:38 | 1 |
WA 6 unlucky [Vologda SPU] 12 Feb 2010 02:38 |
| what to output if N=1 | teamSaratov | 1261. Tips | 11 Feb 2010 21:58 | 5 |
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_). |
| Hint or If you don't know how to solve... | Leonid (SLenik) Andrievskiy | 1261. Tips | 22 Jul 2009 04:32 | 1 |
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. |
| What is the Output for n=4? | Alexey | 1261. Tips | 1 Apr 2009 13:47 | 6 |
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 |
| Why WA on test 1 Help me,please | The Punisher | 1261. Tips | 23 Jul 2006 20:27 | 1 |
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 |
| it seems so easy but can't solve it; | Dulat_TKTL | 1261. Tips | 3 Feb 2006 21:50 | 6 |
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. 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? plz help | Tolstobrov_Anatoliy[Ivanovo SPU] | 1261. Tips | 11 Jan 2006 13:41 | 7 |
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. |
| need mass help!!! | Tolyan_PP | 1261. Tips | 26 Apr 2005 01:17 | 2 |
Give same tests. When output 0
Please. |
| An AC problem that does NOT work. | Evil Cheater | 1261. Tips | 23 Sep 2004 20:01 | 4 |
{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!!! Fixed. Vladimir Yakovlev (USU) 23 Apr 2004 13:59 |
