Dva zadatka s roka 2.7.2003.

[matomic]

Molim vas neka mi netko rijesi ova dva zadatka.
1.Koliko ima prirodnih brojeva manjih od 10^9 u cijem zapisu se pojavljuje niz znamenaka 123(na uzastopnim mjestima)?

2.Neki jezik koristi n slova.Niz slova je rijec tog jezika ako se izmedju dva jednaka slova u nizu ne nalaze dva jednaka slova.
(a) Koliko iznosi maksimalna duljina rijeci tog jezika?
(b)Odredite broj rijeci maksimalne duljine u tom jeziku.

To su dva zadatka s roka 2.07.2003.

Puno hvala

[kikach]

Evo...rijesih ti 1. zadatak...

Ovako...10^9 ...to je 10 znamenaka....kako se mora javiti 123 na uzastopnim mjestima, zakljucujemo da 1-znamenkastih i 2-znamenkastih takvih brojeva nema.
3-znamenkastih ima, i to je samo 123.

E, sad... 4-znamenkastih ima 10 + 9 (jer gledas 2 slucaja: kada je 123 na pocetku-prva 3 mjesta u 4-znam. broju..onda zadnji broj biras na 10 nacina, a ako 123 nije na pocetku, prvi se broj bira na 9 nacina - bez, jelte, nule)

Analogno, 5-znamenkastih ima 10^2 + 2*9*10 = 280

i tako se nastavi za 6-znamenkaste, 7-znamenkaste,...,9-znamenkaste brojeve pa na kraju dobijes po pravilu zbroja:

Suma(k ide od 1 do 6) od (10^k)+ k*9*10^(k-1)

1 + 19 + 280 + 3700 + 46000 + 550000 + 6400000 = 7000000 (ako nisam pogrijesila u racunu)

[grossi]

1. Zadatak. Rjesenje:

Koristi se FUI.
Brojim samo deveteroznamenkaste

Pojavljuje se 123:
na prvom mjestu: brojevi obika 123------.
njih ima 10 ^6
unuar broja a ne na prvom mistu. -123-----.
njih ima 9x6x10^5

Pojavljuje se 123 dva puta:
na prvom mjestu 123. brojevi oblika 123--123-.
njih ima 4x10^3
unutar broja a ne na prvom mjestu, -123-123-.
njih ima 9x10^2x3!

Pojavljuje se tri puta:
123123123
takvih je samo jedan

Rješenje:
10^6 + 9x6x10^5 - 4x10^3 - 9x10^2x3x2 +1

Nisam siguran, napamet sam brojio.

2. Zadatak
(a) Mislim da je rješenje 2n
(b)n!

Nisam siguran ni ovaj, cini mi se pre laganim.

Nadam se da sam barem nesto rijesio tocno.
Eto pa ako ti valja.

_________________
------------------------------------------
Toni Grossi

Nekretnine Nekretnine 24 sata
++++++++++++++++++++++

[grossi]

moj je prvi kriv, ja sam prebrojio samo deveteroznamenkaste, treba jos prebrojiti sve osmoznamenkaste, zedmoznam...., oprosti

_________________
------------------------------------------
Toni Grossi

Nekretnine Nekretnine 24 sata
++++++++++++++++++++++

[ahri]

i drugi ti je kriv :)
a) 3n
b) n!*2^(n-1)

offtopic: svaka cast Siki na raskikavanju ovog zadatka, i time sto je ucinio tjedan dana u skotskoj ljepsim ;).

edit: prosli put sam slucajno napisao krivo rjesenje :/
+ sad mi sika pise svoje rjesenje na icq, pa cu pejstat ovdje.

_________________

[ZELENIZUBNAPLANETIDOSADE]

[ahri]

pa neka ih broji dvaput. zanima te koliko ima brojeva koji imaju 123 uzastopce... ovaj ima nekoliko puta, pa sto sad? ;)

_________________

[kikach]

ne broji dvaput....bitno je da se barem jedan put pojavi 123...ja ih u svakom brojanju gledam kao jedan objekt...na ostalim mjestima moze doci bilo sto.

[ZELENIZUBNAPLANETIDOSADE]

[ahri]

imas pravo zubati ;)

_________________

[Sika]

a)
ako se neko slovo pojavljuje 4 puta onda se 2 jednaka slova nalaze izmedju 2 jednaka slova. dakle duljina najduze rijeci je manja ili jednaka 3*n.
npr. jedna rijec duljine upravo 3*n je
111222333...nnn

b)
uvedimo zahtjev da se i-to slovo mora pojavljivati prije (i+1)-og slova u rijeci,
dokazimo indukcijom po broju slova da takvih rijeci ima 2^(n-1),
te da su 2 zadnja slova nn

za n=1 jedina rijec je 111
pp za neki keN tvrdnja vrijedi
dokazimo da vrijedi za n=k+1
rijec iz pretpostavke je oblika
1...k...kk
gledamo gdje mozemo dodati 3 slova n
n NE SMIJE doci prije k: 1...n...k...kk
1...k...n...n...kk nije rijec
1...k...n...kkn nije rijec
vidimo da zadnja 4 slova moraju biti iz skupa {k, n}
isprobavanjem sve 4 mogucnosti vidimo da imamo samo 2 nacina da iz rijeci iz pretpostavke dobijemo novu rijec
knnn +
nknn +
nnkn -
nnnk -
tj.
1...k...kknnn
1...k...knknn
dakle broj rijeci sa n slova je 2^(k-1)*2=2^k=2^(n-1)

zbog zahtjeva za poretkom slova, 2^(n-1) moramo pomnoziti sa n!

rjesenje: n! * 2^(n-1)

ukratko: ako fiksiramo poredak slova, iz rijeci 111222...nnn mozemo dobiti sve ostale uzastopnim zamjenama mjesta slova na pozicijama 3m i 3m+1
11212233344455657577

[ahri]

well done :).


edit:
rjesenje prvog zadataka je 6990001.

_________________

[ahri]

daklem...
uzet cemo kikijino rjesenje, samo cemo jos oduzeti gdje smo pobrojali 123 dva puta...
npr.

123 _ _ RENDOM-1 RENDOM-2 RENDOM-3 _
i
RENDOM-1 RENDOM-2 RENDOM-3 _ _ 123 _

su isti brojevi (RENDOM-X znaci da je taj X bio jedna od 10 mogucnosti, a 123 su fixirani).


sa dvije 123ojke:

za 9znamenkaste se moze pojaviti ili na prvom mjestu, pa onda ostane 6 mjesta.
u tih 6 mjesta se opet pojavi 123, pa zapravo imamo 4 mjesta, od kojih je jedno garantirano (tj. skupina 123) :). dakle 10^3 * (4 povrh 1). (4 povrh 1) jer na toliko nacina mozemo odabrati gdje se nalazi 123.

a ako se ne nalazi na prvom mjestu, onda imamo 9 * nesto
a to nesto je:
imamo 8 ostalih mjesta, gdje su 2 puta 123... dakle, zapravo 4 mjesta, od kojih su 2 garantirana.

means 10^(4-2) * (4 povrh 2)

dakle, to je

10^3 * (4 // 1) + 9*10^2 * (4 // 2) = 9400
za osmeroznamenkaste to je:
10^2* (3 // 1) + 9*10^1 * (3//2) = 570
za sedmeroznamenkaste:
10^1* (2 // 1) + 9*10^0 * (2//2) = 29
za sesteroznamenkaste je to jedna mogucnost - 123123 = 1

u brojevima s manje znamenki se to ne moze dogoditi.

kad ovo sve sumiramo dobijemo 10000.

no, kod deveteroznamenkastih smo oduzeli duplo kombinaciju kada se 123 pojavlja 3 puta. hvala bogu, to je samo jedna situacija.
dakle, rjesnje je:

7000000 - 10000 + 1 = 6990001

_________________

[ZELENIZUBNAPLANETIDOSADE]

mislim da je b) jedan poprilicno rjesen zadatak

btw: zasto sam ja bio potpuno siguran da je pismeni iz kombinatorike sutra ujutro

_________________

Pupoljak nije negiran. Rekao sam to i ponovit cu to jos jedanput. Pupoljak NIJE negirAn.
MADD
(Mothers Against Dirty Dialectics)
Based on a true story. NOT.
Ko ih sljivi, mi sviramo punk

[ahri]

svi su lijepo i opsirno rjeseni :)

_________________

[ahri]

eh, da. ima netko ideju kako brzo sforpetljati ovaj prvi zadatak?

natipkah u C-u, radi mi 5 minuta... nista prepametno:

[ZELENIZUBNAPLANETIDOSADE]

array [9] znamenki '0'..'9' i trazenje podstringa preskacuci nizove bez 1,2 ili 3 u njima? tj. imati flag koji broji koliko ima znamenki 1,2 i 3 i kada je na 0 ne raditi provjeru postojanja podstringa?
..najkompliciraniji dio bi bio napisati proc dodaj1() za niz znakova?

_________________

Pupoljak nije negiran. Rekao sam to i ponovit cu to jos jedanput. Pupoljak NIJE negirAn.
MADD
(Mothers Against Dirty Dialectics)
Based on a true story. NOT.
Ko ih sljivi, mi sviramo punk

[ahri]

napravio sam to bez flagova, radi 2 minute. nisam bas siguran koliko ce to s flagovima pomoc, jer postavljanje flagova, njihovo ispitivanje, te mjenjanje dok se mijenja broj mi se ne cini znacajno brze od jednostavne provjere substringa.

_________________

[ZELENIZUBNAPLANETIDOSADE]

Uou duplo

Ne znam kako si to implementirao, iako pohvala na ekspeditivnosti , ali.. flagovi se svode na FLAG++ i FLAG-- u dodaj1() proceduri prilikom namjestanja vrijednosti u stringu (jedan if) a oslobadjas se 7^9-u for petlji provjera substringa i isto toliko dodaj1() iteracija jer ako si na zadnjoj znamenci dosao do 4 i FLAG==0 onda ne moras iterirati sve do 9 nego samo bacas prve tri znamenke u 321 i povecavas broj za red 1000?
uz rekurzivno preskakivanje bi jos vise dobio, al nisam siguran dokle zelis ici sa optimizacijom

_________________

Pupoljak nije negiran. Rekao sam to i ponovit cu to jos jedanput. Pupoljak NIJE negirAn.
MADD
(Mothers Against Dirty Dialectics)
Based on a true story. NOT.
Ko ih sljivi, mi sviramo punk

[ZELENIZUBNAPLANETIDOSADE]

ILI !
for po broju pojavnosti niza 123 (1,2 ili 3 puta), s time da postoji samo jedan 9-znam broj sa 3 pojavljanja 123.
Za brojeve sa 1nim 123 je jednostavno. fiksiras jedan takav 123 na i-tom mjestu i iteriras po ostalim znamenkama tako da ti se ne desi jos jedan 123.
Za brojeve sa 2 123 niza imas princip brojalice. Desni niz se pomice za 1 u lijevo kada lijevi niz dodje do njega i tada lijevi opet na pocetak lijeve strane niza i dalje i onda sa tim fiksiranim parom 123-ojki iteriras po ostalim znamenkama izbjegavajuci 123123123.
Ovaj drugi korak SIGURNO moze i pametnije jer za svaki par fiksiranih 123 imamo 10^3 odgovarajucih brojeva koji u sebi sadrze 123 i 123 na tim mjestima. Jedini izuzeti slucaj jest desni 123 na desnom kraju a lijevi na njega slijepljen ili na lijevom kraju. To je 2000 brojeva.
Prvi korak nije tako lijep, al i sa njim bi se vjerujem moglo nesto napraviti. Npr. Ako ti je 123 uz lijevi ili desni kraj onda znas da ti se na dva mjesta lijevo, tj. desno ne moze naci jos jedan 123

isto tako, ne moras gledati znak po znak nego ti je dovoljno da na +3 skokovima naletis na 1, 2, ili 3 da provjeris prethodno i iduce slovo, tj. prethodna/iduca dva i nadjes niz

ovo je bilo zabavno

_________________

Pupoljak nije negiran. Rekao sam to i ponovit cu to jos jedanput. Pupoljak NIJE negirAn.
MADD
(Mothers Against Dirty Dialectics)
Based on a true story. NOT.
Ko ih sljivi, mi sviramo punk