|
Titlul: Problema Subsecventa Scris de: Razvan din Septembrie 23, 2013, 15:29:54 Salut, am incercat sa rezolv o problema dar nu-mi iasa de nici o culoare, problema spune:
Fie n un număr natural și M={S1,S2,…,Sn} o mulțime de șiruri de caractere nevide. Fie Sk un șir de caractere din M. Atunci, orice caracter al lui Sk aparține mulțimii { 'a', 'b' }. Notăm prin |Sk| numărul caracterelor șirului Sk sau, echivalent, lungimea sa. O subsecvență Sk[i:j] a lui Sk este formată din caracterele situate pe pozițiile consecutive i, i+1, .., j. Astfel, dacă Sk = 'abbbaababa', atunci Sk[3:6] = 'bbaa' sau subsecvența evidențiată: 'abbbaababa'. Cerință Fiind dată o mulțime M, se cere să se determine lungimea maximă a unei subsecvențe care se găsește în toate șirurile din M. Date de intrare Pe prima linie a fișierului de intrare subsecvente.in se găsește un număr natural n egal cu cardinalul mulțimii M. Pe fiecare din următoarele n linii se găsește câte un șir din mulțimea M. Date de ieșire Pe prima linie a fișierului de ieșire subsecvente.out se va scrie un singur număr natural egal cu lungimea subsecvenței găsite Exemplu: Date de Intrare: 4 abbabaaaaabb aaaababab bbbbaaaab aaaaaaabaaab Date de Iesire: 5 Explicatie: Lungimea unei subsecvenţe comune de lungime maximă este 5. În exemplu subsecvența comună de lungime 5 este aaaab: abbabaaaaabb, aaaababab, bbbbaaaab, aaaaaaabaaab. Imi puteti da niste sfaturi despre aceasta problema, ce metode se pot folosi, si care sunt acestea? Titlul: Răspuns: Problema Subsecventa Scris de: Alexandru Valeanu din Septembrie 23, 2013, 16:10:16 Problema si poate rezolva cu programare dinamica sau cu siruri de sufixe. Ar fii bune nistre restrictii ca sa fii sigur care metoda e mai simpla. Daca siruri nu sunt lungi ( < 1000 ) si M destul de mic ( < 100 ) merge mai usor cu PD. Succes!
Titlul: Răspuns: Problema Subsecventa Scris de: Razvan din Septembrie 23, 2013, 16:35:18 Restricții
• 1 < n < 5 • Dacă |S| = |S1| + |S2| + … + |Sn|, atunci |S| < 50 001 • Se garantează că va exista întotdeauna soluție • Se garantează că rezultatul nu va depăși 60 • Pentru 30% din teste: |S| < 101 • Pentru 55% din teste: |S| < 3 501 • Pentru 80% din teste: |S| < 10 001 Am uitat. Titlul: Răspuns: Problema Subsecventa Scris de: Alexandru Valeanu din Septembrie 23, 2013, 16:49:27 Puteai spune si tu ca problema a fost data la OJI 2013. La sectiunea Downloads de pe IA ai solutiile oficiale de la OJI 2013. Succes!
|