infoarena

infoarena - concursuri, probleme, evaluator, articole => Arhiva de probleme => Subiect creat de: Airinei Adrian din Aprilie 06, 2008, 14:37:28


Titlul: 699 Online
Scris de: Airinei Adrian din Aprilie 06, 2008, 14:37:28
Aici puteţi discuta despre problema Online (http://infoarena.ro/problema/online).

Titlul: Răspuns: 699 Online
Scris de: Anca Dumitrache din Aprilie 07, 2008, 10:45:18
help much needed...
Am implementat un Kruskal pt determinarea costului initial apoi pt celelalte K muchii, daca nu erau deja in APM, am verificat care este muchia cu costul maxim din ciclul format, si daca era cazul, o scoteam din lista si o adaugam pe cea noua. Am incercat si pe cateva teste de-ale mele si mi-a dat bine, pur si simplu nu-mi dau seama de ce iau doar 10 puncte. Am vreo greseala in gandire sau imi scapa vreun caz? De precizat ca muchiile pe care le scot din lista nu le sterg din lista, ci le setez ca de nefolosit.

Titlul: Răspuns: 699 Online
Scris de: Bogdan-Alexandru Stoica din Aprilie 07, 2008, 15:56:17
incearca urmatorul test

Cod:
7 6
1 2 2
1 3 2
3 7 2
2 4 2
4 5 3
4 6 3
8
2 7 1
3 7 3
1 7 1
4 2 1
6 7 4
6 7 1
5 6 3
5 7 1

raspunsul ar trebui sa fie:

Cod:
14
13
13
12
11
11
9
9
7

sper sa nu fi gresit :)

Titlul: Răspuns: 699 Online
Scris de: Anca Dumitrache din Aprilie 07, 2008, 20:23:22
asa primesc si eu
off.. problema asta imi mananca nervii

Titlul: Răspuns: 699 Online
Scris de: Bogdan-Alexandru Stoica din Aprilie 08, 2008, 09:30:22
Cod:
10 10
1 3 3
1 2 3
3 5 1
3 8 1
5 8 2
5 4 1
5 6 1
5 7 1
8 9 1
8 10 1
8
2 3 4
2 3 1
3 2 1
4 5 6
5 4 1
4 5 7
8 6 3
2 10 1

Cod:
13
13
11
11
11
11
11
11
11

Cod:
10 10
1 3 4
1 2 4
3 5 1
3 8 1
5 8 2
5 4 1
5 6 1
5 7 1
8 9 1
8 10 1
7
2 3 3
1 3 4
2 5 4
2 3 1
2 3 2
6 7 1
7 3 1

Cod:
15
14
14
14
12
12
12
12

Titlul: Răspuns: 699 Online
Scris de: Anca Dumitrache din Aprilie 08, 2008, 10:33:51
tot aceleasi rezultate  :sad:
acum sunt sigura ca gresesc undeva din neatentie

Titlul: Răspuns: 699 Online
Scris de: Toma Radu din Aprilie 08, 2008, 11:09:53
Trimite-mi daca vrei un mail cu sursa sa ma uit peste ea.

Titlul: Răspuns: 699 Online
Scris de: Codrea Marcel din Octombrie 26, 2008, 19:38:06
Imi poate spune cineva ce rezultat primeste pentru testul :

Cod:
9 11
5 6 10
1 2 3
6 9 12
8 9 7
3 6 5
2 7 4
8 2 20
3 1 5
8 5 13
4 3 5
6 7 4
9
1 2 1
2 3 1
3 6 3
1 7 3
2 6 2
3 6 4
8 9 8
1 4 1
3 6 1

Va multumesc anticipat !

Titlul: Răspuns: 699 Online
Scris de: Paul-Dan Baltescu din Octombrie 27, 2008, 00:47:10
Cod:
50
48
44
43
42
41
41
41
37
36

Titlul: Răspuns: 699 Online
Scris de: MciprianM din Decembrie 09, 2008, 14:18:05
Cum putem sorta muchiile dupa cost folosind sort din stl?
Folosesc o structura de genul:
Cod:
struct muchie{
  int n1,n2,cost;
};
pentru a memora muchiile.

Titlul: Răspuns: 699 Online
Scris de: Bogdan-Cristian Tataroiu din Decembrie 09, 2008, 15:16:29
Definesti o functie de comparare:
Cod:
int cmp(muchie a, muchie b)
{
    return a.cost < b.cost;
}
pe care o dai ca parametru la sort.
Cod:
sort(v.begin(), v.end(), cmp);

Asa sortezi un vector v cu elemente de tip muchie, crescator dupa cost.

Titlul: Răspuns: 699 Online
Scris de: MciprianM din Decembrie 11, 2008, 08:07:06
ms. :ok:

Titlul: Răspuns: 699 Online
Scris de: Adrian Draghici din August 29, 2010, 13:26:38
cum fac sa gasesc ciclul format (muchiile care il compun)?
banuiesc ca e ceva cu DFS, dar chiar nu ma prind acum..

Titlul: Răspuns: 699 Online
Scris de: Paul-Dan Baltescu din August 30, 2010, 08:05:23
Nu e nevoie sa-l gasesti. Poti aplica un algoritm de APM la fiecare pas. Dupa ce determini APM-ul initial, la fiecare pas vei avea doar N muchii candidat.

Titlul: Răspuns: 699 Online
Scris de: Adrian Draghici din Septembrie 01, 2010, 11:30:53
multumesc pentru ajutor! m-am lamurit cu asta, dar acum nu reusesc sa iau deloc puncte, desi m-am verificat si eu si imi dau bine si toate testele puse pe forum. este vreo smecherie?

Titlul: Răspuns: 699 Online
Scris de: avram florin constantin din Aprilie 01, 2011, 16:44:36
Nu inteleg de ce iau decat 10 puncte!Primesc Killed by signal 11(SIGSEGV) care din cate stiu e se refera la depasirea memoriei,dar totusi tot ce declar

const int MaxN = 201;
struct muchie{
      int x,y,cost;
      };
vector<muchie> e,E;
int N,M,K,Cost,Lg,T[MaxN],rg[MaxN];
 si cateva variabile locale.Imi poate explica si mie cineva de ce tot primesc sigsegv.

Titlul: Răspuns: 699 Online
Scris de: Paul-Dan Baltescu din Aprilie 01, 2011, 22:55:23
Mai probabil primesti SIGSEGV din cauza ca depasesti limitele unui vector.


Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines