[TEMA] degrade .campion

Se da problema: http://campion.edu.r...tion=view&id=49

#include<cstdio>
#include<cstring>
#define MAX 100001
using namespace std;
FILE * fin=fopen("degrade.in", "r");
FILE * fout=fopen("degrade.out", "w");
int n, i, v[128], j = 1, total, maxs = 1, sir = 1, v1[MAX];
char s[MAX], ch;
void decodificare(char arg[], int target[], int size);
int sirLgMax(int arg[], int size);
int totalSiruriLgMax(int arg[]);
int main() {
	do {
		ch = fgetc(fin);
		if (ch != '\n') v[(int)ch] = ++total;
	} while (ch != '\n');
	fgets(s, 128, fin);
	n = strlen(s)-1;
	decodificare(s, v1, n);
	maxs = sirLgMax(v1, n);
	fprintf(fout, "%d %d", maxs, totalSiruriLgMax(v1));
	fclose(fin);
	fclose(fout);
}
void decodificare(char arg[], int target[], int size) {
	for (i = 0; i<size; i++) target[i] = v[(int)s[i]];
}
int sirLgMax(int arg[], int size) {
	sir = 1, maxs = 1;
	for (i = 1; i<size; i++) {
		if (arg[i] >= arg[i-1]) {
			sir++;
			if (sir > maxs) maxs = sir;
		} else sir = 1;
	}
	return maxs;
}
int totalSiruriLgMax(int arg[]) {
	total = 0;
	for (i = 0; i<n-maxs; i++) {
		sir = 1;
		for (j = i; j<i+maxs-1; j++) {
			if (arg[j+1] >= arg[j]) sir++;
			else sir = 1;
		}
		if (sir == maxs) total++;
	}
	return total;
}

Sincer sa fiu, chiar nu stiu unde e problema in cod de iau numai 30 de puncte ori nu am inteles eu prea bine ce se cere.

ce-ar fi sa asociezi cifre literelor in functie de intensitate

apoi rezolvi problema de baza de aici http://forum.softped...a-a-vectorului/ , avand in vedere faptul ca lungimea maxima nu poate fi mai mare de 10.

Edited by MarianG, 16 April 2014 - 12:44.

in primul rand, nu pari sa calculezi corect valoarea intoarsa de sirLgMax()
in al doilea rand, aste e o problema clasica de programare dinamica. se rezolva asa:
pasul 1:
-incepand de la sfarsitul sirului de valori se determina lungimea degrade-ului care ar incepe cu acea valoare
-pentru asta folosesti un alt sir de int-uri (sa-i zicem lungimi[])
-pe ultima pozitie a noului sir (lungimi[n-1]) pui 1 (fiind ultima valoare, nu poti avea un degrade cu lungime 2 care sa inceapa acolo)
-pentru a completa pozitia X a noului sir compari intensitatea de pe pozitia X cu cea de pe X+1; daca e mai mica sau egala, atunci lungimi[X] = lungimi[X+1] + 1; in caz contrar lungimi[X] = 1
pasul 2:
-iterezi prin noul sir (lungimi) si determini valoarea maxima (si de cate ori apare); poti face asta cu o singura iteratie
pasul3:
-afisezi rezultatul

Am modificat codul dupa cum a zis @_Smiley_

#include<cstdio>
#include<cstring>
#define MAX 100001
using namespace std;
FILE * fin=fopen("degrade.in", "r");
FILE * fout=fopen("degrade.out", "w");
int n, i, v[128], j = 1, total, lgMax, v1[MAX];
char s[MAX], ch;
void decodificare(char arg[], int target[], int size);
int main() {
	do {
		ch = fgetc(fin);
		v[(int)ch] = ++total;
	} while (total<10);
	fscanf(fin, "\n");
	fgets(s, 128, fin);
	n = strlen(s)-1;
	decodificare(s, v1, n);
	v[n] = 1;
	for (i = n-1; i>=0; i--) {
		if (v1[i] <= v1[i+1]) v[i] = v[i+1]+1;
		else v[i] = 1;
		if (v[i] > lgMax) lgMax = v[i];
	}
	total = 0;
	for (i = 0; i<n; i++) if (v[i] == lgMax) total++;
	fprintf(fout, "%d %d", lgMax, total);
	fclose(fin);
	fclose(fout);
}
void decodificare(char arg[], int target[], int size) {
	for (i = 0; i<size; i++) target[i] = v[(int)s[i]];
}

Dar degeaba, tot 30 de puncte iau. Unul din teste e

ijdefabcgh
dehcbfabhahjjgjdjaagcjcefbdfidadhigjfiaeijdjhcdjcffggacbbgjjbjdjjbaebcjceebdhecbbiaiacjbaidcaibjbdechfgbjifiehcghcehefbfegjeecfhfbbcgigigbicaaiacchjiageghacjfbehdifbefjhebigaijehaeaiaifcbeieahhaeafajegdecfedjcdgedgcabfgbagihheaegbiceffjjibdehhhfaigfgjfdjfcehiaiidddicdgdgcceaaeaibgijbhgfbddebehehhjafejihdajjchcahbefhjiafeejdiiajbieaidficgcbacjcggbigefbigeiehihfcjffgfjchadjbhihaieedhejbdfadfhfeccbhbfebagdjgcaegejfjahehjhchejjgajhhfaidfhjihfgegcfibjgaiahcjjibihjfhhjdgibegjicbfdcejdcjcebbecbbbhaigdfggbcgbhhgaccbfecjadbggehhbhijdfgbiahjjhhbjjegfhfhaidifcgibgigdgibifcaejbfagbhfjefjjeedcfeadbdbbejigbdhdihbcegdadcjjjebgidjbgcecddafghaggbicjdccidchhfdijebhigabbaghaifijgbijfdhbhgacbadfcbfabhbdfafehefdhgfejcfgjgacieaaffciefdahjgffbichdgiicgjahbibbbghfgdbjdiijdddehcjebhihiagaahddfcjbgcdjadbgjgcgabcbbcbjcjjfhfichjgdbjfeeicdgeagfeaghdibcjgbehgegcjadgehggdcadbhhbggggiifeccdigaafcfcgeiehdgcgfchdifjgffdhhgfdihaaceijfegicbeiddbbabafifdfdiaciceahfbcbacebicedfhdijigebdicfcaiicffejhgbbhbfdecchbcfjijfibaadaj

Raspunsul oficial e 8 1, iar la mine am 4 5

Edited by pasandrei, 16 April 2014 - 14:16.

Se pare ca n-ai vazut faptul ca j<a<...<g<i.
In rest, e o problema clasica, in a numara secventele (alea continue) crescatoare de lungime maxima. Iar PD este fortata pentru acest exercitiu. Insa s-ar fi pretat daca era vorba de subsiruri.

Ce vrea sa faca acest cod?

do {
				ch = fgetc(fin);
				v[(int)ch] = [b]++total[/b];
		} while ([b]total<10[/b]);

 pasandrei, on 16 aprilie 2014 - 13:56, said:

Nu voi intelege niciodata de ce incepatorii au acest talent de a ignora sfaturile bune, si a le prelua pe cele nu atat de bune.

 pasandrei, on 16 aprilie 2014 - 13:56, said:

ai niste probleme pe acolo:
-nu initializezei variabila total
-dupa decodificare folosesti valori din "v" de la 0 la n; asta inseamna n+1 elemente
-vectorul tau are 128 de elemente; in enuntul problemei se precizeaza ca pot fi 100001 patratele

 OriginalCopy, on 16 aprilie 2014 - 14:44, said:

iti poti detalia un pic postul? care-i sfatul "bun", care-i sfatul "nu atat de bun" si de ce?

Am reusit sa scot 100.

#include<cstdio>
#include<cstring>
#define MAX 100001
using namespace std;
FILE * fin=fopen("degrade.in", "r");
FILE * fout=fopen("degrade.out", "w");
int n, i, v[MAX], j = 1, total, lgMax, v1[MAX];
char s[MAX], ch;
void decodificare(char arg[], int target[], int size);
int main() {
	do {
		ch = fgetc(fin);
		v[(int)ch] = ++total;
	} while (total<10);
	fscanf(fin, "\n");
	fgets(s, MAX, fin);
	n = strlen(s)-2;
	decodificare(s, v1, n);
	v[n] = 1;
	for (i = n-1; i>=0; i--) {
		if (v1[i] <= v1[i+1]) v[i] = v[i+1]+1;
		else v[i] = 1;
		if (v[i] > lgMax) lgMax = v[i];
	}
	total = 0;
	for (i = 0; i<n; i++) if (v[i] == lgMax) total++;
	fprintf(fout, "%d %d", lgMax, total);
	fclose(fin);
	fclose(fout);
}
void decodificare(char arg[], int target[], int size) {
	for (i = 0; i<=size; i++) target[i] = v[(int)s[i]];
}

Problema era la v[128] pe care l=am modificat in v[MAX] si la initializarea lui n unde am pus initial -1, dar mi-am amintit apoi ca si '\n' este numarat de strlen().

map <char, int> codes;
	char my_character ;
	while (!fin.eof() )
	{
		fin.get(my_character);
		codes[my_character]=index++;
		if (my_character == '\n') { break; }
	} // 10 iteratii, nu enspe mii

MI-O SCRIE SI MIE CINEVA IN PASCAL CA AM MARE NEVOIE

 andrieies, on 28 octombrie 2014 - 21:06, said:

Pune burta pe carte!