•filipb
|
|
« : Iulie 07, 2006, 11:45:22 » |
|
Aici puteţi discuta despre problema Senat.
|
|
|
Memorat
|
|
|
|
•pauldb
|
|
« Răspunde #1 : Iulie 11, 2006, 21:28:06 » |
|
Anumite teste/Testele au spatii la sfarsitul liniilor?
|
|
|
Memorat
|
Am zis
|
|
|
•filipb
|
|
« Răspunde #2 : Iulie 12, 2006, 12:30:18 » |
|
DA.
|
|
|
Memorat
|
|
|
|
•marin
Strain
Karma: -1
Deconectat
Mesaje: 22
|
|
« Răspunde #3 : Februarie 28, 2008, 22:15:03 » |
|
Un hint ... ?
|
|
|
Memorat
|
|
|
|
•pauldb
|
|
« Răspunde #4 : Februarie 28, 2008, 22:37:21 » |
|
Cuplaj.
|
|
|
Memorat
|
Am zis
|
|
|
•gabor_oliviu1991
|
|
« Răspunde #5 : Mai 30, 2008, 08:08:11 » |
|
ce e ala un cuplaj?... problema asta se poate face avand cunostinte de clasa a 10a?
|
|
|
Memorat
|
|
|
|
|
•Pepelea_Flaviu
Client obisnuit
Karma: 30
Deconectat
Mesaje: 98
|
|
« Răspunde #7 : Ianuarie 10, 2009, 14:06:10 » |
|
se poate cumva ca o comisie sa un contina nici un candidat? LE: am gasit, ar trebui precizat totusi ca in fisierul de intrare la sfarsitul liniei se pot afla si spatii... ia omu 40 de pcte din cauza citirii
|
|
« Ultima modificare: Ianuarie 10, 2009, 14:24:04 de către Flaviu Pepelea »
|
Memorat
|
|
|
|
•gabor_oliviu1991
|
|
« Răspunde #8 : Martie 10, 2009, 19:02:03 » |
|
cat va da pentru: 22 37 6 31 22 35 36 22 35 32 3 11 26 17 4 30 10 31 5 23 24 14 28 13 7 4 16 32 21 12 24 31 25 13 11 29 27 5 1 3 18 36 2 34 9 21 35 30 10 28 8 10 6 5 30 1 36 14 9 7 35 32 12 27 3 11 25 24 14 10 4 34 5 27 7 22 28 6 33 9 35 25 24 13 20 27 10 22 11 33 2 1 21 26 18 5 3 35 31 32 36 23 28 13 25 6 36 16 32 33 21 7 17 10 1 33 30 23 14 17 12 28 26 16 20 3 36 7 4 29 25 10 5 20 5 9 13 7 35 36 4 28 18 1 23 12 33 6 30 26 8 21 3 2 34 10 20 11 34 22 4 36 26 19 29 12 10 21 17 25 2 16 10 5 23 35 29 32 8 24 14 11 9 17 6 1 15 4 2 7 28 30 36 33 28 29 18 35 34 33 30 21 2 14 31 9 11 6 8 11 3 33 29 5 27 16 14 30 4 18 2 18 3 5 27 21 19 10 25 1 12 30 34 8 13 23 32 31 26 24 20 29 22 29 8 13 31 3 25 6 7 10 19 31 1 28 21 11 34 3 29 13 23 1 16 20 7 10 5 17 24 19 35 15 14 30 32 16 23 26 31 12 28 15 3 6 9 24 29 14 22 24 1 23 25 3 29 36 4 14 6 12 19 30 15 16 28 9 21 34 13 35
|
|
|
Memorat
|
|
|
|
•alexandru92
|
|
« Răspunde #9 : Martie 10, 2009, 20:15:35 » |
|
.............cred ca 0 dar nu bag mana in foc
|
|
|
Memorat
|
|
|
|
•gabor_oliviu1991
|
|
« Răspunde #10 : Martie 10, 2009, 20:39:54 » |
|
si mie imi dadea 0. dar am modificat ceva, si primesc: 6 22 3 4 1 5 7 2 10 12 8 17 9 14 11 16 13 25 19 15 23 21 ceea ce cred ca e corect. dar nu inteleg ceva. fac cuplajul, iar daka in vectorul in care imi retin nodul cu care cuplej un nod i, gasesc 0, adica nu l-am cuplat cu nimic, afisez doar "0" in fisierul de iesire, altfel afisez cuplajul. cu o astfel de abordare primesc 70 de puncte. iar daca afisez cuplajul fara a verifica daca am noduri pe care nu le-am putut cupla iau 80 de puncte. singurul test care nu are solutie (trebuie afisat doar 0) este testul 10, pe care il prind in ambele cazuri.
|
|
|
Memorat
|
|
|
|
•alexandru92
|
|
« Răspunde #11 : Martie 11, 2009, 07:03:05 » |
|
pt a te convinge care solutie e corecta, fa un back........ m-am obisnuit daca n-am alte idei de rezolvare sau doar sa verfic ca da rezultatul corect ........fac un back(in cazurile posibile) :d
|
|
|
Memorat
|
|
|
|
•gabor_oliviu1991
|
|
« Răspunde #12 : Martie 11, 2009, 10:13:25 » |
|
cazurile de pana in maxim 7,8 camere le pot verifica si manual, dar alea de exemplu cel care l-am postat mai sus, are 22 de camere, ceea ce inseamna ca backul meu o sa ruleze o groaza de timp. totusi nu inteleg ce nu prind alea doua teste.inca nu am intalnit test care sa nu mearga. tu cum ai facut?
|
|
|
Memorat
|
|
|
|
•alexandru92
|
|
« Răspunde #13 : Martie 13, 2009, 14:25:53 » |
|
initial .........m-am gandit la back dar dupa ce am vazut limitile ....... verific daca graful e bipartit , in caz afirmativ afisez solutia altfel 0
|
|
|
Memorat
|
|
|
|
•gabor_oliviu1991
|
|
« Răspunde #14 : Martie 13, 2009, 15:00:51 » |
|
Hmmm... interesant. Eu citeam prima oara M si dupa N, si totusi scoteam 80 de puncte cu o astfel de citire. Mi se pare ca la o astfel de greseala programul sa nu scoata niciun punct, nicidecum 80. Si in testul postat mai sus de mine, inversati 22 cu 37, raspunsul e bun oricum.
|
|
|
Memorat
|
|
|
|
•alexandru92
|
|
« Răspunde #15 : Martie 13, 2009, 15:09:11 » |
|
separe ca renunt..la ideaa cu bipartit ......... desi nu prea inteleg de ce n-ar merge ?? ........hm vreo idee ca eu am ramas fara
|
|
|
Memorat
|
|
|
|
•gabor_oliviu1991
|
|
« Răspunde #16 : Martie 13, 2009, 15:12:21 » |
|
Descrie putin ideea. ceea ce ai zis mai sus e prea vag. Intradevar, problema se face cu ajutorul cuplajului (care se aplica unui graf bipartit).
|
|
|
Memorat
|
|
|
|
•alexandru92
|
|
« Răspunde #17 : Martie 13, 2009, 15:20:11 » |
|
pai eu am .........citit graful si am creat un fel de matrice de adicanta adica........ is pe linia i si citestc numerele j,k,l,m,n (ci j,k,l,m,n!=i) si pun a[ i ][j]=1,a[ i ][k]=1.....a[ i ][n]=1; Si apoi pur si simplu incerc sa impart nodurile grafurilor in 2 multimi........daca am reusit afisez o multime altfel afisez 0
|
|
|
Memorat
|
|
|
|
•pauldb
|
|
« Răspunde #18 : Martie 13, 2009, 15:46:24 » |
|
Nu mi se pare corect ce incerci sa faci. Poate ar trebui sa citesti mai mult despre cuplaj.
|
|
|
Memorat
|
Am zis
|
|
|
•alexandru92
|
|
« Răspunde #19 : Martie 13, 2009, 18:47:36 » |
|
Stiu ca poate cer ceva imposibil, dar stie cineva un articol sau ceva de genu care exmplica cuplajul intr-un graf pe limba orcui si o implmentare a problemei cuplaj maxim in graf bipartit, explicat va rog [later] Am modificat, mai bine?
|
|
« Ultima modificare: Martie 14, 2009, 14:13:23 de către alexandru »
|
Memorat
|
|
|
|
•wefgef
|
|
« Răspunde #20 : Martie 13, 2009, 21:18:09 » |
|
@Alexandru: Un sfat prietenesc: ar fi o idee buna daca ai folosi caracterul "." doar o singura data. Ma dor ochii atunci cand iti citesc posturile, si nu cred ca sunt singurul. Ar fi un pas inainte daca ai scrie corect, in limba romana.
|
|
|
Memorat
|
omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
|
|
|
•freak93
|
|
« Răspunde #21 : Iulie 15, 2009, 16:21:59 » |
|
Imi poate spune cineva cu ce gresesc la acest algoritm. Pun un nod sursa->0,senatorii ii pun nodurile in 1->n, comisiile in nodurile de la n+1->n+m si un nod destinatie in in n+m+1. Daca un senator x faca parte dintr-o comisie y pun costul muchiei C[ x ][ y ]=1. Pe deasupra mai pun si costul muchiilor de la sursa la fiecare senator ca fiind 1 si costul muchiilor de la comisie la destinatie ca fiind tot 1. Fac flux maxim de la sursa la destinatie si verific daca este egal cu m(in caz afirmativ caut pentru fiecare comisie cu ce senator e unita,altfel afisez 0) Algoritmul si ideea mi se par perfecte si totusi nu iau decat 10 puncte WA pe testele 1-8 si 10(corect pe 9). Putin ajutor va rog? [Later Edit]Am luat 100. Era de la citire
|
|
|
Memorat
|
|
|
|
•DraStiK
|
|
« Răspunde #22 : Februarie 22, 2010, 11:18:54 » |
|
Problema asta da mari bătăi de cap. Iau 90p, și din câte am citit din posturile anterioare, testul 10 (cel care il pic eu) e cel fără soluție. Practic când nu este soluție, cuplajul maxim e mai mic decât M. Nu am dreptate? Va rog puțin ajutor
|
|
|
Memorat
|
|
|
|
•Florian
|
|
« Răspunde #23 : Februarie 22, 2010, 12:14:29 » |
|
Nu. Daca exista vreun nod necuplat ( dreapta[ i ] == 0) inseamna ca nu exista solutie. Altfel, exista.
|
|
|
Memorat
|
|
|
|
•DraStiK
|
|
« Răspunde #24 : Februarie 22, 2010, 12:21:05 » |
|
Exact asta verific. Uite mai exact: for (i=1; i<=m; ++i) if (r[i]==0) { printf ("0"); return ; } for (i=1; i<=m; ++i) printf ("%d\n",r[i]);
Am verificat sa fac bine cuplaju de nenumărate ori. Chiar nu știu ce ar putea fi.
|
|
|
Memorat
|
|
|
|
|