infoarena

infoarena - concursuri, probleme, evaluator, articole => Arhiva de probleme => Subiect creat de: Filip Cristian Buruiana din Iulie 07, 2006, 11:45:22



Titlul: 254 Senat
Scris de: Filip Cristian Buruiana din Iulie 07, 2006, 11:45:22
Aici puteţi discuta despre problema Senat (http://infoarena.ro/problema/senat).


Titlul: Raspuns: 254 Senat
Scris de: Paul-Dan Baltescu din Iulie 11, 2006, 21:28:06
Anumite teste/Testele au spatii la sfarsitul liniilor?


Titlul: Raspuns: 254 Senat
Scris de: Filip Cristian Buruiana din Iulie 12, 2006, 12:30:18
DA.


Titlul: Răspuns: 254 Senat
Scris de: Mari n din Februarie 28, 2008, 22:15:03
Un hint ... ?


Titlul: Răspuns: 254 Senat
Scris de: Paul-Dan Baltescu din Februarie 28, 2008, 22:37:21
Cuplaj.


Titlul: Răspuns: 254 Senat
Scris de: gaboru corupt din Mai 30, 2008, 08:08:11
ce e ala un cuplaj?... problema asta se poate face avand cunostinte de clasa a 10a?


Titlul: Răspuns: 254 Senat
Scris de: Alina Ene din Mai 30, 2008, 08:59:04
Matching http://en.wikipedia.org/wiki/Matching (http://en.wikipedia.org/wiki/Matching)
Probabil ca nu (algoritmi pe grafuri se fac dintr-a 11a nu?).


Titlul: Răspuns: 254 Senat
Scris de: Flaviu Pepelea din 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...:D
ia omu 40 de pcte din cauza citirii :weightlift:


Titlul: Răspuns: 254 Senat
Scris de: gaboru corupt din Martie 10, 2009, 19:02:03
cat va da pentru: :-s

Cod:
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


Titlul: Răspuns: 254 Senat
Scris de: alexandru din Martie 10, 2009, 20:15:35
.............cred  ca  0  dar  nu bag  mana in foc :P


Titlul: Răspuns: 254 Senat
Scris de: gaboru corupt din Martie 10, 2009, 20:39:54
si mie imi dadea 0. dar am modificat ceva, si primesc:

Cod:
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.


Titlul: Răspuns: 254 Senat
Scris de: alexandru din 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


Titlul: Răspuns: 254 Senat
Scris de: gaboru corupt din 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?


Titlul: Răspuns: 254 Senat
Scris de: alexandru din Martie 13, 2009, 14:25:53
  initial .........m-am gandit la back  dar dupa ce am vazut limitile ....... verific daca graful e bipartit :D , in caz afirmativ afisez solutia altfel 0 :)


Titlul: Răspuns: 254 Senat
Scris de: gaboru corupt din 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. :)


Titlul: Răspuns: 254 Senat
Scris de: alexandru din 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


Titlul: Răspuns: 254 Senat
Scris de: gaboru corupt din 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).


Titlul: Răspuns: 254 Senat
Scris de: alexandru din 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 :)


Titlul: Răspuns: 254 Senat
Scris de: Paul-Dan Baltescu din Martie 13, 2009, 15:46:24
Nu mi se pare corect ce incerci sa faci. Poate ar trebui sa citesti mai mult despre cuplaj (http://infoarena.ro/problema/cuplaj).


Titlul: Răspuns: 254 Senat
Scris de: alexandru din 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?


Titlul: Răspuns: 254 Senat
Scris de: Andrei Grigorean din 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.


Titlul: Răspuns: 254 Senat
Scris de: Adrian Budau din 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


Titlul: Răspuns: 254 Senat
Scris de: Dragos Oprica din 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 :)


Titlul: Răspuns: 254 Senat
Scris de: Florian Marcu din Februarie 22, 2010, 12:14:29
Nu. Daca exista vreun nod necuplat ( dreapta[ i ] == 0) inseamna ca nu exista solutie. Altfel, exista.


Titlul: Răspuns: 254 Senat
Scris de: Dragos Oprica din Februarie 22, 2010, 12:21:05
Exact asta verific. Uite mai exact:

Cod:
    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.


Titlul: Răspuns: 254 Senat
Scris de: Florian Marcu din Februarie 22, 2010, 19:54:46
Mda, am inteles eu gresit initial. Nu prea sunt cazuri particulare la problema asta. Poate nu iti declari vectorii suficienti de mari ( se mai ia si WA cateodata de la asta ), sau poate o fi citirea cu probleme ( vreu ciclu infinit sau ceva de genu' ).


Titlul: Răspuns: 254 Senat
Scris de: Dragos Oprica din Februarie 23, 2010, 12:02:06
Se pare ca problema era de la citire. Eu citeam fiecare linie cu fgets, iar la ultima linie nu exista end-line. Astfel mie nu îmi citea ultimul număr corect.
Mulțumesc de ajutor.  :D


Titlul: Răspuns: 254 Senat
Scris de: Vlad Dumitru-Popescu din Mai 09, 2016, 01:26:36
Eu m-am chinuit vreo 20 de minute cu citirea si nu mi se pare ca o citire complicata este in avantajul unei probleme, oricat de simple ar fi, asa ca am sa pun aici fragmentul de cod pentru citire cu care am luat 100 daca ajuta pe cineva.  Sper sa nu incalc nicio regula  :-'

Cod:
f >> n >> m;
   for(i = 1; i <= m; i++) {
      while(isspace(f.peek())) f.get();
      while(!f.eof() && f.peek() != '\n') {
         f >> x;
         graph[x].push_back(i);
         while(isspace(f.peek()) && f.peek() != '\n') f.get();
      }
   }



Titlul: Răspuns: 254 Senat
Scris de: Alexandru Valeanu din Mai 09, 2016, 11:08:04
Exista si o solutie putin mai simpla :
Cod:
std::string str;
int n;

getline(in, str);
std::stringstream stream(str);

while (stream >> n) {
    /*...*/
}


Titlul: Răspuns: 254 Senat
Scris de: OvidiuPita din Martie 08, 2019, 09:03:18
Editat de moderator.

Ai grija la felul in care vorbesti