infoarena

Aici puteţi discuta despre problema Lacate (http://infoarena.ro/problema/lacate).

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

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.

ma, va rog frumos, un exemplu macar [-o< ...

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.

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

6 e cam mare :D

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


Have fun!

Silviu

10x! :)

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

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

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

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

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

pentru n=6 e bun rezultatu asta?

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

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

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

probabil ca asa au facut toti...

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

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!

Atunci de ce in exemplul de pe infoarena:


ambii membri detin chei de la acelasi lacat?

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

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

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?

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.

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.

pai enuntul iti spune ca lacatele pot fi deschise in prezenta a N-1 membrii, deci daca lipsesc 2 membrii nu se mai pot deschide.
Uitate pe exemplele de mai sus si iti dai seama ce trebuie sa faci.

Cred ca nu m-am exprimat bine, nu am zis absenta a 2 membri,ci a n-2 lacate.
De ex,n=3,3 lacate => fiecarui membru trebuie sa ii lipseasca 3-2=1 lacate,adica fiecare sa aiba 2 lacate,si vine solutia:
3 1
12
23
31
In posturile anterioare nu am gasit nici un indiciu,mai mult niste exemple de solutii.Care vrea sa imi zica,pls.

 imi cer scuze daca nu te-am inteles, dar eu cred ca tu nu ai inteles enuntul, membrii comisiei trebuie sa detina chei si nu lacate, lacatele sunt la seif si daca te refereai la chei si numarul de chei pe care le detine un membru al comisiei sa fie nr_lacate-2 , nu este bine , asta puteai sa o deduci din exemplul lui :
adica 15-2!=5.
ps: ce am postat mai sus era ideea pe care ai cerut-o, vezi ce se intampla cand lipsesc 2 membrii in exemplul lui cristian , oricare ar fi acesti membrii. :thumbup:

Dati-mi o idee ca tot nu m-am prins.In posturile anterioare nu am gasit decat exemple de solutii,dar vreo indicatie,nu.

stop Trimbitas Viorel Stefan !!!
Bine ca nu pui si implementariile pe forum. Cred ca ar trebui editate mesajele tale  :-k

Intr-adevar exagerezi! Daca cineva va avea nevoie de ajutorul tau, fii sigur ca ti-l va cere. Nu e cazul sa te dai "mare scula in bascula" pe forum cu cate stii tu. O sa ne dovedesti cat esti de valoros in timpul concursurilor.

Fratilor...explicati-mi si mie de ce pt. n=4 nu este bun si
2 1
1: 1
2: 1
3: 2
4: 2
 sau
1 1 ..ma rog..toti sa aiba 1 adica..exemplul respecta conditiile
1. oricare doi membri detin acelasi numar de chei
2. fiecare membru detine chei de la lacate distincte
3. toate lacatele seifului se vor putea deschide numai in prezenta oricarui grup format din cel putin N-1 membrii
Daca mesajul este nepotrivit rubricii rog moderatorii sa-l scoata ...#1 time cand postez

   Din cate vad eu se poate deschide lacatul si in prezenta unui grup de 2 persoane ( 1 si 3) si nu e bine (vezi cond. 3)

imi zice si mie cineva de ce pt n=4 de ce
1 1
1
1
1
1
nu e bun?

Nu este respectata conditia asta.

aaa gata ma  prins si eu   :-' ms 

nu stiu exact riguros dar cred ca pleaca de la faptul ca oricare 2 membrii trebuie sa aiba o cheie in comun si ca ei trebuie sa fie singurii cu acea cheie

pana la urma de ce nu e buna solutia:

N-1 1
1
2
3
...
N-2
N-1
1
?
exista vreo una cu mai putine lacate?
dati-mi va rog un exemplu :D

Sunt oarece debusolat...
Eu inteleg de ce nu merge un raspuns de genul (la n=4)
3 1
1
2
3
...

Si nici:
1 1
1
1
...

Dar totusi... explicati-mi va rog de ce nu ar fi buna solutia:
3 3
1 2 3
1 2 3
1 2 3
1 2 3
 :?

Ma gandesc... din ce inteleg eu in conditii, nu cere sa se afiseze un numar minim de chei... ci doar de lacate, iar acesta va fi intotdeauna va fi N-1 sau mai mare, dar nu e corecta si solutia de N-1 lacate si cate o cheie la fiecare lacat pentru fiecare membru? Respecta conditiile totusi...

Nu este corecta solutia cu n-1 lacate deoarece problema cere ca oricare n-1 persoane sa aiba toate cheile pe cand daca dam primilor n-1 presoane cheile 1,2,...,n-1 ultimul va trebui sa ia de exemplu cheia 2 si daca luam persoanele de la 2 la n nu vor avea cheia 1