Srednjoškolski zadaci

WebWolf · 17.02.2010

marko_n je napisao(la):
Moje je average vrednost velikog broja slučajeva.

A 17670 je šta?

Vise nista. To je navodno cena koju bi iskostala kapetana po onom mom algoritmu da kako dodju do bandere nasumicno izaberu kuda ce. Ali problem je upravo u tom random. U zavisnosti kako ga napravis, menja se iznos... Znaci, nema veze sa zivotom. Ocigledno je resenje komplikovanije od toga

.

Bahati [SiD] · 18.02.2010

graf algo:
updanje u luku 2,14%
u kafanu 3,48%
spavanje 94,39%

algo je sledeci:
napravi se binarno drvo (ili nesto nalik drvetu) gde je koren 7. leva i desna grana u sledecem nivou su 6 i 8. i tako redom, s tim sto 0 (luka) i 10 (kafana) nemaju grane (listovi su). treci nivo bi bio 5 7 7 9...
drvo ima visinu 10, tj. broj udaraca u banderu.

broj nacina upadanja u luku je broj nula u drvetu.
broj nacina ulazaka u kafanu je broj desetki u drvetu, sem u poslednjem nivou kada se racuna kao spavanje.
broj nodova u poslednjem nivou, minus oni koji su nule je broj spavanja.

drvo je u sustini samo razvijeni iliti usmereni oblik prethodno opisanog grafa.

ovo poslednje mi deluje najklimavije, a logika je da bi mornar morao da zaobidje sve nule i desetke u prethodnim nivoima da bi stigao do poslednjeg. mozda ne treba da racunam duplikate... videcu...

jel ima neko da se (ne)slaze sa algom? osim toga sto izglada da ne radi kako treba?

ps. mislim da je sporedno da li mornari izlaze 1 po 1, jer nigde ne pise da bandera moze biti "zauzeta". sporedno je i kol'ko ih ima, sustina je u verovatnocama za jednog mornara, ostalo je samo mnozenje...

yooyo · 18.02.2010

Tacnog odgovora se ni ja ne secam.

Ja sam taj zadatak resio simulacijom..

Kod:

#include <stdlib.h>
#include <time.h>


int sim(int &t, int& z, int& u)
{
	int sum = 0;
	int br_treznih = 0;
	int br_zaspalih = 0;
	int br_uhapsenih = 0;
	// dvesta mornara
	for (int m = 0; m < 200; m++)
	{
		int b = 7; // pocinje od 7. bandere
		int p = 0; // broj udaraca
		while (1)
		{
			// ako je 10x udario u banderu.. zaspace
			if (p==10)
			{
				br_zaspalih++;
				sum += 30;
				break;
			}
			// udarac u banderu.. gde dalje napred ili nazad
			b += (rand()&1)? -1 : 1;

			// upada u vodu, trezni se i ide da spava
			if (b == 0) 
			{
				br_treznih++;
				break;
			}

			// stigao do kafane i ide da se napije
			if (b == 10)
			{
				br_uhapsenih ++;
				sum += 200;
				break;
			}
			p++;
		}
	}

	//printf("\n%d (T:%d, Z:%d, U:%d)", sum, br_treznih, br_zaspalih, br_uhapsenih);
	t = br_treznih;
	u = br_uhapsenih;
	z = br_zaspalih;
	return sum;
}

#define NITER 1000000

int _tmain(int argc, _TCHAR* argv[])
{
	srand((unsigned)time(0)); 
	int br_treznih = 0;
	int br_zaspalih = 0;
	int br_uhapsenih = 0;

	double tsum = 0;
	for (int i=0; i<NITER; i++)
	{
		int t,z,u;
		tsum += sim(t, z, u);
		br_treznih += t;
		br_uhapsenih += u;
		br_zaspalih += z;
	}
	double avg = (double)tsum/(double)NITER;
	double at = (double)br_treznih/(double)NITER;
	double az = (double)br_zaspalih/(double)NITER;
	double au = (double)br_uhapsenih/(double)NITER;

	printf("\navg = %f.\nTrezno = %6.2f%%\nZaspalo = %6.2f%%\nUhapseno = %6.2f%%", avg, 100.0*at/200.0, 100.0*az/200.0f, 100.0*au/200.0f);
}

avg = $17609.83
Trezno = 2.02%
Zaspalo = 63.48%
Uhapseno = 34.50%

Hint: Ako smanjite broj iteracija (NITER), razultati se razlikuju izmedju dva testa.

Trebalo bi da ima veze sa poznatim random-walk problemom.

Bahati [SiD] · 18.02.2010

moja simulacija je (skoro) identicna, samo mislim da kod p == 10 treba da brojis u trezne ako je b == 0. to znaci da je u 10. koraku upao u vodu -> nije zaspao nego se se otreznio.

i nisam siguran da p krece od 0, posto je vec udario u jednu banderu...

al svakako mislim da je (malo) gay da se resi simulacijom, kada postoji egzaktan odgovor.

u tom smislu cak vise verujem graf resenju, samo ne mogu da provalim koje je pogresno i zasto.

graf:
luka 2,14 %
kafana 3,48 %
spavanje 94,39 %

simulacija:
luka 2,15 %
kafana 34,40 %
spavanje 63,46 %

C++/CLI:

Kod:

using namespace System;

void simulacija(int iteracija){
	Random^ r = gcnew Random();
	int bandera, cnt, spavanje = 0, kafana = 0, luka = 0;

	for(int i=0; i<iteracija; i++) {
		bandera = 7;
		cnt = 1;
		while(true) {
			if(cnt == 10)
			{
				if(bandera != 0) spavanje++;
				else luka++;
				break;
			}
			else
			{
				if(r->NextDouble()>0.5F) bandera++;
				else bandera--;

				if(bandera == 10)
				{
					kafana++;
					break;
				}
				if(bandera == 0)
				{
					luka++;
					break;
				}
			}
			cnt++;
		}
		if(i%(iteracija/1000) == 0)
		{
			Console::CursorLeft = 0;
			Console::Write("sim {0:P1} ",(double)i/(double)iteracija);
			if(Console::KeyAvailable)
			{
				Console::ReadKey(true);
				break;
			}
		}
		if(i%(iteracija/100) == 0)
		{
			Console::WriteLine(Environment::NewLine + "luka {0:P2}     ",(double)luka/(double)(luka+kafana+spavanje));
			Console::WriteLine("kafana {0:P2}     ",(double)kafana/(double)(luka+kafana+spavanje));
			Console::WriteLine("spavanje {0:P2}     ",(double)spavanje/(double)(luka+kafana+spavanje));
			Console::CursorTop -= 4;
		}
	}
	Console::Beep(1500,1000);
}

void graf(void) {
	//pravljenje drveta
	array<Collections::Generic::List<int>^>^ outcomes = gcnew array<Collections::Generic::List<int>^>(10);

	for (int i=0; i<outcomes->Length; i++) {
		outcomes[i] = gcnew Collections::Generic::List<int>;
	}

	//popunjavanje drveta
	outcomes[0]->Add(7);
	for (int i=0; i<outcomes->Length-1; i++) {
		for each (int k in outcomes[i]) {
			if(k>0 && k<10)
			{
				outcomes[i+1]->Add(k-1);
				outcomes[i+1]->Add(k+1);
			}
		}
	}

	//citanje drveta (sve sem poslednjeg nivoa)
	int luka = 0, lukatmp = 0, kafana = 0, spavanje = 0;
	for (int i=0; i<outcomes->Length-1; i++) {
		Console::WriteLine("Korak {0}",i+1);
		for each (int k in outcomes[i]) {
			if(k == 0) luka++;
			if(k == 10) kafana++;
			Console::Write("{0} ",k);
		}
		Console::WriteLine(Environment::NewLine);
	}

	//poslednji nivo
	Console::WriteLine("Korak {0}",outcomes->Length);
	for each (int k in outcomes[outcomes->Length-1]) {
		if(k == 0) lukatmp++;
		Console::Write("{0} ",k);
	}
	Console::WriteLine(Environment::NewLine);

	spavanje += outcomes[outcomes->Length-1]->Count - lukatmp;
	luka += lukatmp;

	Console::WriteLine("luka {0:P2}      ",(double)luka/(double)(luka+kafana+spavanje));
	Console::WriteLine("kafana {0:P2}    ",(double)kafana/(double)(luka+kafana+spavanje));
	Console::WriteLine("spavanje {0:P2}  ",(double)spavanje/(double)(luka+kafana+spavanje));
	Console::WriteLine(Environment::NewLine);
}

int main(array<System::String ^> ^args)
{
	graf();
	simulacija(int::MaxValue/1000);

	Console::Read();
	return 0;
}

yooyo · 18.02.2010

Pogledacu ponovo.. sada sam malo premoren da proveravam da li sam dobro odrolao petlju.

Bahati [SiD] · 18.02.2010

glup sam bio! :wall:

lepo sam izbrojao skup dogadjaja i sve, ali nisam uzeo u obzir da su jedni verovatniji od drugih!

verovatnoca da ce se neka putanja desiti je: 0,5^k-1; gde je k broj koraka u putanji od sedme bandere.

evo egzaktnih rezultata:

verovatnoca da upadne u vodu: 2,14843750 %
verovatnoca da udje u kafanu: 28,90625000 %
verovatnoca da udari 10 puta u banderu: 68,94531250 %
ukupno 100,00000000 %
tuca za 200 mornara 11562,50$
spavanje na ulici za 200 mornara 4136,72$
ukupno 15699,22$

dakle onaj prethodni algo radi, samo ga treba sitno modifikovati da ne broji slucajeve, nego da sabira verovatnoce pojedinacnih slucajeva.

vidi se i da je simulacija ok, ali daleko od precizne. da ne pricamo sto je ovaj nacin gotovo trenutan.

u spojleru su sve moguce putanje sa ishodom, brojem koraka i verovatnocom.

Kafana(4)(12,50 %): 7 8 9 10
Kafana(6)(3,13 %): 7 6 7 8 9 10
Kafana(6)(3,13 %): 7 8 7 8 9 10
Kafana(6)(3,13 %): 7 8 9 8 9 10
Kafana(8)(0,78 %): 7 6 5 6 7 8 9 10
Kafana(8)(0,78 %): 7 6 7 6 7 8 9 10
Kafana(8)(0,78 %): 7 6 7 8 7 8 9 10
Kafana(8)(0,78 %): 7 6 7 8 9 8 9 10
Kafana(8)(0,78 %): 7 8 7 6 7 8 9 10
Kafana(8)(0,78 %): 7 8 7 8 7 8 9 10
Kafana(8)(0,78 %): 7 8 7 8 9 8 9 10
Kafana(8)(0,78 %): 7 8 9 8 7 8 9 10
Kafana(8)(0,78 %): 7 8 9 8 9 8 9 10
Luka(10)(0,20 %): 7 6 5 4 3 2 1 2 1 0
Luka(10)(0,20 %): 7 6 5 4 3 2 3 2 1 0
Luka(10)(0,20 %): 7 6 5 4 3 4 3 2 1 0
Luka(10)(0,20 %): 7 6 5 4 5 4 3 2 1 0
Luka(10)(0,20 %): 7 6 5 6 5 4 3 2 1 0
Luka(10)(0,20 %): 7 6 7 6 5 4 3 2 1 0
Luka(10)(0,20 %): 7 8 7 6 5 4 3 2 1 0
Luka(8)(0,78 %): 7 6 5 4 3 2 1 0
Spavanje(10)(0,20 %): 7 6 5 4 3 2 1 2 1 2
Spavanje(10)(0,20 %): 7 6 5 4 3 2 1 2 3 2
Spavanje(10)(0,20 %): 7 6 5 4 3 2 1 2 3 4
Spavanje(10)(0,20 %): 7 6 5 4 3 2 3 2 1 2
Spavanje(10)(0,20 %): 7 6 5 4 3 2 3 2 3 2
Spavanje(10)(0,20 %): 7 6 5 4 3 2 3 2 3 4
Spavanje(10)(0,20 %): 7 6 5 4 3 2 3 4 3 2
Spavanje(10)(0,20 %): 7 6 5 4 3 2 3 4 3 4
Spavanje(10)(0,20 %): 7 6 5 4 3 2 3 4 5 4
Spavanje(10)(0,20 %): 7 6 5 4 3 2 3 4 5 6
Spavanje(10)(0,20 %): 7 6 5 4 3 4 3 2 1 2
Spavanje(10)(0,20 %): 7 6 5 4 3 4 3 2 3 2
Spavanje(10)(0,20 %): 7 6 5 4 3 4 3 2 3 4
Spavanje(10)(0,20 %): 7 6 5 4 3 4 3 4 3 2
Spavanje(10)(0,20 %): 7 6 5 4 3 4 3 4 3 4
Spavanje(10)(0,20 %): 7 6 5 4 3 4 3 4 5 4
Spavanje(10)(0,20 %): 7 6 5 4 3 4 3 4 5 6
Spavanje(10)(0,20 %): 7 6 5 4 3 4 5 4 3 2
Spavanje(10)(0,20 %): 7 6 5 4 3 4 5 4 3 4
Spavanje(10)(0,20 %): 7 6 5 4 3 4 5 4 5 4
Spavanje(10)(0,20 %): 7 6 5 4 3 4 5 4 5 6
Spavanje(10)(0,20 %): 7 6 5 4 3 4 5 6 5 4
Spavanje(10)(0,20 %): 7 6 5 4 3 4 5 6 5 6
Spavanje(10)(0,20 %): 7 6 5 4 3 4 5 6 7 6
Spavanje(10)(0,20 %): 7 6 5 4 3 4 5 6 7 8
Spavanje(10)(0,20 %): 7 6 5 4 5 4 3 2 1 2
Spavanje(10)(0,20 %): 7 6 5 4 5 4 3 2 3 2
Spavanje(10)(0,20 %): 7 6 5 4 5 4 3 2 3 4
Spavanje(10)(0,20 %): 7 6 5 4 5 4 3 4 3 2
Spavanje(10)(0,20 %): 7 6 5 4 5 4 3 4 3 4
Spavanje(10)(0,20 %): 7 6 5 4 5 4 3 4 5 4
Spavanje(10)(0,20 %): 7 6 5 4 5 4 3 4 5 6
Spavanje(10)(0,20 %): 7 6 5 4 5 4 5 4 3 2
Spavanje(10)(0,20 %): 7 6 5 4 5 4 5 4 3 4
Spavanje(10)(0,20 %): 7 6 5 4 5 4 5 4 5 4
Spavanje(10)(0,20 %): 7 6 5 4 5 4 5 4 5 6
Spavanje(10)(0,20 %): 7 6 5 4 5 4 5 6 5 4
Spavanje(10)(0,20 %): 7 6 5 4 5 4 5 6 5 6
Spavanje(10)(0,20 %): 7 6 5 4 5 4 5 6 7 6
Spavanje(10)(0,20 %): 7 6 5 4 5 4 5 6 7 8
Spavanje(10)(0,20 %): 7 6 5 4 5 6 5 4 3 2
Spavanje(10)(0,20 %): 7 6 5 4 5 6 5 4 3 4
Spavanje(10)(0,20 %): 7 6 5 4 5 6 5 4 5 4
Spavanje(10)(0,20 %): 7 6 5 4 5 6 5 4 5 6
Spavanje(10)(0,20 %): 7 6 5 4 5 6 5 6 5 4
Spavanje(10)(0,20 %): 7 6 5 4 5 6 5 6 5 6
Spavanje(10)(0,20 %): 7 6 5 4 5 6 5 6 7 6
Spavanje(10)(0,20 %): 7 6 5 4 5 6 5 6 7 8
Spavanje(10)(0,20 %): 7 6 5 4 5 6 7 6 5 4
Spavanje(10)(0,20 %): 7 6 5 4 5 6 7 6 5 6
Spavanje(10)(0,20 %): 7 6 5 4 5 6 7 6 7 6
Spavanje(10)(0,20 %): 7 6 5 4 5 6 7 6 7 8
Spavanje(10)(0,20 %): 7 6 5 4 5 6 7 8 7 6
Spavanje(10)(0,20 %): 7 6 5 4 5 6 7 8 7 8
Spavanje(10)(0,20 %): 7 6 5 4 5 6 7 8 9 10
Spavanje(10)(0,20 %): 7 6 5 4 5 6 7 8 9 8
Spavanje(10)(0,20 %): 7 6 5 6 5 4 3 2 1 2
Spavanje(10)(0,20 %): 7 6 5 6 5 4 3 2 3 2
Spavanje(10)(0,20 %): 7 6 5 6 5 4 3 2 3 4
Spavanje(10)(0,20 %): 7 6 5 6 5 4 3 4 3 2
Spavanje(10)(0,20 %): 7 6 5 6 5 4 3 4 3 4
Spavanje(10)(0,20 %): 7 6 5 6 5 4 3 4 5 4
Spavanje(10)(0,20 %): 7 6 5 6 5 4 3 4 5 6
Spavanje(10)(0,20 %): 7 6 5 6 5 4 5 4 3 2
Spavanje(10)(0,20 %): 7 6 5 6 5 4 5 4 3 4
Spavanje(10)(0,20 %): 7 6 5 6 5 4 5 4 5 4
Spavanje(10)(0,20 %): 7 6 5 6 5 4 5 4 5 6
Spavanje(10)(0,20 %): 7 6 5 6 5 4 5 6 5 4
Spavanje(10)(0,20 %): 7 6 5 6 5 4 5 6 5 6
Spavanje(10)(0,20 %): 7 6 5 6 5 4 5 6 7 6
Spavanje(10)(0,20 %): 7 6 5 6 5 4 5 6 7 8
Spavanje(10)(0,20 %): 7 6 5 6 5 6 5 4 3 2
Spavanje(10)(0,20 %): 7 6 5 6 5 6 5 4 3 4
Spavanje(10)(0,20 %): 7 6 5 6 5 6 5 4 5 4
Spavanje(10)(0,20 %): 7 6 5 6 5 6 5 4 5 6
Spavanje(10)(0,20 %): 7 6 5 6 5 6 5 6 5 4
Spavanje(10)(0,20 %): 7 6 5 6 5 6 5 6 5 6
Spavanje(10)(0,20 %): 7 6 5 6 5 6 5 6 7 6
Spavanje(10)(0,20 %): 7 6 5 6 5 6 5 6 7 8
Spavanje(10)(0,20 %): 7 6 5 6 5 6 7 6 5 4
Spavanje(10)(0,20 %): 7 6 5 6 5 6 7 6 5 6
Spavanje(10)(0,20 %): 7 6 5 6 5 6 7 6 7 6
Spavanje(10)(0,20 %): 7 6 5 6 5 6 7 6 7 8
Spavanje(10)(0,20 %): 7 6 5 6 5 6 7 8 7 6
Spavanje(10)(0,20 %): 7 6 5 6 5 6 7 8 7 8
Spavanje(10)(0,20 %): 7 6 5 6 5 6 7 8 9 10
Spavanje(10)(0,20 %): 7 6 5 6 5 6 7 8 9 8
Spavanje(10)(0,20 %): 7 6 5 6 7 6 5 4 3 2
Spavanje(10)(0,20 %): 7 6 5 6 7 6 5 4 3 4
Spavanje(10)(0,20 %): 7 6 5 6 7 6 5 4 5 4
Spavanje(10)(0,20 %): 7 6 5 6 7 6 5 4 5 6
Spavanje(10)(0,20 %): 7 6 5 6 7 6 5 6 5 4
Spavanje(10)(0,20 %): 7 6 5 6 7 6 5 6 5 6
Spavanje(10)(0,20 %): 7 6 5 6 7 6 5 6 7 6
Spavanje(10)(0,20 %): 7 6 5 6 7 6 5 6 7 8
Spavanje(10)(0,20 %): 7 6 5 6 7 6 7 6 5 4
Spavanje(10)(0,20 %): 7 6 5 6 7 6 7 6 5 6
Spavanje(10)(0,20 %): 7 6 5 6 7 6 7 6 7 6
Spavanje(10)(0,20 %): 7 6 5 6 7 6 7 6 7 8
Spavanje(10)(0,20 %): 7 6 5 6 7 6 7 8 7 6
Spavanje(10)(0,20 %): 7 6 5 6 7 6 7 8 7 8
Spavanje(10)(0,20 %): 7 6 5 6 7 6 7 8 9 10
Spavanje(10)(0,20 %): 7 6 5 6 7 6 7 8 9 8
Spavanje(10)(0,20 %): 7 6 5 6 7 8 7 6 5 4
Spavanje(10)(0,20 %): 7 6 5 6 7 8 7 6 5 6
Spavanje(10)(0,20 %): 7 6 5 6 7 8 7 6 7 6
Spavanje(10)(0,20 %): 7 6 5 6 7 8 7 6 7 8
Spavanje(10)(0,20 %): 7 6 5 6 7 8 7 8 7 6
Spavanje(10)(0,20 %): 7 6 5 6 7 8 7 8 7 8
Spavanje(10)(0,20 %): 7 6 5 6 7 8 7 8 9 10
Spavanje(10)(0,20 %): 7 6 5 6 7 8 7 8 9 8
Spavanje(10)(0,20 %): 7 6 5 6 7 8 9 8 7 6
Spavanje(10)(0,20 %): 7 6 5 6 7 8 9 8 7 8
Spavanje(10)(0,20 %): 7 6 5 6 7 8 9 8 9 10
Spavanje(10)(0,20 %): 7 6 5 6 7 8 9 8 9 8
Spavanje(10)(0,20 %): 7 6 7 6 5 4 3 2 1 2
Spavanje(10)(0,20 %): 7 6 7 6 5 4 3 2 3 2
Spavanje(10)(0,20 %): 7 6 7 6 5 4 3 2 3 4
Spavanje(10)(0,20 %): 7 6 7 6 5 4 3 4 3 2
Spavanje(10)(0,20 %): 7 6 7 6 5 4 3 4 3 4
Spavanje(10)(0,20 %): 7 6 7 6 5 4 3 4 5 4
Spavanje(10)(0,20 %): 7 6 7 6 5 4 3 4 5 6
Spavanje(10)(0,20 %): 7 6 7 6 5 4 5 4 3 2
Spavanje(10)(0,20 %): 7 6 7 6 5 4 5 4 3 4
Spavanje(10)(0,20 %): 7 6 7 6 5 4 5 4 5 4
Spavanje(10)(0,20 %): 7 6 7 6 5 4 5 4 5 6
Spavanje(10)(0,20 %): 7 6 7 6 5 4 5 6 5 4
Spavanje(10)(0,20 %): 7 6 7 6 5 4 5 6 5 6
Spavanje(10)(0,20 %): 7 6 7 6 5 4 5 6 7 6
Spavanje(10)(0,20 %): 7 6 7 6 5 4 5 6 7 8
Spavanje(10)(0,20 %): 7 6 7 6 5 6 5 4 3 2
Spavanje(10)(0,20 %): 7 6 7 6 5 6 5 4 3 4
Spavanje(10)(0,20 %): 7 6 7 6 5 6 5 4 5 4
Spavanje(10)(0,20 %): 7 6 7 6 5 6 5 4 5 6
Spavanje(10)(0,20 %): 7 6 7 6 5 6 5 6 5 4
Spavanje(10)(0,20 %): 7 6 7 6 5 6 5 6 5 6
Spavanje(10)(0,20 %): 7 6 7 6 5 6 5 6 7 6
Spavanje(10)(0,20 %): 7 6 7 6 5 6 5 6 7 8
Spavanje(10)(0,20 %): 7 6 7 6 5 6 7 6 5 4
Spavanje(10)(0,20 %): 7 6 7 6 5 6 7 6 5 6
Spavanje(10)(0,20 %): 7 6 7 6 5 6 7 6 7 6
Spavanje(10)(0,20 %): 7 6 7 6 5 6 7 6 7 8
Spavanje(10)(0,20 %): 7 6 7 6 5 6 7 8 7 6
Spavanje(10)(0,20 %): 7 6 7 6 5 6 7 8 7 8
Spavanje(10)(0,20 %): 7 6 7 6 5 6 7 8 9 10
Spavanje(10)(0,20 %): 7 6 7 6 5 6 7 8 9 8
Spavanje(10)(0,20 %): 7 6 7 6 7 6 5 4 3 2
Spavanje(10)(0,20 %): 7 6 7 6 7 6 5 4 3 4
Spavanje(10)(0,20 %): 7 6 7 6 7 6 5 4 5 4
Spavanje(10)(0,20 %): 7 6 7 6 7 6 5 4 5 6
Spavanje(10)(0,20 %): 7 6 7 6 7 6 5 6 5 4
Spavanje(10)(0,20 %): 7 6 7 6 7 6 5 6 5 6
Spavanje(10)(0,20 %): 7 6 7 6 7 6 5 6 7 6
Spavanje(10)(0,20 %): 7 6 7 6 7 6 5 6 7 8
Spavanje(10)(0,20 %): 7 6 7 6 7 6 7 6 5 4
Spavanje(10)(0,20 %): 7 6 7 6 7 6 7 6 5 6
Spavanje(10)(0,20 %): 7 6 7 6 7 6 7 6 7 6
Spavanje(10)(0,20 %): 7 6 7 6 7 6 7 6 7 8
Spavanje(10)(0,20 %): 7 6 7 6 7 6 7 8 7 6
Spavanje(10)(0,20 %): 7 6 7 6 7 6 7 8 7 8
Spavanje(10)(0,20 %): 7 6 7 6 7 6 7 8 9 10
Spavanje(10)(0,20 %): 7 6 7 6 7 6 7 8 9 8
Spavanje(10)(0,20 %): 7 6 7 6 7 8 7 6 5 4
Spavanje(10)(0,20 %): 7 6 7 6 7 8 7 6 5 6
Spavanje(10)(0,20 %): 7 6 7 6 7 8 7 6 7 6
Spavanje(10)(0,20 %): 7 6 7 6 7 8 7 6 7 8
Spavanje(10)(0,20 %): 7 6 7 6 7 8 7 8 7 6
Spavanje(10)(0,20 %): 7 6 7 6 7 8 7 8 7 8
Spavanje(10)(0,20 %): 7 6 7 6 7 8 7 8 9 10
Spavanje(10)(0,20 %): 7 6 7 6 7 8 7 8 9 8
Spavanje(10)(0,20 %): 7 6 7 6 7 8 9 8 7 6
Spavanje(10)(0,20 %): 7 6 7 6 7 8 9 8 7 8
Spavanje(10)(0,20 %): 7 6 7 6 7 8 9 8 9 10
Spavanje(10)(0,20 %): 7 6 7 6 7 8 9 8 9 8
Spavanje(10)(0,20 %): 7 6 7 8 7 6 5 4 3 2
Spavanje(10)(0,20 %): 7 6 7 8 7 6 5 4 3 4
Spavanje(10)(0,20 %): 7 6 7 8 7 6 5 4 5 4
Spavanje(10)(0,20 %): 7 6 7 8 7 6 5 4 5 6
Spavanje(10)(0,20 %): 7 6 7 8 7 6 5 6 5 4
Spavanje(10)(0,20 %): 7 6 7 8 7 6 5 6 5 6
Spavanje(10)(0,20 %): 7 6 7 8 7 6 5 6 7 6
Spavanje(10)(0,20 %): 7 6 7 8 7 6 5 6 7 8
Spavanje(10)(0,20 %): 7 6 7 8 7 6 7 6 5 4
Spavanje(10)(0,20 %): 7 6 7 8 7 6 7 6 5 6
Spavanje(10)(0,20 %): 7 6 7 8 7 6 7 6 7 6
Spavanje(10)(0,20 %): 7 6 7 8 7 6 7 6 7 8
Spavanje(10)(0,20 %): 7 6 7 8 7 6 7 8 7 6
Spavanje(10)(0,20 %): 7 6 7 8 7 6 7 8 7 8
Spavanje(10)(0,20 %): 7 6 7 8 7 6 7 8 9 10
Spavanje(10)(0,20 %): 7 6 7 8 7 6 7 8 9 8
Spavanje(10)(0,20 %): 7 6 7 8 7 8 7 6 5 4
Spavanje(10)(0,20 %): 7 6 7 8 7 8 7 6 5 6
Spavanje(10)(0,20 %): 7 6 7 8 7 8 7 6 7 6
Spavanje(10)(0,20 %): 7 6 7 8 7 8 7 6 7 8
Spavanje(10)(0,20 %): 7 6 7 8 7 8 7 8 7 6
Spavanje(10)(0,20 %): 7 6 7 8 7 8 7 8 7 8
Spavanje(10)(0,20 %): 7 6 7 8 7 8 7 8 9 10
Spavanje(10)(0,20 %): 7 6 7 8 7 8 7 8 9 8
Spavanje(10)(0,20 %): 7 6 7 8 7 8 9 8 7 6
Spavanje(10)(0,20 %): 7 6 7 8 7 8 9 8 7 8
Spavanje(10)(0,20 %): 7 6 7 8 7 8 9 8 9 10
Spavanje(10)(0,20 %): 7 6 7 8 7 8 9 8 9 8
Spavanje(10)(0,20 %): 7 6 7 8 9 8 7 6 5 4
Spavanje(10)(0,20 %): 7 6 7 8 9 8 7 6 5 6
Spavanje(10)(0,20 %): 7 6 7 8 9 8 7 6 7 6
Spavanje(10)(0,20 %): 7 6 7 8 9 8 7 6 7 8
Spavanje(10)(0,20 %): 7 6 7 8 9 8 7 8 7 6
Spavanje(10)(0,20 %): 7 6 7 8 9 8 7 8 7 8
Spavanje(10)(0,20 %): 7 6 7 8 9 8 7 8 9 10
Spavanje(10)(0,20 %): 7 6 7 8 9 8 7 8 9 8
Spavanje(10)(0,20 %): 7 6 7 8 9 8 9 8 7 6
Spavanje(10)(0,20 %): 7 6 7 8 9 8 9 8 7 8
Spavanje(10)(0,20 %): 7 6 7 8 9 8 9 8 9 10
Spavanje(10)(0,20 %): 7 6 7 8 9 8 9 8 9 8
Spavanje(10)(0,20 %): 7 8 7 6 5 4 3 2 1 2
Spavanje(10)(0,20 %): 7 8 7 6 5 4 3 2 3 2
Spavanje(10)(0,20 %): 7 8 7 6 5 4 3 2 3 4
Spavanje(10)(0,20 %): 7 8 7 6 5 4 3 4 3 2
Spavanje(10)(0,20 %): 7 8 7 6 5 4 3 4 3 4
Spavanje(10)(0,20 %): 7 8 7 6 5 4 3 4 5 4
Spavanje(10)(0,20 %): 7 8 7 6 5 4 3 4 5 6
Spavanje(10)(0,20 %): 7 8 7 6 5 4 5 4 3 2
Spavanje(10)(0,20 %): 7 8 7 6 5 4 5 4 3 4
Spavanje(10)(0,20 %): 7 8 7 6 5 4 5 4 5 4
Spavanje(10)(0,20 %): 7 8 7 6 5 4 5 4 5 6
Spavanje(10)(0,20 %): 7 8 7 6 5 4 5 6 5 4
Spavanje(10)(0,20 %): 7 8 7 6 5 4 5 6 5 6
Spavanje(10)(0,20 %): 7 8 7 6 5 4 5 6 7 6
Spavanje(10)(0,20 %): 7 8 7 6 5 4 5 6 7 8
Spavanje(10)(0,20 %): 7 8 7 6 5 6 5 4 3 2
Spavanje(10)(0,20 %): 7 8 7 6 5 6 5 4 3 4
Spavanje(10)(0,20 %): 7 8 7 6 5 6 5 4 5 4
Spavanje(10)(0,20 %): 7 8 7 6 5 6 5 4 5 6
Spavanje(10)(0,20 %): 7 8 7 6 5 6 5 6 5 4
Spavanje(10)(0,20 %): 7 8 7 6 5 6 5 6 5 6
Spavanje(10)(0,20 %): 7 8 7 6 5 6 5 6 7 6
Spavanje(10)(0,20 %): 7 8 7 6 5 6 5 6 7 8
Spavanje(10)(0,20 %): 7 8 7 6 5 6 7 6 5 4
Spavanje(10)(0,20 %): 7 8 7 6 5 6 7 6 5 6
Spavanje(10)(0,20 %): 7 8 7 6 5 6 7 6 7 6
Spavanje(10)(0,20 %): 7 8 7 6 5 6 7 6 7 8
Spavanje(10)(0,20 %): 7 8 7 6 5 6 7 8 7 6
Spavanje(10)(0,20 %): 7 8 7 6 5 6 7 8 7 8
Spavanje(10)(0,20 %): 7 8 7 6 5 6 7 8 9 10
Spavanje(10)(0,20 %): 7 8 7 6 5 6 7 8 9 8
Spavanje(10)(0,20 %): 7 8 7 6 7 6 5 4 3 2
Spavanje(10)(0,20 %): 7 8 7 6 7 6 5 4 3 4
Spavanje(10)(0,20 %): 7 8 7 6 7 6 5 4 5 4
Spavanje(10)(0,20 %): 7 8 7 6 7 6 5 4 5 6
Spavanje(10)(0,20 %): 7 8 7 6 7 6 5 6 5 4
Spavanje(10)(0,20 %): 7 8 7 6 7 6 5 6 5 6
Spavanje(10)(0,20 %): 7 8 7 6 7 6 5 6 7 6
Spavanje(10)(0,20 %): 7 8 7 6 7 6 5 6 7 8
Spavanje(10)(0,20 %): 7 8 7 6 7 6 7 6 5 4
Spavanje(10)(0,20 %): 7 8 7 6 7 6 7 6 5 6
Spavanje(10)(0,20 %): 7 8 7 6 7 6 7 6 7 6
Spavanje(10)(0,20 %): 7 8 7 6 7 6 7 6 7 8
Spavanje(10)(0,20 %): 7 8 7 6 7 6 7 8 7 6
Spavanje(10)(0,20 %): 7 8 7 6 7 6 7 8 7 8
Spavanje(10)(0,20 %): 7 8 7 6 7 6 7 8 9 10
Spavanje(10)(0,20 %): 7 8 7 6 7 6 7 8 9 8
Spavanje(10)(0,20 %): 7 8 7 6 7 8 7 6 5 4
Spavanje(10)(0,20 %): 7 8 7 6 7 8 7 6 5 6
Spavanje(10)(0,20 %): 7 8 7 6 7 8 7 6 7 6
Spavanje(10)(0,20 %): 7 8 7 6 7 8 7 6 7 8
Spavanje(10)(0,20 %): 7 8 7 6 7 8 7 8 7 6
Spavanje(10)(0,20 %): 7 8 7 6 7 8 7 8 7 8
Spavanje(10)(0,20 %): 7 8 7 6 7 8 7 8 9 10
Spavanje(10)(0,20 %): 7 8 7 6 7 8 7 8 9 8
Spavanje(10)(0,20 %): 7 8 7 6 7 8 9 8 7 6
Spavanje(10)(0,20 %): 7 8 7 6 7 8 9 8 7 8
Spavanje(10)(0,20 %): 7 8 7 6 7 8 9 8 9 10
Spavanje(10)(0,20 %): 7 8 7 6 7 8 9 8 9 8
Spavanje(10)(0,20 %): 7 8 7 8 7 6 5 4 3 2
Spavanje(10)(0,20 %): 7 8 7 8 7 6 5 4 3 4
Spavanje(10)(0,20 %): 7 8 7 8 7 6 5 4 5 4
Spavanje(10)(0,20 %): 7 8 7 8 7 6 5 4 5 6
Spavanje(10)(0,20 %): 7 8 7 8 7 6 5 6 5 4
Spavanje(10)(0,20 %): 7 8 7 8 7 6 5 6 5 6
Spavanje(10)(0,20 %): 7 8 7 8 7 6 5 6 7 6
Spavanje(10)(0,20 %): 7 8 7 8 7 6 5 6 7 8
Spavanje(10)(0,20 %): 7 8 7 8 7 6 7 6 5 4
Spavanje(10)(0,20 %): 7 8 7 8 7 6 7 6 5 6
Spavanje(10)(0,20 %): 7 8 7 8 7 6 7 6 7 6
Spavanje(10)(0,20 %): 7 8 7 8 7 6 7 6 7 8
Spavanje(10)(0,20 %): 7 8 7 8 7 6 7 8 7 6
Spavanje(10)(0,20 %): 7 8 7 8 7 6 7 8 7 8
Spavanje(10)(0,20 %): 7 8 7 8 7 6 7 8 9 10
Spavanje(10)(0,20 %): 7 8 7 8 7 6 7 8 9 8
Spavanje(10)(0,20 %): 7 8 7 8 7 8 7 6 5 4
Spavanje(10)(0,20 %): 7 8 7 8 7 8 7 6 5 6
Spavanje(10)(0,20 %): 7 8 7 8 7 8 7 6 7 6
Spavanje(10)(0,20 %): 7 8 7 8 7 8 7 6 7 8
Spavanje(10)(0,20 %): 7 8 7 8 7 8 7 8 7 6
Spavanje(10)(0,20 %): 7 8 7 8 7 8 7 8 7 8
Spavanje(10)(0,20 %): 7 8 7 8 7 8 7 8 9 10
Spavanje(10)(0,20 %): 7 8 7 8 7 8 7 8 9 8
Spavanje(10)(0,20 %): 7 8 7 8 7 8 9 8 7 6
Spavanje(10)(0,20 %): 7 8 7 8 7 8 9 8 7 8
Spavanje(10)(0,20 %): 7 8 7 8 7 8 9 8 9 10
Spavanje(10)(0,20 %): 7 8 7 8 7 8 9 8 9 8
Spavanje(10)(0,20 %): 7 8 7 8 9 8 7 6 5 4
Spavanje(10)(0,20 %): 7 8 7 8 9 8 7 6 5 6
Spavanje(10)(0,20 %): 7 8 7 8 9 8 7 6 7 6
Spavanje(10)(0,20 %): 7 8 7 8 9 8 7 6 7 8
Spavanje(10)(0,20 %): 7 8 7 8 9 8 7 8 7 6
Spavanje(10)(0,20 %): 7 8 7 8 9 8 7 8 7 8
Spavanje(10)(0,20 %): 7 8 7 8 9 8 7 8 9 10
Spavanje(10)(0,20 %): 7 8 7 8 9 8 7 8 9 8
Spavanje(10)(0,20 %): 7 8 7 8 9 8 9 8 7 6
Spavanje(10)(0,20 %): 7 8 7 8 9 8 9 8 7 8
Spavanje(10)(0,20 %): 7 8 7 8 9 8 9 8 9 10
Spavanje(10)(0,20 %): 7 8 7 8 9 8 9 8 9 8
Spavanje(10)(0,20 %): 7 8 9 8 7 6 5 4 3 2
Spavanje(10)(0,20 %): 7 8 9 8 7 6 5 4 3 4
Spavanje(10)(0,20 %): 7 8 9 8 7 6 5 4 5 4
Spavanje(10)(0,20 %): 7 8 9 8 7 6 5 4 5 6
Spavanje(10)(0,20 %): 7 8 9 8 7 6 5 6 5 4
Spavanje(10)(0,20 %): 7 8 9 8 7 6 5 6 5 6
Spavanje(10)(0,20 %): 7 8 9 8 7 6 5 6 7 6
Spavanje(10)(0,20 %): 7 8 9 8 7 6 5 6 7 8
Spavanje(10)(0,20 %): 7 8 9 8 7 6 7 6 5 4
Spavanje(10)(0,20 %): 7 8 9 8 7 6 7 6 5 6
Spavanje(10)(0,20 %): 7 8 9 8 7 6 7 6 7 6
Spavanje(10)(0,20 %): 7 8 9 8 7 6 7 6 7 8
Spavanje(10)(0,20 %): 7 8 9 8 7 6 7 8 7 6
Spavanje(10)(0,20 %): 7 8 9 8 7 6 7 8 7 8
Spavanje(10)(0,20 %): 7 8 9 8 7 6 7 8 9 10
Spavanje(10)(0,20 %): 7 8 9 8 7 6 7 8 9 8
Spavanje(10)(0,20 %): 7 8 9 8 7 8 7 6 5 4
Spavanje(10)(0,20 %): 7 8 9 8 7 8 7 6 5 6
Spavanje(10)(0,20 %): 7 8 9 8 7 8 7 6 7 6
Spavanje(10)(0,20 %): 7 8 9 8 7 8 7 6 7 8
Spavanje(10)(0,20 %): 7 8 9 8 7 8 7 8 7 6
Spavanje(10)(0,20 %): 7 8 9 8 7 8 7 8 7 8
Spavanje(10)(0,20 %): 7 8 9 8 7 8 7 8 9 10
Spavanje(10)(0,20 %): 7 8 9 8 7 8 7 8 9 8
Spavanje(10)(0,20 %): 7 8 9 8 7 8 9 8 7 6
Spavanje(10)(0,20 %): 7 8 9 8 7 8 9 8 7 8
Spavanje(10)(0,20 %): 7 8 9 8 7 8 9 8 9 10
Spavanje(10)(0,20 %): 7 8 9 8 7 8 9 8 9 8
Spavanje(10)(0,20 %): 7 8 9 8 9 8 7 6 5 4
Spavanje(10)(0,20 %): 7 8 9 8 9 8 7 6 5 6
Spavanje(10)(0,20 %): 7 8 9 8 9 8 7 6 7 6
Spavanje(10)(0,20 %): 7 8 9 8 9 8 7 6 7 8
Spavanje(10)(0,20 %): 7 8 9 8 9 8 7 8 7 6
Spavanje(10)(0,20 %): 7 8 9 8 9 8 7 8 7 8
Spavanje(10)(0,20 %): 7 8 9 8 9 8 7 8 9 10
Spavanje(10)(0,20 %): 7 8 9 8 9 8 7 8 9 8
Spavanje(10)(0,20 %): 7 8 9 8 9 8 9 8 7 6
Spavanje(10)(0,20 %): 7 8 9 8 9 8 9 8 7 8
Spavanje(10)(0,20 %): 7 8 9 8 9 8 9 8 9 10
Spavanje(10)(0,20 %): 7 8 9 8 9 8 9 8 9 8

output svih putanja se lako dobija ako se napravi graf koji sam pominjao ranije i obidje, ali mrzi me sad da ga sredjujem da lici na nesto. ako nekome bas treba nek me cima...

marko_n · 18.02.2010

Moja simulacija je napisana u Javi, ostatak koda nije bitan, evo samo metode za pomeranje mornara od bandere do bandere:

Kod:

    /** Metoda pomera mornara 10 puta (10 udaraca) i potom vraca stanje mornara.
     * 
     * @return Stanje mornara. Moze biti SPAVA, ZATVOR_ZASPAO, ZATVOR_TUCA
     */
    public StanjeMornara go() {

        for (int i = 1; i <= 10; i++) { // 10 pomeranja-udaraca

            bandera += rnd.nextBoolean() == true ? 1 : -1; // na koju ce stranu

            if (bandera == 11) { // Stigao do 11. "bandere" sto je kafana
                return StanjeMornara.ZATVOR_TUCA;
            }

            if (bandera == 0) { // Stigao do 0. "bandere" sto je luka
                return StanjeMornara.SPAVA;
            }

        }
        return StanjeMornara.ZATVOR_ZASPAO;  // Zaspao na ulici
    }

Prosek posle 8 milion ponavljanja je 13573.9795.

Mornar se kroz for petlju pomera 10 puta, i proverava se da li je stigao do luke ili kafane, ako nije stigao ni tamo ni ovamo, znači da je zaspao, metoda vraća enum vrednost koja definiše kako je mornar završio svoj put.

Ako je bandera 0 = luka, onda bi po mom mišljenju, kafana trebala da bude "bandera" 11. Mornar kad stigne kod bandere 10 udari u nju i opet se zavrti i može da uđe u kafanu ili da se vrati ka devetoj banderi, isto važi i za luku, kad udari u prvu banderu može da se vrati ka drugoj ili da ode u luku, tako da bih ja ta dva slučaja tretirao jednako. Mišljenja? :smash:

Drugo ako do "bandere" 11 ili 0 stigne sa 10 udaraca, neće zaspati jer se u ovoj petlji i kafana i luka računaju kao bandere, što zapravo nisu, pa je i taj deseti udarac nepostojeći.

Eto, jeste što kaže Bahati simulacija malo bezveze rešenje, ali čisto prvo da utvrdimo precizan algoritam pomeranja mornara.

Bahati [SiD] · 18.02.2010

moze i tako i ima vise smisla:

verovatnoca da upadne u vodu: 2,14843750 %
verovatnoca da udje u kafanu: 17,96875000 %
verovatnoca da udari 10 puta u banderu: 79,88281250 %
ukupno: 100,00000000 %
tuca za 200 mornara: 7187,50 $
spavanje na ulici za 200 mornara: 4792,97 $
ukupno: 11980,47 $

putanje:

K (05) : 07 08 09 10 11
K (07) : 07 06 07 08 09 10 11
K (07) : 07 08 07 08 09 10 11
K (07) : 07 08 09 08 09 10 11
K (07) : 07 08 09 10 09 10 11
K (09) : 07 06 05 06 07 08 09 10 11
K (09) : 07 06 07 06 07 08 09 10 11
K (09) : 07 06 07 08 07 08 09 10 11
K (09) : 07 06 07 08 09 08 09 10 11
K (09) : 07 06 07 08 09 10 09 10 11
K (09) : 07 08 07 06 07 08 09 10 11
K (09) : 07 08 07 08 07 08 09 10 11
K (09) : 07 08 07 08 09 08 09 10 11
K (09) : 07 08 07 08 09 10 09 10 11
K (09) : 07 08 09 08 07 08 09 10 11
K (09) : 07 08 09 08 09 08 09 10 11
K (09) : 07 08 09 08 09 10 09 10 11
K (09) : 07 08 09 10 09 08 09 10 11
K (09) : 07 08 09 10 09 10 09 10 11
L (08) : 07 06 05 04 03 02 01 00
L (10) : 07 06 05 04 03 02 01 02 01 00
L (10) : 07 06 05 04 03 02 03 02 01 00
L (10) : 07 06 05 04 03 04 03 02 01 00
L (10) : 07 06 05 04 05 04 03 02 01 00
L (10) : 07 06 05 06 05 04 03 02 01 00
L (10) : 07 06 07 06 05 04 03 02 01 00
L (10) : 07 08 07 06 05 04 03 02 01 00
S (10) : 07 06 05 04 03 02 01 02 01 02
S (10) : 07 06 05 04 03 02 01 02 03 02
S (10) : 07 06 05 04 03 02 01 02 03 04
S (10) : 07 06 05 04 03 02 03 02 01 02
S (10) : 07 06 05 04 03 02 03 02 03 02
S (10) : 07 06 05 04 03 02 03 02 03 04
S (10) : 07 06 05 04 03 02 03 04 03 02
S (10) : 07 06 05 04 03 02 03 04 03 04
S (10) : 07 06 05 04 03 02 03 04 05 04
S (10) : 07 06 05 04 03 02 03 04 05 06
S (10) : 07 06 05 04 03 04 03 02 01 02
S (10) : 07 06 05 04 03 04 03 02 03 02
S (10) : 07 06 05 04 03 04 03 02 03 04
S (10) : 07 06 05 04 03 04 03 04 03 02
S (10) : 07 06 05 04 03 04 03 04 03 04
S (10) : 07 06 05 04 03 04 03 04 05 04
S (10) : 07 06 05 04 03 04 03 04 05 06
S (10) : 07 06 05 04 03 04 05 04 03 02
S (10) : 07 06 05 04 03 04 05 04 03 04
S (10) : 07 06 05 04 03 04 05 04 05 04
S (10) : 07 06 05 04 03 04 05 04 05 06
S (10) : 07 06 05 04 03 04 05 06 05 04
S (10) : 07 06 05 04 03 04 05 06 05 06
S (10) : 07 06 05 04 03 04 05 06 07 06
S (10) : 07 06 05 04 03 04 05 06 07 08
S (10) : 07 06 05 04 05 04 03 02 01 02
S (10) : 07 06 05 04 05 04 03 02 03 02
S (10) : 07 06 05 04 05 04 03 02 03 04
S (10) : 07 06 05 04 05 04 03 04 03 02
S (10) : 07 06 05 04 05 04 03 04 03 04
S (10) : 07 06 05 04 05 04 03 04 05 04
S (10) : 07 06 05 04 05 04 03 04 05 06
S (10) : 07 06 05 04 05 04 05 04 03 02
S (10) : 07 06 05 04 05 04 05 04 03 04
S (10) : 07 06 05 04 05 04 05 04 05 04
S (10) : 07 06 05 04 05 04 05 04 05 06
S (10) : 07 06 05 04 05 04 05 06 05 04
S (10) : 07 06 05 04 05 04 05 06 05 06
S (10) : 07 06 05 04 05 04 05 06 07 06
S (10) : 07 06 05 04 05 04 05 06 07 08
S (10) : 07 06 05 04 05 06 05 04 03 02
S (10) : 07 06 05 04 05 06 05 04 03 04
S (10) : 07 06 05 04 05 06 05 04 05 04
S (10) : 07 06 05 04 05 06 05 04 05 06
S (10) : 07 06 05 04 05 06 05 06 05 04
S (10) : 07 06 05 04 05 06 05 06 05 06
S (10) : 07 06 05 04 05 06 05 06 07 06
S (10) : 07 06 05 04 05 06 05 06 07 08
S (10) : 07 06 05 04 05 06 07 06 05 04
S (10) : 07 06 05 04 05 06 07 06 05 06
S (10) : 07 06 05 04 05 06 07 06 07 06
S (10) : 07 06 05 04 05 06 07 06 07 08
S (10) : 07 06 05 04 05 06 07 08 07 06
S (10) : 07 06 05 04 05 06 07 08 07 08
S (10) : 07 06 05 04 05 06 07 08 09 08
S (10) : 07 06 05 04 05 06 07 08 09 10
S (10) : 07 06 05 06 05 04 03 02 01 02
S (10) : 07 06 05 06 05 04 03 02 03 02
S (10) : 07 06 05 06 05 04 03 02 03 04
S (10) : 07 06 05 06 05 04 03 04 03 02
S (10) : 07 06 05 06 05 04 03 04 03 04
S (10) : 07 06 05 06 05 04 03 04 05 04
S (10) : 07 06 05 06 05 04 03 04 05 06
S (10) : 07 06 05 06 05 04 05 04 03 02
S (10) : 07 06 05 06 05 04 05 04 03 04
S (10) : 07 06 05 06 05 04 05 04 05 04
S (10) : 07 06 05 06 05 04 05 04 05 06
S (10) : 07 06 05 06 05 04 05 06 05 04
S (10) : 07 06 05 06 05 04 05 06 05 06
S (10) : 07 06 05 06 05 04 05 06 07 06
S (10) : 07 06 05 06 05 04 05 06 07 08
S (10) : 07 06 05 06 05 06 05 04 03 02
S (10) : 07 06 05 06 05 06 05 04 03 04
S (10) : 07 06 05 06 05 06 05 04 05 04
S (10) : 07 06 05 06 05 06 05 04 05 06
S (10) : 07 06 05 06 05 06 05 06 05 04
S (10) : 07 06 05 06 05 06 05 06 05 06
S (10) : 07 06 05 06 05 06 05 06 07 06
S (10) : 07 06 05 06 05 06 05 06 07 08
S (10) : 07 06 05 06 05 06 07 06 05 04
S (10) : 07 06 05 06 05 06 07 06 05 06
S (10) : 07 06 05 06 05 06 07 06 07 06
S (10) : 07 06 05 06 05 06 07 06 07 08
S (10) : 07 06 05 06 05 06 07 08 07 06
S (10) : 07 06 05 06 05 06 07 08 07 08
S (10) : 07 06 05 06 05 06 07 08 09 08
S (10) : 07 06 05 06 05 06 07 08 09 10
S (10) : 07 06 05 06 07 06 05 04 03 02
S (10) : 07 06 05 06 07 06 05 04 03 04
S (10) : 07 06 05 06 07 06 05 04 05 04
S (10) : 07 06 05 06 07 06 05 04 05 06
S (10) : 07 06 05 06 07 06 05 06 05 04
S (10) : 07 06 05 06 07 06 05 06 05 06
S (10) : 07 06 05 06 07 06 05 06 07 06
S (10) : 07 06 05 06 07 06 05 06 07 08
S (10) : 07 06 05 06 07 06 07 06 05 04
S (10) : 07 06 05 06 07 06 07 06 05 06
S (10) : 07 06 05 06 07 06 07 06 07 06
S (10) : 07 06 05 06 07 06 07 06 07 08
S (10) : 07 06 05 06 07 06 07 08 07 06
S (10) : 07 06 05 06 07 06 07 08 07 08
S (10) : 07 06 05 06 07 06 07 08 09 08
S (10) : 07 06 05 06 07 06 07 08 09 10
S (10) : 07 06 05 06 07 08 07 06 05 04
S (10) : 07 06 05 06 07 08 07 06 05 06
S (10) : 07 06 05 06 07 08 07 06 07 06
S (10) : 07 06 05 06 07 08 07 06 07 08
S (10) : 07 06 05 06 07 08 07 08 07 06
S (10) : 07 06 05 06 07 08 07 08 07 08
S (10) : 07 06 05 06 07 08 07 08 09 08
S (10) : 07 06 05 06 07 08 07 08 09 10
S (10) : 07 06 05 06 07 08 09 08 07 06
S (10) : 07 06 05 06 07 08 09 08 07 08
S (10) : 07 06 05 06 07 08 09 08 09 08
S (10) : 07 06 05 06 07 08 09 08 09 10
S (10) : 07 06 05 06 07 08 09 10 09 08
S (10) : 07 06 05 06 07 08 09 10 09 10
S (10) : 07 06 07 06 05 04 03 02 01 02
S (10) : 07 06 07 06 05 04 03 02 03 02
S (10) : 07 06 07 06 05 04 03 02 03 04
S (10) : 07 06 07 06 05 04 03 04 03 02
S (10) : 07 06 07 06 05 04 03 04 03 04
S (10) : 07 06 07 06 05 04 03 04 05 04
S (10) : 07 06 07 06 05 04 03 04 05 06
S (10) : 07 06 07 06 05 04 05 04 03 02
S (10) : 07 06 07 06 05 04 05 04 03 04
S (10) : 07 06 07 06 05 04 05 04 05 04
S (10) : 07 06 07 06 05 04 05 04 05 06
S (10) : 07 06 07 06 05 04 05 06 05 04
S (10) : 07 06 07 06 05 04 05 06 05 06
S (10) : 07 06 07 06 05 04 05 06 07 06
S (10) : 07 06 07 06 05 04 05 06 07 08
S (10) : 07 06 07 06 05 06 05 04 03 02
S (10) : 07 06 07 06 05 06 05 04 03 04
S (10) : 07 06 07 06 05 06 05 04 05 04
S (10) : 07 06 07 06 05 06 05 04 05 06
S (10) : 07 06 07 06 05 06 05 06 05 04
S (10) : 07 06 07 06 05 06 05 06 05 06
S (10) : 07 06 07 06 05 06 05 06 07 06
S (10) : 07 06 07 06 05 06 05 06 07 08
S (10) : 07 06 07 06 05 06 07 06 05 04
S (10) : 07 06 07 06 05 06 07 06 05 06
S (10) : 07 06 07 06 05 06 07 06 07 06
S (10) : 07 06 07 06 05 06 07 06 07 08
S (10) : 07 06 07 06 05 06 07 08 07 06
S (10) : 07 06 07 06 05 06 07 08 07 08
S (10) : 07 06 07 06 05 06 07 08 09 08
S (10) : 07 06 07 06 05 06 07 08 09 10
S (10) : 07 06 07 06 07 06 05 04 03 02
S (10) : 07 06 07 06 07 06 05 04 03 04
S (10) : 07 06 07 06 07 06 05 04 05 04
S (10) : 07 06 07 06 07 06 05 04 05 06
S (10) : 07 06 07 06 07 06 05 06 05 04
S (10) : 07 06 07 06 07 06 05 06 05 06
S (10) : 07 06 07 06 07 06 05 06 07 06
S (10) : 07 06 07 06 07 06 05 06 07 08
S (10) : 07 06 07 06 07 06 07 06 05 04
S (10) : 07 06 07 06 07 06 07 06 05 06
S (10) : 07 06 07 06 07 06 07 06 07 06
S (10) : 07 06 07 06 07 06 07 06 07 08
S (10) : 07 06 07 06 07 06 07 08 07 06
S (10) : 07 06 07 06 07 06 07 08 07 08
S (10) : 07 06 07 06 07 06 07 08 09 08
S (10) : 07 06 07 06 07 06 07 08 09 10
S (10) : 07 06 07 06 07 08 07 06 05 04
S (10) : 07 06 07 06 07 08 07 06 05 06
S (10) : 07 06 07 06 07 08 07 06 07 06
S (10) : 07 06 07 06 07 08 07 06 07 08
S (10) : 07 06 07 06 07 08 07 08 07 06
S (10) : 07 06 07 06 07 08 07 08 07 08
S (10) : 07 06 07 06 07 08 07 08 09 08
S (10) : 07 06 07 06 07 08 07 08 09 10
S (10) : 07 06 07 06 07 08 09 08 07 06
S (10) : 07 06 07 06 07 08 09 08 07 08
S (10) : 07 06 07 06 07 08 09 08 09 08
S (10) : 07 06 07 06 07 08 09 08 09 10
S (10) : 07 06 07 06 07 08 09 10 09 08
S (10) : 07 06 07 06 07 08 09 10 09 10
S (10) : 07 06 07 08 07 06 05 04 03 02
S (10) : 07 06 07 08 07 06 05 04 03 04
S (10) : 07 06 07 08 07 06 05 04 05 04
S (10) : 07 06 07 08 07 06 05 04 05 06
S (10) : 07 06 07 08 07 06 05 06 05 04
S (10) : 07 06 07 08 07 06 05 06 05 06
S (10) : 07 06 07 08 07 06 05 06 07 06
S (10) : 07 06 07 08 07 06 05 06 07 08
S (10) : 07 06 07 08 07 06 07 06 05 04
S (10) : 07 06 07 08 07 06 07 06 05 06
S (10) : 07 06 07 08 07 06 07 06 07 06
S (10) : 07 06 07 08 07 06 07 06 07 08
S (10) : 07 06 07 08 07 06 07 08 07 06
S (10) : 07 06 07 08 07 06 07 08 07 08
S (10) : 07 06 07 08 07 06 07 08 09 08
S (10) : 07 06 07 08 07 06 07 08 09 10
S (10) : 07 06 07 08 07 08 07 06 05 04
S (10) : 07 06 07 08 07 08 07 06 05 06
S (10) : 07 06 07 08 07 08 07 06 07 06
S (10) : 07 06 07 08 07 08 07 06 07 08
S (10) : 07 06 07 08 07 08 07 08 07 06
S (10) : 07 06 07 08 07 08 07 08 07 08
S (10) : 07 06 07 08 07 08 07 08 09 08
S (10) : 07 06 07 08 07 08 07 08 09 10
S (10) : 07 06 07 08 07 08 09 08 07 06
S (10) : 07 06 07 08 07 08 09 08 07 08
S (10) : 07 06 07 08 07 08 09 08 09 08
S (10) : 07 06 07 08 07 08 09 08 09 10
S (10) : 07 06 07 08 07 08 09 10 09 08
S (10) : 07 06 07 08 07 08 09 10 09 10
S (10) : 07 06 07 08 09 08 07 06 05 04
S (10) : 07 06 07 08 09 08 07 06 05 06
S (10) : 07 06 07 08 09 08 07 06 07 06
S (10) : 07 06 07 08 09 08 07 06 07 08
S (10) : 07 06 07 08 09 08 07 08 07 06
S (10) : 07 06 07 08 09 08 07 08 07 08
S (10) : 07 06 07 08 09 08 07 08 09 08
S (10) : 07 06 07 08 09 08 07 08 09 10
S (10) : 07 06 07 08 09 08 09 08 07 06
S (10) : 07 06 07 08 09 08 09 08 07 08
S (10) : 07 06 07 08 09 08 09 08 09 08
S (10) : 07 06 07 08 09 08 09 08 09 10
S (10) : 07 06 07 08 09 08 09 10 09 08
S (10) : 07 06 07 08 09 08 09 10 09 10
S (10) : 07 06 07 08 09 10 09 08 07 06
S (10) : 07 06 07 08 09 10 09 08 07 08
S (10) : 07 06 07 08 09 10 09 08 09 08
S (10) : 07 06 07 08 09 10 09 08 09 10
S (10) : 07 06 07 08 09 10 09 10 09 08
S (10) : 07 06 07 08 09 10 09 10 09 10
S (10) : 07 08 07 06 05 04 03 02 01 02
S (10) : 07 08 07 06 05 04 03 02 03 02
S (10) : 07 08 07 06 05 04 03 02 03 04
S (10) : 07 08 07 06 05 04 03 04 03 02
S (10) : 07 08 07 06 05 04 03 04 03 04
S (10) : 07 08 07 06 05 04 03 04 05 04
S (10) : 07 08 07 06 05 04 03 04 05 06
S (10) : 07 08 07 06 05 04 05 04 03 02
S (10) : 07 08 07 06 05 04 05 04 03 04
S (10) : 07 08 07 06 05 04 05 04 05 04
S (10) : 07 08 07 06 05 04 05 04 05 06
S (10) : 07 08 07 06 05 04 05 06 05 04
S (10) : 07 08 07 06 05 04 05 06 05 06
S (10) : 07 08 07 06 05 04 05 06 07 06
S (10) : 07 08 07 06 05 04 05 06 07 08
S (10) : 07 08 07 06 05 06 05 04 03 02
S (10) : 07 08 07 06 05 06 05 04 03 04
S (10) : 07 08 07 06 05 06 05 04 05 04
S (10) : 07 08 07 06 05 06 05 04 05 06
S (10) : 07 08 07 06 05 06 05 06 05 04
S (10) : 07 08 07 06 05 06 05 06 05 06
S (10) : 07 08 07 06 05 06 05 06 07 06
S (10) : 07 08 07 06 05 06 05 06 07 08
S (10) : 07 08 07 06 05 06 07 06 05 04
S (10) : 07 08 07 06 05 06 07 06 05 06
S (10) : 07 08 07 06 05 06 07 06 07 06
S (10) : 07 08 07 06 05 06 07 06 07 08
S (10) : 07 08 07 06 05 06 07 08 07 06
S (10) : 07 08 07 06 05 06 07 08 07 08
S (10) : 07 08 07 06 05 06 07 08 09 08
S (10) : 07 08 07 06 05 06 07 08 09 10
S (10) : 07 08 07 06 07 06 05 04 03 02
S (10) : 07 08 07 06 07 06 05 04 03 04
S (10) : 07 08 07 06 07 06 05 04 05 04
S (10) : 07 08 07 06 07 06 05 04 05 06
S (10) : 07 08 07 06 07 06 05 06 05 04
S (10) : 07 08 07 06 07 06 05 06 05 06
S (10) : 07 08 07 06 07 06 05 06 07 06
S (10) : 07 08 07 06 07 06 05 06 07 08
S (10) : 07 08 07 06 07 06 07 06 05 04
S (10) : 07 08 07 06 07 06 07 06 05 06
S (10) : 07 08 07 06 07 06 07 06 07 06
S (10) : 07 08 07 06 07 06 07 06 07 08
S (10) : 07 08 07 06 07 06 07 08 07 06
S (10) : 07 08 07 06 07 06 07 08 07 08
S (10) : 07 08 07 06 07 06 07 08 09 08
S (10) : 07 08 07 06 07 06 07 08 09 10
S (10) : 07 08 07 06 07 08 07 06 05 04
S (10) : 07 08 07 06 07 08 07 06 05 06
S (10) : 07 08 07 06 07 08 07 06 07 06
S (10) : 07 08 07 06 07 08 07 06 07 08
S (10) : 07 08 07 06 07 08 07 08 07 06
S (10) : 07 08 07 06 07 08 07 08 07 08
S (10) : 07 08 07 06 07 08 07 08 09 08
S (10) : 07 08 07 06 07 08 07 08 09 10
S (10) : 07 08 07 06 07 08 09 08 07 06
S (10) : 07 08 07 06 07 08 09 08 07 08
S (10) : 07 08 07 06 07 08 09 08 09 08
S (10) : 07 08 07 06 07 08 09 08 09 10
S (10) : 07 08 07 06 07 08 09 10 09 08
S (10) : 07 08 07 06 07 08 09 10 09 10
S (10) : 07 08 07 08 07 06 05 04 03 02
S (10) : 07 08 07 08 07 06 05 04 03 04
S (10) : 07 08 07 08 07 06 05 04 05 04
S (10) : 07 08 07 08 07 06 05 04 05 06
S (10) : 07 08 07 08 07 06 05 06 05 04
S (10) : 07 08 07 08 07 06 05 06 05 06
S (10) : 07 08 07 08 07 06 05 06 07 06
S (10) : 07 08 07 08 07 06 05 06 07 08
S (10) : 07 08 07 08 07 06 07 06 05 04
S (10) : 07 08 07 08 07 06 07 06 05 06
S (10) : 07 08 07 08 07 06 07 06 07 06
S (10) : 07 08 07 08 07 06 07 06 07 08
S (10) : 07 08 07 08 07 06 07 08 07 06
S (10) : 07 08 07 08 07 06 07 08 07 08
S (10) : 07 08 07 08 07 06 07 08 09 08
S (10) : 07 08 07 08 07 06 07 08 09 10
S (10) : 07 08 07 08 07 08 07 06 05 04
S (10) : 07 08 07 08 07 08 07 06 05 06
S (10) : 07 08 07 08 07 08 07 06 07 06
S (10) : 07 08 07 08 07 08 07 06 07 08
S (10) : 07 08 07 08 07 08 07 08 07 06
S (10) : 07 08 07 08 07 08 07 08 07 08
S (10) : 07 08 07 08 07 08 07 08 09 08
S (10) : 07 08 07 08 07 08 07 08 09 10
S (10) : 07 08 07 08 07 08 09 08 07 06
S (10) : 07 08 07 08 07 08 09 08 07 08
S (10) : 07 08 07 08 07 08 09 08 09 08
S (10) : 07 08 07 08 07 08 09 08 09 10
S (10) : 07 08 07 08 07 08 09 10 09 08
S (10) : 07 08 07 08 07 08 09 10 09 10
S (10) : 07 08 07 08 09 08 07 06 05 04
S (10) : 07 08 07 08 09 08 07 06 05 06
S (10) : 07 08 07 08 09 08 07 06 07 06
S (10) : 07 08 07 08 09 08 07 06 07 08
S (10) : 07 08 07 08 09 08 07 08 07 06
S (10) : 07 08 07 08 09 08 07 08 07 08
S (10) : 07 08 07 08 09 08 07 08 09 08
S (10) : 07 08 07 08 09 08 07 08 09 10
S (10) : 07 08 07 08 09 08 09 08 07 06
S (10) : 07 08 07 08 09 08 09 08 07 08
S (10) : 07 08 07 08 09 08 09 08 09 08
S (10) : 07 08 07 08 09 08 09 08 09 10
S (10) : 07 08 07 08 09 08 09 10 09 08
S (10) : 07 08 07 08 09 08 09 10 09 10
S (10) : 07 08 07 08 09 10 09 08 07 06
S (10) : 07 08 07 08 09 10 09 08 07 08
S (10) : 07 08 07 08 09 10 09 08 09 08
S (10) : 07 08 07 08 09 10 09 08 09 10
S (10) : 07 08 07 08 09 10 09 10 09 08
S (10) : 07 08 07 08 09 10 09 10 09 10
S (10) : 07 08 09 08 07 06 05 04 03 02
S (10) : 07 08 09 08 07 06 05 04 03 04
S (10) : 07 08 09 08 07 06 05 04 05 04
S (10) : 07 08 09 08 07 06 05 04 05 06
S (10) : 07 08 09 08 07 06 05 06 05 04
S (10) : 07 08 09 08 07 06 05 06 05 06
S (10) : 07 08 09 08 07 06 05 06 07 06
S (10) : 07 08 09 08 07 06 05 06 07 08
S (10) : 07 08 09 08 07 06 07 06 05 04
S (10) : 07 08 09 08 07 06 07 06 05 06
S (10) : 07 08 09 08 07 06 07 06 07 06
S (10) : 07 08 09 08 07 06 07 06 07 08
S (10) : 07 08 09 08 07 06 07 08 07 06
S (10) : 07 08 09 08 07 06 07 08 07 08
S (10) : 07 08 09 08 07 06 07 08 09 08
S (10) : 07 08 09 08 07 06 07 08 09 10
S (10) : 07 08 09 08 07 08 07 06 05 04
S (10) : 07 08 09 08 07 08 07 06 05 06
S (10) : 07 08 09 08 07 08 07 06 07 06
S (10) : 07 08 09 08 07 08 07 06 07 08
S (10) : 07 08 09 08 07 08 07 08 07 06
S (10) : 07 08 09 08 07 08 07 08 07 08
S (10) : 07 08 09 08 07 08 07 08 09 08
S (10) : 07 08 09 08 07 08 07 08 09 10
S (10) : 07 08 09 08 07 08 09 08 07 06
S (10) : 07 08 09 08 07 08 09 08 07 08
S (10) : 07 08 09 08 07 08 09 08 09 08
S (10) : 07 08 09 08 07 08 09 08 09 10
S (10) : 07 08 09 08 07 08 09 10 09 08
S (10) : 07 08 09 08 07 08 09 10 09 10
S (10) : 07 08 09 08 09 08 07 06 05 04
S (10) : 07 08 09 08 09 08 07 06 05 06
S (10) : 07 08 09 08 09 08 07 06 07 06
S (10) : 07 08 09 08 09 08 07 06 07 08
S (10) : 07 08 09 08 09 08 07 08 07 06
S (10) : 07 08 09 08 09 08 07 08 07 08
S (10) : 07 08 09 08 09 08 07 08 09 08
S (10) : 07 08 09 08 09 08 07 08 09 10
S (10) : 07 08 09 08 09 08 09 08 07 06
S (10) : 07 08 09 08 09 08 09 08 07 08
S (10) : 07 08 09 08 09 08 09 08 09 08
S (10) : 07 08 09 08 09 08 09 08 09 10
S (10) : 07 08 09 08 09 08 09 10 09 08
S (10) : 07 08 09 08 09 08 09 10 09 10
S (10) : 07 08 09 08 09 10 09 08 07 06
S (10) : 07 08 09 08 09 10 09 08 07 08
S (10) : 07 08 09 08 09 10 09 08 09 08
S (10) : 07 08 09 08 09 10 09 08 09 10
S (10) : 07 08 09 08 09 10 09 10 09 08
S (10) : 07 08 09 08 09 10 09 10 09 10
S (10) : 07 08 09 10 09 08 07 06 05 04
S (10) : 07 08 09 10 09 08 07 06 05 06
S (10) : 07 08 09 10 09 08 07 06 07 06
S (10) : 07 08 09 10 09 08 07 06 07 08
S (10) : 07 08 09 10 09 08 07 08 07 06
S (10) : 07 08 09 10 09 08 07 08 07 08
S (10) : 07 08 09 10 09 08 07 08 09 08
S (10) : 07 08 09 10 09 08 07 08 09 10
S (10) : 07 08 09 10 09 08 09 08 07 06
S (10) : 07 08 09 10 09 08 09 08 07 08
S (10) : 07 08 09 10 09 08 09 08 09 08
S (10) : 07 08 09 10 09 08 09 08 09 10
S (10) : 07 08 09 10 09 08 09 10 09 08
S (10) : 07 08 09 10 09 08 09 10 09 10
S (10) : 07 08 09 10 09 10 09 08 07 06
S (10) : 07 08 09 10 09 10 09 08 07 08
S (10) : 07 08 09 10 09 10 09 08 09 08
S (10) : 07 08 09 10 09 10 09 08 09 10
S (10) : 07 08 09 10 09 10 09 10 09 08
S (10) : 07 08 09 10 09 10 09 10 09 10

svaka putanja do kafane se mora zavrsavati sa 11 (kafana)
svaka putanja do luke se mora zavrsavati sa 0 (luka)
svaka putanja do spavanja mora imati duzinu deset i ne sme se zavrsavati sa 0 ili 11 (luka ili kafana), tj. ako je 10-i korak jedno od ta dva upada tamo.

stavljam to zato sto je dovoljno naci duplikat, putanju koja nedostaje ili ne odgovara pravilima da bi se srusio algo.

sad i simulacija mnogo bolje radi, ko zna sta smo gresili ranije.

na ~100M iteracija ubode prve tri decimale, mada se tada vec postavlja pitanje kvaliteta rnd brojeva...

HUH! to bi bilo to sto se mene tice.

marko_n · 18.02.2010

Bahati [SiD] je napisao(la):
ukupno: 11980,47 $

Dobijem identičan rezultat kad u gornjoj petlji "i" ide do <= 9.

Mislim da im u tvojoj simulaciji daješ jedan potez manje nego što bi trebalo?

Bahati [SiD] · 18.02.2010

marko_n je napisao(la):
Dobijem identičan rezultat kad u gornjoj petlji "i" ide do <= 9.

Mislim da im u tvojoj simulaciji daješ jedan potez manje nego što bi trebalo?

nije to simulacija, to je egzaktno matematicko resenje.

imas tamo sve moguce putanje pa vidi... meni se cini da je ok i da ima poteza koliko treba, tj. max 10.

i tesko da dobijas identican, mada se nikad ne zna sa tim rnd stvarima... :d

11980,468750$

ps. mozda si negde zeznuo da li se racuna pocetna, sedma bandera kao udarac? pa mu dodje taj jedan + 9 na ispravno, tj. 10?

marko_n · 18.02.2010

Tu sam zeznuo, nisam računao sedmu banderu kao udarac, pa sam im davao jedan potez više.

Tako da je rešenje koje daje moja simulacija $11980.

Evo ga output koji izbacuje na svakih 500 hiljada iteracija, minimalna i maksimalna kazna do tada, kao i prosek:

Sim No: 500001 Min: 7860 Max: 16820 Average: 11982.358115283872
Sim No: 1000001 Min: 7860 Max: 16820 Average: 11981.647688352266
Sim No: 1500001 Min: 7860 Max: 16820 Average: 11980.957539361605
Sim No: 2000001 Min: 7860 Max: 17020 Average: 11980.319989839978
Sim No: 2500001 Min: 7800 Max: 17020 Average: 11980.49800380089
Sim No: 3000001 Min: 7800 Max: 17020 Average: 11980.42773319134
Sim No: 3500001 Min: 7800 Max: 17470 Average: 11980.319325623552
Sim No: 4000001 Min: 7800 Max: 17470 Average: 11980.308417423334
Sim No: 4500001 Min: 7800 Max: 17470 Average: 11980.298422156142
Sim No: 5000001 Min: 7780 Max: 17470 Average: 11980.533209893882
Sim No: 5500001 Min: 7380 Max: 17470 Average: 11980.600918072389
Sim No: 6000001 Min: 7380 Max: 17580 Average: 11980.5071499158
Sim No: 6500001 Min: 7380 Max: 17580 Average: 11980.57494145031
Sim No: 7000001 Min: 7380 Max: 17580 Average: 11980.738599894765
Sim No: 7500001 Min: 7380 Max: 17580 Average: 11980.78214656264
Sim No: 8000001 Min: 7380 Max: 17580 Average: 11980.727747409275
Sim No: 8500001 Min: 7380 Max: 17580 Average: 11980.85602931135
Sim No: 9000001 Min: 7380 Max: 17580 Average: 11980.807858799237
Sim No: 9500001 Min: 7380 Max: 17580 Average: 11980.744986236823
Sim No: 10000001 Min: 7380 Max: 17580 Average: 11980.794298920257
Sim No: 10500001 Min: 7380 Max: 17580 Average: 11980.765818974869
Sim No: 11000001 Min: 7380 Max: 17580 Average: 11980.751249023207
Sim No: 11500001 Min: 7380 Max: 17580 Average: 11980.783565149786
Sim No: 12000001 Min: 7380 Max: 17580 Average: 11980.738420772306
Sim No: 12500001 Min: 7380 Max: 17580 Average: 11980.740270341266
Sim No: 13000001 Min: 7380 Max: 17580 Average: 11980.709726099722
Sim No: 13500001 Min: 7380 Max: 17580 Average: 11980.668271802802
Sim No: 14000001 Min: 7380 Max: 17580 Average: 11980.62066709896
Sim No: 14500001 Min: 7380 Max: 17580 Average: 11980.610040648004
Sim No: 15000001 Min: 7380 Max: 17580 Average: 11980.596319960652
Sim No: 15500001 Min: 7380 Max: 17580 Average: 11980.65603544194
Sim No: 16000001 Min: 7380 Max: 17580 Average: 11980.614939961948
Sim No: 16500001 Min: 7380 Max: 17580 Average: 11980.637004810249
Sim No: 17000001 Min: 7380 Max: 17580 Average: 11980.60684878812
Sim No: 17500001 Min: 7380 Max: 17580 Average: 11980.61560910792
Sim No: 18000001 Min: 7380 Max: 17580 Average: 11980.61010885526
Sim No: 18500001 Min: 7380 Max: 17580 Average: 11980.61968375071
Sim No: 19000001 Min: 7380 Max: 17580 Average: 11980.615685230687
Sim No: 19500001 Min: 7380 Max: 17580 Average: 11980.579878432087

Pogledaću kasnije tvoje rešenje sa grafovima, pogledao sam za sada samo putanje i deluje mi sve OK!

WebWolf · 18.02.2010

Moj kod je skoro istovetan kao Yoyov. Ocigledno svi pravimo razliku u tome, da li racunamo prvu banderu ili da li udarac u 10 automatski racunamo kao ulaz u kafanu (sto sam ja radio) ili ako je 10. bandera 10. udarac onda prelazi u sleep na ulici...

Kod mi je trenutno u netbooku, pa ne mogu da ga ubacim (dodacu ako ne zaboravim), ali procenat ovih u luci, u kafani i na ulici mi je gotovo istovetan kao vasi. Gde je greska?

yooyo · 18.02.2010

Ajde da ne lomimo glavu i da ako neko ima arhivu casopisa Racunari nadje originalni text zadatka.

U medjuvremenu, jel moze jedno pitanje vezano za perpoznavanje. Ima veze sa motion capturing-om.

Na glumcu se nalazi 50 markera. Opticki sistem detektuje te markere i racuna njihove 3d pozicije. Glumac izvodi jednostavnu vezbu gde pomera, ruke, noge, glavu, napravi korak napred i korak nazad. Rezultat je snimak koji se sastoji od N frejmova, i u svakom frejmu ima 50 markera. Mozda je bolje reci da postoji 50 kanala gde svaki kanal ima N frejmova. Putanja markera u kanalu nije kontinualna jer opticki sistem nezna kako da razvrsta markere kada im odredi 3 poziciju pa ih slaze po kanalima na meni nepoznat nacin.

Kanal1: AA AAAAB ABA...
Kanal2: BCCCBB CCBBCCCB...
Kanal3: CDDA DDACCDDAC...
Kanal4: D BDDDBBDD BBDD...
...

A, B C i D su markeri, tj njihove 3d koordinate u vremenu (po frejmovima). Prazna polja su podaci koji nedostaju.

Potom operater manuelno identifikuje prvi frejm (tj poredja markere po nekom redosledu, glava_levo_napred, glava_desno_napred, glava_levo_pozadi, glava_desno_pozadi, vrat, grudi1, grudi2, ... ) i potom koristeci neki tool otprati trajektorije u svim frejmovima. Sada imamo sredjen snimak. Tool nije idealan te se operater mora angazovati malo vise da bi obradio ceo snimak.

Zatim glumac odigra svoju ulogu i to se snimi. Sistem naravno i dalje nema pojma koji je marker na kom mestu.

Problemi koji se javljaju su:
- markeri mogu da nestanu u nekom frejmu ili cak u vise uzastopnih frejmova
- veze izmedju markera nisu konstantne vec se rastezu i skupljaju. Najstabilnije veze su izmedju 5 markera na glavi.
- markeri imaju mali jitter (noise) tako da ako snimate marker koji miruje snimak ipak pokazuje kako poskakuje za neki delic milimetra.
- u snimku moze ucestvovati i vise glumaca
- akcija se izvodi u prostoru pokrivenom kamerama. Glumac moze da izadje i ponovo udje u obelezeni prostor. U snimku dok glumac nije u polju nema podataka.

Da li mozete da smislite algoritam koji bi na osnovu obradjenog prvog snimka izgradio "znanje" kojim bi identifikovao glumca u drugim snimcima i automatski obradio ostale snimke. Uslov je da algoritam nemora da obradi sve podatke, ali da ono sto obradi mora biti 100% tacno.

Ja sam napravio nekoliko resenja ovog problema, i sva resenja imaju neke prednosti i neke mane. Zanima me neka out-of-box ideja osobe koja nema puno dodira sa ovom tehnologijom a opet mozda primeti neku slicnost sa nekim drugim problemom gde se primenjuju drugacija resenja.

Koga zanimaju test snimci neka se javi.. okacicu ih negde.

Bahati [SiD] · 18.02.2010

WebWolf je napisao(la):
Gde je greska?

u tome sto uopste pravis simulaciju kada postoji egzaktno resenje.

simulacije su super za gadno komplikovane stvari, ali kad moze da se prebroji skup mogucih dogadjaja i znaju se njihove verovatnoce nema potrebe za tim. em je sporo, em je neprecizno... detalji teksta zadatka tu nista ne menjaju!

Bahati [SiD] · 18.02.2010

yooyo je napisao(la):
Da li mozete da smislite algoritam koji bi na osnovu obradjenog prvog snimka izgradio "znanje" kojim bi identifikovao glumca u drugim snimcima i automatski obradio ostale snimke. Uslov je da algoritam nemora da obradi sve podatke, ali da ono sto obradi mora biti 100% tacno.

kako mislis identifikovao? u smislu prepoznao da je glumac X, a ne glumac Y ili prepoznao markere na njemu? sta je ulaz u algo, a sta izlaz?

yooyo · 18.02.2010

Treba prepoznati markere na glumcu.
Ulaz je snimak sa neidentifikovanim markerima (RUN, WALK, JUMP, ...), izlaz je snimak sa identifikovanim markerima (koliko je god to moguce), parametar za rad je unapred pripremljeni snimak sa identifikovanim markerima (nazovimo ga ROM) jednog ili vise glumaca. Za pocetak neka bude samo jedan glumac.

Zato unpred pripremljeni obradjeni snimak (ROM)? Zato sto se odnosi izmedju markera menjaju u zanisnosti od pokreta koji glumac izvodi i zato sto je ROM snimak zgodan za analizu odnosa markera.

Bahati [SiD] · 18.02.2010

da jos malo pojasnim foru sa grafom, ako nekog zanima.

gradic izgleda ovako kada se predstavi grafom:

0<-1<->2<->3<->4<->5<->6<->7<->8<->9<->10->11

brojevi predstavljaju cvorove grafa, strelice predstavljaju ivice (veze izmedju cvorova).

cvor 0 je luka, cvor 11 je kafana. oni su jedini koji nemaju povratnu vezu - kada jednom upadnes u njih nema natrag.
cvorovi 1 do 10 su bandere. od svake bandere se moze doci do obe susedne.

skup mogucih putanja po grafu je konacan zato sto se zavrsava na jedan od tri nacina. ili upadnes u luku, ili upadnes u kafanu ili se pomeris 10 puta. nesto od ovoga mora da se desi! ne mozes da odes od bandere 5 do 4 i stanes, ne mozes da se pomeris vise od 10 puta, itd...

onda lepo krenes od bandere 7 i zapisujes sve moguce putanje koje si mogao da napravis dok se pomeranje ne zavrsi. i kada ih sve zapises to je skup mogucih dogadjaja. ne postoji ni jedan drugi nacin na koji si mogao da se pomeras po grafu. neki od dogadjaja znace da si upao u luku, neki da si usao u kafanu, neki da si zaspao. cetvrto ne postoji.

e sad ide ono sto je meni prvo promaklo: nisu svi dogadjaji jednako verovatni.
npr:
K (05) : 07 08 09 10 11
K (07) : 07 06 07 08 09 10 11

u oba slucaja si upao u kafanu, ali u prvom u pet koraka, u drugom u sedam. sto se verovatnoce tice to izgleda ovako:

za K (05):

verovatnoca da iz 07 odes do 08 je 50%. isto vazi i za 08->09. ali to znaci da su ti sanse 50%*50% = 25% da napravis put 07->08->09, jer si u medjuvremenu mogao da skrenes! moglo je da ti se desi da ides 07->08->07 i onda to ne bi bilo to. za 09->10 mnozis sa jos 50%, i jos jednom za 10->11
ukupno si mnozio cetiri puta, tj. jedan manje nego sto si napravio koraka. to mu izadje na 50%^4 = 6,25%

za K (07) izadje 50%^6 = 1,5625%

onda saberes sve verovatnoce za grupe dogadjaja koji te zanimaju: posebno sve verovatnoce za kafane, upadanje u luku, spavanje. ukupno, naravno, mora biti 100%

i to je to! matematicki egzaktno resenje koje tacno kaze koje su verovatnoce za odredjenu sudbinu jednog mornara. posle samo izmnozis sa brojem mornara i kaznama i dobijes ono sto se trazi.

ps. sa drvetom je manje vise ista stvar. razlika je u tome sto se cvorovi ponavljaju, umesto da se prave povratne veze.

Kod:

         7
     /      \
    6        8
   / \      /  \
  5   7     7   9
 /\   /\   /\   /\
4  6 6  8 6  8 8  10
................../\
.................9 11
................ /\
................itd

i ovde brojis ono sto te zanima, 0 i 11, a dubina drveta (broj nivoa) predstavlja broj koraka. gore je nacrtano cetiri nivoa i dva cvora iz petog. u njemu se prvi put pojavljuje kafana i to je ona pominjana K (05) putanja. cvorovi koji predstavljaju luku ili kafanu nemaju decu, to je kraj putanje.
sve sto u poslednjem nivou nije 0 ili 11 predstavlja spavanje. ali da se ne bi smarao, lepo izbrojis sve 0 i 11 u drvetu, sracunas verovatnoce za luku i kafanu (na isti nacin kao za graf) i oduzmes ih od 100%. to je verovatnoca za spavanje.

Bahati [SiD] · 18.02.2010

yooyo je napisao(la):
Treba prepoznati markere na glumcu.

ok, valjda sam razumeo...

ja bi isao na neku heuristicku varijantu. recimo da operater, kad dobije hrpu markera, krene od glave i pravi coveka. zna gde je glava i zna kako izgleda covek.

algoritam treba da zna za neku referentnu tacku i da uklapa nekakav model. koji je ustvari ta povratna sprega, ili "znanje". model je, naravno, rezultat operaterovog pocetnog truda.

e sad, predpostavljam da su mesta za markere birana sa drugim prioritetima, pa na osnovu njih nije bas lako odrediti tu referentnu tacku i eventualno orijentaciju glumca, sto cenim da bi dosta ubrzalo stvari...

uglavnom, heuristika, povratna sprega, model. kljucne reci!

drfedja · 18.02.2010

Dakle, ako su nam dati markeri, oni imaju neke svoje koordinate. Algoritam bi trebalo da prepoznaje medjusobne odnose izmedju tih markera kada dolazi do transformacija matrice (kada se glumac pomera, itd....).

Konkretno u afinoj geometriji, afine transformacije cuvaju:

(a) kolinearnost tačaka,
(b) konkurentnost pravaca,
(c) paralelnost pravaca,
(d) odnos dužina na pravcu,
(e) odnos površina poligona.

Algoritam bi na osnovu prvobitne slike trebalo da pamti ovakve stvari, za svakog glumca. Zbog jitter-a bi trebalo odrediti neku epsilon okolinu, t.j. dozvoljeno odstupanje od zadatih vrednosti.
Algoritam vraca vrednost o prepoznatoj osobi ako su ovih pet osobina "upale" u dati izbor.

marko_n · 18.02.2010

Bahati [SiD] je napisao(la):
da jos malo pojasnim foru sa grafom, ako nekog zanima.

Mene je zanimalo, hvala.

Što se tiče drugog problema koji je yooyo postavio, nemam predstavu kako bih to rešio.

Nisam imao iskustva sa sličnim problemima, ali ovako laički, kako to mali Perica zamišlja, prva asocijacija su mi neuronske mreže, tako da bih krenuo u tom smeru. Uzgred da pitam, da li neko možda ima neku kvalitetnu literaturu na tu temu (ANN)?

Bahati [SiD] · 18.02.2010

btw i drvo je graf, da se neko ne zbuni.

posto kod nas informatiku uglavnom predaju matematicari, kada stignete do objektnog programiranja i grafova niko vam nece reci da instance objekata u vasem programu cine cvorove grafa, tj. da svaki pointer/referenca koju napravite predstavlja usmerenu ivicu u tom grafu. vas program je graf!

o finim detaljima, kao npr. da su cvor i ivica medjusobno zamenljivi termini, tj. da mozes da biras da li "svet" posmatras kao skup veza, pa gledas sta povezuju, ili skup objekata, pa gledas kako su povezani takodje tesko da cete cuti...

to je bar moje iskustvo i nekolicine ljudi s kojima sam pricao. siguran sam da negde postoje izuzeci, ali ne mogu se oteti utisku da kod nas radi ta "ruska" skola: uciti, uciti i samo uciti. program = graf?! ko ce o tome da razmislja posle analize 3...

marko_n · 18.02.2010

Jedan lak problem (za ljubitelje grafova

).

Imamo gradić koji leži na reci i ima dve ade i 7 mostova, kao na slici. Da li je moguće da osoba prošeta gradom i da pri tom pređe preko svih 7 mostova, ali da ni preko jednog mosta ne pređe 2 puta? Početna i odredišna tačka šetnje su proizvoljne.

drfedja · 19.02.2010

Bahati [SiD] je napisao(la):
btw i drvo je graf, da se neko ne zbuni.

posto kod nas informatiku uglavnom predaju matematicari, kada stignete do objektnog programiranja i grafova niko vam nece reci da instance objekata u vasem programu cine cvorove grafa, tj. da svaki pointer/referenca koju napravite predstavlja usmerenu ivicu u tom grafu. vas program je graf!

Svasta se moze opisati grafom, ali u opstem slucaju gde god imas neku referencu i pokazivač, to možeš predstaviti grafom. Međutim, pitanje je šta ćeš raditi sa tim grafom.

o finim detaljima, kao npr. da su cvor i ivica medjusobno zamenljivi termini, tj. da mozes da biras da li "svet" posmatras kao skup veza, pa gledas sta povezuju, ili skup objekata, pa gledas kako su povezani takodje tesko da cete cuti...

To je već pitanje interpretacije grafa. Na studijama Informatike na PMF-u postoji predmet koji se zove Programske paradigme. Tu se diskutuje o različitim pristupima ovoj problematici. A što se tiče grafova i algoritama baziranim na radu sa njima, to je možda glavna stvar na celim studijama. Posle 4-5 godina ispiranja mozga sa grafovima, sve živo počneš da posmatraš tako. :d

to je bar moje iskustvo i nekolicine ljudi s kojima sam pricao. siguran sam da negde postoje izuzeci, ali ne mogu se oteti utisku da kod nas radi ta "ruska" skola: uciti, uciti i samo uciti. program = graf?! ko ce o tome da razmislja posle analize 3...

Istina, uglavnom ljudi sa faxa izađu relativno nespremni za posao. Mada sve zavisi od toga koliko široko gledaš na stvari.

drfedja · 19.02.2010

marko_n je napisao(la):
Jedan lak problem (za ljubitelje grafova ).

Imamo gradić koji leži na reci i ima dve ade i 7 mostova, kao na slici. Da li je moguće da osoba prošeta gradom i da pri tom pređe preko svih 7 mostova, ali da ni preko jednog mosta ne pređe 2 puta? Početna i odredišna tačka šetnje su proizvoljne.

To je problem Keningbenskih mostova, iliiti problem 7 mostova.
Graf 7 mostova ima 4 neparna cvora, pa ga ne mozemo nacrtati jednim potezom.Dakle, setac koji zeli da predje preko svih 7 keningsberskih mostova prelazeci preko svakog mosta samo po jedanput, nece moci to da ostvari.

Graf se moze nacrtati jednim potezom samo ako nema nijedan neparan cvor ili ima dva neparna cvora - Ojlerov graf.

Bahati [SiD] · 19.02.2010

i evo poslednja stvar u vezi problema sa mornarima, necu vise da smaram.

cela ona prica o grafovima je tu da nam olaksa da modelujemo stanje na terenu, tj. da sve to slozimo u glavi. graf bi posebno bio od koristi da, recimo, udarac u banderu proizvodi vise od dva moguca efekta, sa razlicitim verovatnocama. praktican algoritam za resavanje ovog konkretnog problema moze da apstrahuje graf i svodi se na prostu rekurzivnu funkciju od nekoliko redova:

Kod:

void rekurzija(int sudar, int bandera, double %luka, double %kafana, double %spavanje) {
	if(bandera == 0) luka += Math::Pow(0.5F,sudar-1);
	else if(bandera == 11) kafana += Math::Pow(0.5F,sudar-1);
	else if(sudar == 10) spavanje += Math::Pow(0.5F,9);
	else
	{
		rekurzija(sudar+1, bandera-1, luka, kafana, spavanje);
		rekurzija(sudar+1, bandera+1, luka, kafana, spavanje);
	}
}

poziv funkcije i ispis:

Kod:

double luka = 0, kafana = 0, spavanje = 0;
rekurzija(1,7,luka,kafana,spavanje);
PrintResults(luka,kafana,spavanje);

ovo iznad je ceo program, bez funkcije za ispis koja je dosadna.

uporedite to sa simulacijom po jednostavnosti, brzini i tacnosti i sve ce sa samo kasti. jedino je nezgodno sto je rekurzija, pa mora da se pazi na kapacitet return stack-a. ali ako radi, radi perfektno.

marko_n · 19.02.2010

drfedja je napisao(la):
To je problem Keningbenskih mostova, iliiti problem 7 mostova.
Graf 7 mostova ima 4 neparna cvora, pa ga ne mozemo nacrtati jednim potezom.Dakle, setac koji zeli da predje preko svih 7 keningsberskih mostova prelazeci preko svakog mosta samo po jedanput, nece moci to da ostvari.

Graf se moze nacrtati jednim potezom samo ako nema nijedan neparan cvor ili ima dva neparna cvora - Ojlerov graf.

Da, ko je pazio na času, ovo mu je dobro poznato.

Inače problem koji je Ojler rešio 1735. godine, ako nekoga zanima više: Seven Bridges of Königsberg.

Bahati, svaka čast na rekurzivnom rešenju.

arty: Još jedan lep problem za rekurziju, ko voli da lomi glavu, su Hanojske kule. Doduše, problem se može rešiti na više različitih načina.

Da li neko od vas koristi ili možda uči funkcionalnu paradigmu? Ne mislim na jezike u kojima se samo može tako programirati, nego baš na jezike koji su primarno okrenuti toj paradigmi, kao što su Haskell, OCaml, Scheme, F#, Clojure, Scala...? (bilo bi zanimljivo da se otvori neka tema, u čemu radite, šta učite, šta predviđate da će biti korisno znati za 5, 10, 15 godina...)

drfedja · 19.02.2010

marko_n je napisao(la):
Hanojske kule. Doduše, problem se može rešiti na više različitih načina.

Moze, ali je rekurzivni prilicno smislen nacin.
Prebacis n-1 diskova gledano odozgo na pomocni stap i onda n-ti prebacis na destination stap, a zatim n-1 rekurzivno stavis na destination i dobio si sta se trazilo. :d Prilicno simplifikovano u poredjenju sa iterativnom varijantom.

Srednjoškolski zadaci

Slavan

Čuven

Čuven

Čuven

Čuven

Čuven

Slavan

Čuven

Slavan

Čuven

Slavan

Slavan

Čuven

Čuven

Čuven

Čuven

Čuven

Čuven

Čuven

Slavan

Čuven

Slavan

Prilozi

Čuven

Čuven

Čuven

Slavan

Čuven