[Algorytm] Optymalne odważniki na szalce.

Witam, mam taki problem algorytmiczny:

Mamy n=20 odważników, których masa m(i) = 3^i. Na wejściu podajemy masę m przedmiotu, który należy zważyć przy pomocy wagi szalkowej. Wyjście ma zwrócić numery porządkowe odważników, jakie należy ustawić na szalce pierwszej (z przedmiotem) i szalce drugiej (w dwóch liniach).

Przykład: m=5
0(1) 2(3) - 3(9)
spr.: 5+1+3 = 9

O ile można by ten przykład zrobić w następujący sposób:

Szalka 2: odważnik o masie większej i jak najbardziej zbliżonej do masy przedmiotu
Szalka 1: przedmiot + x odwaznikow o sumie mas mniejszej od masy przedmiotu

O tyle przykład z m=11 wygląda w sposób troszkę inny:

Szalka 1: masa przedmiotu + odwaznik o masie 1
Szalka 2: odwaznik o masie 9 i odwaznik o masie 3

Zastanawiam się jak ugryźć ten problem. Proszę o pomoc i pozdrawiam :)

Najistotniejsze jest chyba spostrzeżenie, że na przeciwnej szalce umieszczamy największy dostępny odważnik o wadze nie większej od 2ciężar, np. dla 13 stawiamy 9 (132 <27), ale dla 14 dajemy już 27 s=N;
while (s!=0) {
k:=1;
while (k<abs(s)2)
k= k3
k= k / 3
if (s>0) z= -1
else z=1;
s= s + zk;
pisz(zk)
}

było bardzo podobne zadanie na jakiejś olimpiadzie (z tym, że można było użyć co najwyżej jednego odważnika o danej wadze).

nie pamiętam dokładnie całego algorytmu (nie chce mi się go przypominać), ale główny trik polegał na tym, żeby wcześniej wejściową liczbę zamienić na system trójkowy (wtedy chyba gdy wyszło zero to nic się nie robiło, gdy wyszło jeden to kładło się odważnik na jednej szalce, a gdy wyszło dwa to kładło się odważnik na drugiej szalce i chyba odejmowało się jedynkę).

A ja znam dokładne rozwiązanie tego problemu...

Odważniki to po kolei:
3^0=1
3^1=3
3^2=9
3^3=27
3^4=81
itd...

Mamy odważnik o masie m
Dodajemy kolejne potęgi trójki do tej pory aż otrzymana liczba będzie większa od m... Przykład:
m=35
1<35
1+3<35
1+3+9<35
1+3+9+27=40 >35
Ok mamy więc liczbę 40... Teraz dodajemy tą liczbę do liczby m: 40+35=75
Dzielimy otrzymaną sumę przez 3 i zapisujemy reszty z dzielenia:
75 |0
25 |1
8 |2
2 |2
0

75:3 = 25 r 0
25:3 = 8 r 1
8:3 = 2 r 2
2:3 = 0 r 2

Otrzymane reszty to miejsca gdzie znajdują się poszczególne odważniki...
0 - szalka tam gdzie jest odważnik o masie m
1 - nie użyty
2 - druga szalka

Dla naszego przykładu wychodzi:
0 - odważnik 3^0 - stan 0
1 - odważnik 3^1 - stan 1
2 - odważnik 3^2 - stan 2
2 - odważnik 3^3 - stan 2

Wynik:
Lewa szalka:
m(35), + 1=36

Prawa szalka:
9+27=36

To zadanie było na finale olimpiady informatycznej w podstawówce. Jedna osoba rozwiązała, a profesor, który prowadził, niesamowicie się ucieszył z rozwiązania i gratulował laureatowi.

@lewymati czy możesz wytłumaczyć to rozwiązanie?

Ciekawszy był chyba problem z serialu Columbo.
http://pl.wikipedia.org/wiki/Porucznik_Columbo

Tam były worki z monetami, jakaś tam liczba sztuk, np. 20, i było wiadomo że w jednym z nich są fałszywe monety, znaczy o innej wadze od prawdziwych.

I problem polegał na tym, że mamy znaleźć ten worek z fałszywymi, i tylko jednym ważeniem!

Potrafi ktoś to rozwiązać?

Ta druga waga, a worków z monetami jest więcej, np. 100.

tweety3d napisał(a):

@lewymati czy możesz wytłumaczyć to rozwiązanie?

A to dasz rady odczytać bez specjalnych tłumaczeń?

      cout<<N;
      for(unsigned W=1;N;W*=3,N=(N+(p>1))/3)
        {
         unsigned p=n%3;
         if(p==1) cout<<" -"<<W;
         else if(p) cout<<" +"<<W;
        }         
      cout<<endl;