Imprimă pagina - 412 Randuri

Titlul: 412 Randuri
Scris de: Adrian Diaconu din Aprilie 24, 2007, 07:42:38

Aici puteţi discuta despre problema Randuri (http://infoarena.ro/problema/randuri).

Titlul: Răspuns: 412 Randuri
Scris de: Gabriel Bitis din Mai 12, 2007, 16:44:51

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

Titlul: Răspuns: 412 Randuri
Scris de: Codrea Marcel din Mai 12, 2007, 17:56:47

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 !

Titlul: Răspuns: 412 Randuri
Scris de: Cezar Mocan din Ianuarie 04, 2008, 14:22:27

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²) :D

L.E. Solved

Titlul: Răspuns: 412 Randuri
Scris de: Anonim din Aprilie 04, 2008, 19:07:29

Eu nu pot sa inteleg cum se calculeaza muzicalitatea :(

Titlul: Răspuns: 412 Randuri
Scris de: Bogdan-Alexandru Stoica din Aprilie 04, 2008, 19:58:12

Citat

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.

Titlul: Răspuns: 412 Randuri
Scris de: Anonim din Aprilie 04, 2008, 22:03:36

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

Titlul: Răspuns: 412 Randuri
Scris de: Paul-Dan Baltescu din Aprilie 04, 2008, 23:05:02

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

Titlul: Răspuns: 412 Randuri
Scris de: Anonim din Aprilie 28, 2008, 19:41:12

Ms am inteles.

Titlul: Răspuns: 412 Randuri
Scris de: Prigoana Cristian din Martie 22, 2009, 19:02:01

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;}

Titlul: Răspuns: 412 Randuri
Scris de: Usurelu Catalin din Aprilie 03, 2009, 16:50:15

Nu inteleg de ce nu imi merge testul 5 ! :x 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 :annoyed:! )) 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

Titlul: Răspuns: 412 Randuri
Scris de: Dragos Oprica din Aprilie 05, 2009, 20:07:54

Citat din mesajul lui: usurelu catalin din Aprilie 03, 2009, 16:50:15

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)

Titlul: Răspuns: 412 Randuri
Scris de: Ciprian Tomoiaga din Februarie 24, 2010, 13:23:56

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?

Titlul: Răspuns: 412 Randuri
Scris de: Cosmin-Mihai Tutunaru din Februarie 24, 2010, 16:34:39

Citat din mesajul lui: Ciprian Tomoiaga din Februarie 24, 2010, 13:23:56

se poate sa fie sters si ultimul sau primul rand?

Conform enunțului:

Citat

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

Titlul: Răspuns: 412 Randuri
Scris de: Pirtoaca George Sebastian din Februarie 24, 2012, 15:57:30

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!

Titlul: Răspuns: 412 Randuri
Scris de: FMI Ekart Dragos-Ioan din Martie 01, 2012, 17:18:49

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>

Cod:

#include<fstream>

si am adaugat

Cod:

using namespace std;

infoarena

infoarena - concursuri, probleme, evaluator, articole => Arhiva de probleme => Subiect creat de: Adrian Diaconu din Aprilie 24, 2007, 07:42:38