Imprimă pagina - 149 Soldati

Titlul: 149 Soldati
Scris de: Mircea Pasoi din Decembrie 12, 2005, 00:18:00

Aici puteţi discuta despre problema Soldati (http://infoarena.ro/problema/soldati).

Titlul: Raspuns: 149 Soldati
Scris de: Vlad Berteanu din Iulie 25, 2006, 16:49:56

:D N-am nici o idee... Cine are o solutie buna as vrea sa mi dea un hint ceva... :aha:

Titlul: Re: 149 Soldati
Scris de: Tiberiu-Lucian Florea din Iulie 25, 2006, 21:27:45

Considera doar sagetile care arata intr-o parte (dreapta sa zicem), si considera ca in locul celorlaltor sageti ai casute goale. La fiecare pas, fiecare sageata merge la dreapta daca e gol locul. Poti sa iti faci o dinamica care sa iti spuna cand ajunge cea mai din stanga sageata ?

Titlul: Raspuns: 149 Soldati
Scris de: Toma Radu din Octombrie 02, 2006, 20:53:49

Mi-ar putea zice si mie cineva cum ar merge dinamica aceea (cand ajunge cea mai din stanga sageata)?

Titlul: Raspuns: 149 Soldati
Scris de: Toma Radu din Octombrie 22, 2006, 18:25:55

cum merge dinamica la problema asta?

Titlul: Raspuns: 149 Soldati
Scris de: Marius Stroe din Octombrie 22, 2006, 21:56:36

Solutia e in O(N). Vezi cat timp sta pe loc o sageata.

Titlul: Raspuns: 149 Soldati
Scris de: Toma Radu din Octombrie 23, 2006, 18:39:35

Mi-a iesit pana la urma :)

Titlul: Răspuns: 149 Soldati
Scris de: Andrei-Bogdan Antonescu din Martie 11, 2008, 14:05:19

Are cineva vreo idee la ce gresesc de nu pot sa iau mai mult de 20 pt ](*,) ] (*,)
Am incercat tot felul de teste si imi da bine dar totusi iau 8 WA.

Eu am parcusr vectorul si dupa ce gaseam o sageata orientata dreapta ( care le-am marcat cu 1)
numaram cate sageti orientate stanga ( marcate cu 0) si adaugam pentru fiecare grupa de unu cu mai multe elemente adaugam numarul de 1 din ea -1. daca intalneam din nou un 0.
In for mergeam pana la l (lungimea sirului )

Cod:

scanf("%s", &v);
		l=strlen(v);
		v[l]=1; v[l+1]=1;
		for(j=0;j<l;++j)
		{	if(v[j]==62) v[j]=1;
			if(v[j]==60) v[j]=0;}
		rez=0;
		g=0;
		nr=0;
		for(j=0;j<l;++j)
		{
			if(v[j])
				g=1;
			if(g)
			{
				if(v[j] && v[j-1])
					++nr;
				if(!v[j])
					{++rez; rez+=nr; nr=0;}
			}		
		}
		printf("%d\n",rez);

Editat de admin: Pentru a scrie cod, trebuie sa incadrezi sursa pe care o postezi intre cele doua taguri :)

Titlul: Răspuns: 149 Soldati
Scris de: Casu-Pop Bogdan din Martie 11, 2008, 18:02:16

dar pe care teste ai luat ?
k si eu am faut cam la fel si am luat pe 3 si 4 restu WA

Titlul: Răspuns: 149 Soldati
Scris de: Andrei-Bogdan Antonescu din Martie 11, 2008, 22:02:57

da tot pe 3 si 4 OK si in rest WA
Nustu ce am gresit imi poate spune cineva .
multumesc

Titlul: Răspuns: 149 Soldati
Scris de: Serban Andrei Stan din Martie 13, 2008, 18:20:06

Daca faci cu programare dinamica, si o codezi corect, ar trebui sa nu ai probleme.

Titlul: Răspuns: 149 Soldati
Scris de: Ionescu Robert Marius din Martie 13, 2008, 19:51:11

cat va da pentru
1

Cod:

<><><>>>>>><<<<>>><><><><<<<<<<>>><<>><><>><>>><<<>>>>>>>>>>>>>>>>>>><<<><><>>>>>>>><>>><

mie imi da 71 ..voua cat va da?

Editat de moderator: Folositi tag-ul code pentru teste (mai ales pentru cele lungi/late)!

Titlul: Răspuns: 149 Soldati
Scris de: Bogdan-Cristian Tataroiu din Martie 13, 2008, 20:01:23

Titlul: Răspuns: 149 Soldati
Scris de: Antoche Ioana Alexandra din Septembrie 01, 2009, 19:20:31

Daca am o secventa de '<<<<<...'care incepe pe o pozitie pozf (pozf!=0) atunci primul'<' din secventa nu se va mai putea muta la stanga dupa pozf-nr+1 pasi (unde nr reprezinta numatul de '<' pana pe pozitia pozf inclusiv). Celelalte ajung la o diferenta de un timp fiecare.
Deci daca retin ultima secventa de '<<..' din sir, nu pot sa calculez dupa formula pozf-(nr-(poz-pozf))+1+poz-pozf?
poz=pozitia ultimului element din ultima secventa de '<<..'
de exemplu daca am sirul:>><<< , poz=4, pozf=2; nr=3
Iau Wa pe 9 teste, dar pe toate exeplele mele da bine (inclusiv pe cel de pe forum) ](*,).
Are cineva un contra-exemplu? Va rog!
Multumesc anticipat!

Titlul: Răspuns: 149 Soldati
Scris de: Bogdan-Cristian Tataroiu din Martie 21, 2010, 17:43:50

Testele de la această problemă conţineau caractere invalide la sfârşitul testelor. Problema a fost reevaluată, însă nu ar trebui să se schimbe niciun scor.

Titlul: Răspuns: 149 Soldati
Scris de: Simoiu Robert din Aprilie 02, 2010, 15:51:00

Buna, daca fac sper exemplu un for, daca dau de >< ii schimb in <> si nr++, intra in timp? Merci .

Titlul: Răspuns: 149 Soldati
Scris de: Cosmin-Mihai Tutunaru din Aprilie 02, 2010, 15:54:35

Nu, deoarece complexitatea ta este pătratică pe cazul cel mai nasol.

Titlul: Răspuns: 149 Soldati
Scris de: Simoiu Robert din Aprilie 02, 2010, 17:43:47

Se poate face altcumva decat cu PD ?

Titlul: Răspuns: 149 Soldati
Scris de: Petru Trimbitas din Noiembrie 28, 2011, 13:27:02

http://acm.timus.ru/problem.aspx?space=1&num=1135

infoarena

infoarena - concursuri, probleme, evaluator, articole => Arhiva de probleme => Subiect creat de: Mircea Pasoi din Decembrie 12, 2005, 00:18:00