|
Titlul: 488 Strigat Scris de: Adrian Diaconu din Iulie 30, 2007, 14:22:03 Aici puteţi discuta despre problema Strigat (http://infoarena.ro/problema/strigat).
Titlul: Răspuns: 488 Strigat Scris de: Paul-Dan Baltescu din Iulie 31, 2007, 12:47:23 Imi puteti spune ce are mai special ultimul test? Am vazut ca sunt si altii care se chinuie la el.
Later edit: Mi-am gasit singur un test care-mi pica. Poate mai ajuta pe cineva: Cod: 8 3 Titlul: Răspuns: 488 Strigat Scris de: Savin Tiberiu din August 01, 2007, 10:12:16 pai cuvantul e "oooooooo" si contine de 8 ori cuvantul "o" de 4 ori cuvantul "oo" si 1 singura data cuvnatul "oooooo". Deci gradul de spaima e 8*1+4*2+1=17.
Titlul: Răspuns: 488 Strigat Scris de: Bogdan-Cristian Tataroiu din August 01, 2007, 10:59:48 contine de 8 ori "o", de 7 ori "oo" si de 3 ori "oooooo" de fapt. -> 25
Titlul: Răspuns: 488 Strigat Scris de: Savin Tiberiu din August 01, 2007, 20:39:02 da scuze am uitat de suprapunere
Titlul: Răspuns: 488 Strigat Scris de: Ionescu Victor Cristian din August 05, 2007, 19:48:16 kmp iese din timp ](*,)
Titlul: Răspuns: 488 Strigat Scris de: Andrei Grigorean din August 06, 2007, 12:26:09 Trebuie un automat finit :).
Titlul: Răspuns: 488 Strigat Scris de: Lucian Boca din Aprilie 13, 2008, 22:48:15 Cum se poate construi un automat finit determinist care accepta mai multe (N) cuvinte?
Adica... nu imi dau seama care sunt starile lui :? Titlul: Răspuns: 488 Strigat Scris de: Bogdan-Alexandru Stoica din Aprilie 14, 2008, 14:48:16 gasesti aici (http://infoarena.ro/summer-challenge-2007/solutii/runda-1) mai multe informatii.
Titlul: Răspuns: 488 Strigat Scris de: Lucian Boca din Aprilie 14, 2008, 16:21:38 Citisem solutia oficiala (http://infoarena.ro/summer-challenge-2007/solutii/runda-1) si articolul despre automate finite (http://infoarena.ro/Automate-finite-si-KMP). Am inteles cum se poate construi un automat finit care accepta un cuvant, dar, din cate inteleg din solutie, trebuie construit un automat care accepta mai multe cuvinte, iar starilor de acceptare le voi asocia apoi valorile "strigatului" (nu pot construi un automat avand ca stari cele 100 * 1000 valori posibile pentru strigat...). Dupa asta, dinamica e evidenta.
Insa, asa cum am spus, ramane de construit automatul pentru cele M cuvinte. :-k LE: Cred ca m-am prins cum se face: pot lua ca stari toate prefixele cuvintelor, prefixele comune aparand o singura data. Astfel am maxim LTot stari, unde LTot este lungimea totala a cuvintelor. Constructia automatului se poate face astfel in O( LTot*|sigma| ) LE2: ...sau nu :-' |