032 Lacate

[•fluffy]

Aici puteţi discuta despre problema Lacate.

[•ParrAzitU]

Cred ca sunt obosit si nu-mi dau seama, da zicetimi si mie careva dece nu e la lacate tot timpu solutia ceva de genul :
N-1 1
1
2
3
...
N-1
1

[•HeLLHeiM]

Imi puteti da un exemplu mai complex ? Din exemplul dat in problema e greu sa-mi dau seama daca am facut bine sau nu.

Multumesc.

[•HeLLHeiM]

ma, va rog frumos, un exemplu macar ...

[•filipb]

Testele nu sunt publice ( nu ai citit articolele puse mai sus de domino? )... Poate doar daca ai noroc... Succes... Poate iti dai singur seama...


  Filip b.

[•HeLLHeiM]

Ma, mie nu-mi trebuie un test oficial, ci doar un exemplu de iesire. De exemplu, ce ar trebui sa afisez pentru n = 6 ?

[•silviug]

6 e cam mare

Pentru N = 4 mie imi da:
6 3
1 2 3
1 4 5
2 4 6
3 5 6


Have fun!

Silviu

[•HeLLHeiM]

10x!

[•Cosmin]

hellheim de pe topcoder esti tu? http://www.topcoder.com/tc?module=MemberProfile&cr=15195775

[•HeLLHeiM]

dap... is si pe topcoder, dar de putina vreme (n-am participat decat la 2 concursuri). Sincer, mi se pare destul de ciudat formatul concursurilor, dar sper sa ma obisnuiesc

P.S. Am vazut intr-o noapte un topic in care era propusa ideea de a realiza  un fel de ghid spre a fi de ajutor celor care participa pe topcoder. Eu unul sprijin ideea asta.

[•Cosmin]

Eu as fi sprijinit ideea sa nu ai motto ala naspa, da vad ca l-ai schimbat, felicitari.

[•HeLLHeiM]

scuze... userul a fost facut la scoala si acolo actioneaza diferite influentze   . Oricum, nu pun prea mare pret pe chestiile astea

[•cristy]

pentru n=6 e bun rezultatu asta?

Cod:

15 5
1 2  3  4  5 
1 6  7  8  9 
2 6 10 11 12 
3 7 10 13 14 
4 8 11 13 15 
5 9 12 14 15 

[vladut.forum]

hmm daca e corect cred ca si pt n=4
10 4
1 2 3 4
1 5 6 7
2 5 8 9
3 6 8 10
4 7 9 10

zice-ti careva daca e corect... mc mult

[vladut.forum]

dap, vad ca nu raspunde nimeni, am rezolvat problema de 100 acum..si toate exemplele de mai sus sunt ff corecte

[•PuMa]

Stiti cumva cum se poate demonstra(riguros) ca numarul de lacate necesare este egal cu....Am facut pb [ de 100 ] dar am cam ghicit numarul de lacate  

[•cristy]

probabil ca asa au facut toti...

[•fireatmyself]

demonstratia pentru numarul de lacate care este ... se bazeaza pe observatia :

toate lacatele seifului se vor putea deschide numai in prezenta oricarui grup format din cel putin N-1 membrii

[•thestick]

cred ca o parte din voi au avut sentimentul ca sunt nedreptatiti , macar o data in viata!
ajutor
de ce nu sunt toate raspunsurile asa
pt 6 , de ex .

6 2

1 2
1 3
2 4
3 5
4 6
5 6

astept un reply , plz!

[•devilkind]

 fiecare membru detine chei de la lacate distincte

Atunci de ce in exemplul de pe infoarena:

Cod:

lacate.in        lacate.out
2                    1 1
                      1
                      1

ambii membri detin chei de la acelasi lacat?

[•thestick]

pai asta inseamna ca nu o sa ai
membrul1 cheile 1 1 4 5
membrul2 cheile 2 2 8 etc
adica nu o sa aiba dubluri  

[•tm_radu]

TheStick, raspunsul tau nu e bun, pentru ca spune in problema ca seiful se poate deschide doar in prezenta unui grup format din cel putin n-1 membri....iar la tine se poate deschide cu un grup format din membrul 1, 4, 5....

[•k_ounu_eddy]

Pentru N = 4 mie imi da:
6 3
1 2 3
1 4 5
2 4 6
3 5 6


Have fun!

Silviu

Pai uite ca eu am gasit un rezultat cu si mai putine lacate:
3 1
1
2
3
1
Vad ca a mai mentionat si Bindea Catalin despre solutia asta.Ce e gresit aici?

[•devilkind]

orice grup de n-1 membri trebuie sa poate deschide seiful. in configuratia ta grupul de persoane 1 2 4 nu poate deschide seiful si nici grupul 1 3 4.

[•k_ounu_eddy]

Dati-mi si mie o idee despre cum trebuie sa rezolv aceasta problema.O observatie pe care am deduso este ca fiecare membru trebuie sa ii lipseasca cel putin lacate-2 chei ca sa poata fi indeplinita conditia:toate lacatele seifului se vor putea deschide numai in prezenta oricarui grup format din cel putin N-1 membrii.