[Logo] Mendo Judge Discussion Board - Forums
  [Search] Search   [Recent Topics] Recent Topics   [Hottest Topics] Hottest Topics   [Members]  Member Listing   [Groups] Back to home page 
bonboni  XML
Forum Index » Задачи од национални натпревари
Author Message
jovank



Joined: 01/01/2010 16:17:42
Messages: 127
Offline

Moze nekoj poubavo da mi go objasni resenieto na zadacata bonboni, bidjki mislam deka ic ne go svakam? fala odnapred
[MSN]
igorchete



Joined: 04/02/2010 22:04:03
Messages: 10
Offline

Alal im vera na tie sto stvarno ja resija zadacata, mene ni nakraj pamet takvo resenie ne bi mi padnalo na pamet, jas probav brute force, ali i toa bese komplicirano, pa ja ostaviv.
obi1kenobi



Joined: 18/02/2010 20:01:33
Messages: 168
Offline

Prvo n go zapisuvas kako broj so osnova 3:
_________
while(n>0)
{
a[i]=n%3;
n/=3;
i++;
}
_________

Sega za sekoe a[i] sto e 2, mozes da dodades uste edna kutija so 3^i bonboni i toa a[i] da stane 0, dodeka a[i+1] da se zgolemi za 1. Dodadenata kutija za zapisuvas vo add[i].

Ovaa postapka moze na nekoi mesta da napravi da se pojavat trojki vo nizata a, togas sekoja trojka kaj a[i] ja zamenuvas so 0, a a[i+1] go zgolemuvas za 1.
_________
for(i=0;i<14;i++)
{
if(a[i]==2)
{
a[i]=0;
a[i+1]++;
add[i]=1;
} else if(a[i]==3) {
a[i]=0;
a[i+1]++;
}
}
_________

Posle e samo prasanje na ispisuvanje na rezultatite. Gi vnesuvame vo vector<int> give, koj potoa go sortirame za da gi ispecatime vrednostite podredeni. Koristime vector za da ne mora racno da prebaruvame na koe mesto treba da go ispecatime n.
_________
tmp=1;
for(i=0;i<15;i++)
{
if(add[i]==1)
{
give.push_back(tmp);
}
tmp*=3;
}
give.push_back(n);
_________

Na slicen nacin gi pecatime vrednostite od a[i]. Zabelezi deka bidejki a[i] pretstavuva broj so osnova 3, mozeme direktno da gi ispecatime stepenite na 3, nema potreba da gi dodavame vo vector za da gi sortirame.

Ako uste nesto ne ti e jasno pisi =)

This message was edited 1 time. Last update was at 20/03/2010 19:25:46

jovank



Joined: 01/01/2010 16:17:42
Messages: 127
Offline

okey, svakam ova, ali samo me buni zosto e potrebno da go pretvorime n vo broj so osnova 3? sakam da prasam, od kaj sledi deka toj nacin raboti?
[MSN]
obi1kenobi



Joined: 18/02/2010 20:01:33
Messages: 168
Offline

Hahaha kako matematicar ne bi trebalo toa da go prasuvas Se zezam

Koga n ke go napravis vo osnova 3, ti vsusnost gledas od koi kutii moze da se napravi - bonbonite vo sekoja kutija se stepen na 3. So dodavanje na vistinskite stepeni na 3 samo po ednas (za od 2 kutii so ist broj bonboni da stane edna pogolema so 3 pati poveke bonboni) moze da go dovedeme n da moze da se zapise kako zbir na razlicni stepeni na 3 - zadacata vsusnost toa i go bara. Samo tie kutii sto bi trebalo da se javat po 2 pati vo n se problem, drugite golemini ili se javuvaat po ednas (zadacata go dozvoluva toa) ili voopsto gi nema.

Znaci idejata za resavanje ni se sveduva na dodavanje na razlicni stepeni na 3 so cel n da stane zbir na isto taka razlicni stepeni na 3. Ako pretpostavime deka nekoj stepen na 3 se javuva i vo grupata na dodadeni stepeni i vo grupata na dobieni stepeni - toa znaci deka vsusnost popusto sme go dodale i negovoto isfrlanje od dvete grupi gi pravi disjunktni a se uste ja zadrzuva ispolnetosta na site uslovi na zadacata. Spored toa resenieto raboti
nikola3103


[Avatar]

Joined: 25/12/2009 16:09:56
Messages: 184
Offline

A be ovaa potoci bila mn lesna, a i ja i jovce sme ja utnale. Inace uste ne sfakam zaso mi dava gresen rezultat. ama aj ke prasam nekoj
jovank



Joined: 01/01/2010 16:17:42
Messages: 127
Offline

hehe ja znam zasto sum ja utnal posle letna monitorot niz prozor i fala na objasnuvanjeto, sea konecno go svativ resenieto

This message was edited 1 time. Last update was at 21/03/2010 13:12:41

[MSN]
obi1kenobi



Joined: 18/02/2010 20:01:33
Messages: 168
Offline

Nema problem
 
Forum Index » Задачи од национални натпревари
Go to:   
Powered by JForum 2.1.8 © JForum Team