412 Randuri

[•DITzoneC]

Aici puteţi discuta despre problema Randuri.

[•gabitzish1]

nu prea am inteles cum se calculeaza muzicalitatea  .. pot primi niste explicatii de la cei care au inteles?

[•marcelcodrea]

Muzicalitatea este de fapt lungimea celui mai lung subsir comun al celor 2 versuri .

http://zhuzeyuan.hp.infoseek.co.jp/ita/chap16.htm

Sectiunea 16.3 !

[•CezarMocan]

Ce complexitate trebuie scoasa pentru a lua 100?? Ca eu iau 60 de puncte (cu TLE pe testele 8 si 9). Complexitatea e ceva de genu O(n²*muzicalitate+n³+n²)

L.E. Solved

[•jupanu92]

Eu nu pot sa inteleg cum se calculeaza muzicalitatea

[•fireatmyself]

Asadar, muzicalitatea reprezinta dimensiunea celei mai lungi succesiuni formata din caractere ce apar in ordinea din succesiune atat in primul rand, cat si in cel de al doilea, pe pozitii nu neaparat consecutive.

cu alte cuvinte, muzicalitatea a doua randuri este lungimea cel mai lung subsir comun al acestora.

[•jupanu92]

Deci in propozitiile acestea Te-nalta pana-n nori Tot mai departe cel mai lung subsir comun care ar fi ? cred ca 'pa' si muzicaliatea in explicatie e 7 
I'm  confuse

[•pauldb]

Un subsir este o multime de elemente din sir nu neaparat consecutive, luate in ordinea in care apar. Ce spui tu se numeste subsecventa.

[•jupanu92]

Ms am inteles.

[•cristiprg]

io calculez lungimea celui mai lung subsir comun a doua stringuri cu o functie , cand ii mai mare ca 6 incrementez un contor, dar la 3 teste imi afiseaza cu 1 in plus fata de normal si nu stiu de ce, iar daca afisez cu 1 mai putin, numa testele alea 3 is bune, scap ceva probabil     pls help !

Cod:

int cmlsc(char s1[], char s2[])
{
	
	int i, j;
	int n = strlen(s1) - 2, m = strlen(s2) - 2;
	for (i = 0; i <= n ;i++)
		for (j = 0; j <= m; j++)
		{
			if (a[i][j] > 6)
			{
				curata(i, j);
				return 1;
			}

			if (s1[i] == s2[j])
			{
				if (i != 0 && j != 0)
					a[i][j] = a[i-1][j-1] + 1;
				else     //daca ii pe margine
					if (i == 0 && j != 0)
						a[i][j] = a[i][j-1];
					else
						if (i != 0 && j == 0)
							a[i][j] = a[i-1][j];
						else
							a[i][j] = 1;

			}

			else
			{
				if (i != 0 && j != 0 )
					a[i][j] = max(a[i-1][j], a[i][j-1]);
				else     //daca ii pe margine
					if (i == 0 && j != 0)
						a[i][j] = a[i][j-1];
					else
						if (i != 0 && j == 0)
							a[i][j] = a[i-1][j];
						else
							a[i][j] = 0;
			}
		}




	if (a[n][m] > 6)
		{curata(n, m);return 1;}

	else
		{curata(n, m);return 0;}

[•ucc_5]

Nu inteleg de ce nu imi merge testul 5 ! Ce are asa special ?
Dupa ce m-am chinuit o jumatate de zi cu testele de evaluare de la oni si apoi am aflat ca sunt gresite (inclusiv rezolvarea data de profesori (bravo domnilor, sunteti tari  ! )) acuma ma chinui si aici. Are cineva vreo idee ca am vazut ca au mai fost cativa carora nu le-am ers testul iar apoi au luat 100

[•DraStiK]

Nu inteleg de ce nu imi merge testul 5 ! Ce are asa special ?
Dupa ce m-am chinuit o jumatate de zi cu testele de evaluare de la oni si apoi am aflat ca sunt gresite (inclusiv rezolvarea data de profesori (bravo domnilor, sunteti tari  ! )) acuma ma chinui si aici. Are cineva vreo idee ca am vazut ca au mai fost cativa carora nu le-am ers testul iar apoi au luat 100

nu cred ca e gresita rezolvarea oficiala
eu de acolo mam inspirat si am reusit sa fac de 100

incearca sa mai dai niste teste si vei gasi problema (apropo, eu cred ca s-au pastrat testele de la ONI)

[•cipri_tom]

stie cineva ce are testul 2 si testul 3 mai special?
iau Incorrect si imi da cu un rand mai putin (verificat).
se poate sa fie sters si ultimul sau primul rand?

[•stocarul]

se poate sa fie sters si ultimul sau primul rand?

Conform enunțului:

... un rand se poate elimina doar daca imediat inaintea sa se afla un rand (sa-l notam p), iar imediat dupa el se afla un alt rand (sa-l notam u) astfel incat randurile p si u au muzicalitatea strict mai mare decat 6 ....

Reiese că primul și ultimul rând nu pot fi eliminate, deoarece nu pot fi încadrate de două rânduri.

[•SebiSebi]

Imi poate spune cineva daca gresesc la determinarea celui mai lung subsir comun :

Cod:

int muzicalitate(char a[], char b[])
{
	int n,m,i,j;
	n=strlen(a)-1;
	m=strlen(b)-1;
	for(i=1;i<=n;i++)
		for(j=1;j<=m;j++)
			if(a[i]==b[j])
				d[i][j]=1+d[i-1][j-1];
			else d[i][j]=maxim(d[i-1][j],d[i][j-1]);
	return d[n][m];
}

Sirurile sunt indexate de la 1(pe pozitia 0 se afla ' ');
Multumesc anticipat!

[•fulgerulnegru]

Acum eu am incarcat sourca de la oni si nu am reusit sa iau 100 de puncte (Am modificat doar cat sa nu am erori de sintaxa ) in reste e foarte bine

P.S pentru cei curiosi am modificat doar din

Cod:

#include<fstream.h>

in

Cod:

#include<fstream>

si am adaugat

Cod:

using namespace std;