Salut !

Pana la olimpiada mai trebuie sa inveti functii si structuri !

Tu vei avea nevoie de o Structura care sa iti pastreze pentru fiecare ingredient in parte numele (sub forma de string) si cantitatea (int). Astfel vei avea un vector destructuri (pana la 100 de elemente in total), in care vei retine cele N posibile elemente. Dupa ce ai aflat toate ingredientele si cantitatea, ele trebuiesc sortate crescator dupa nume. In acest mod vei sorta vectorul de structuri, interschimband structurile intre ele, nu doar numele sau cantinatea.

Ar trebui sa arate cam asa:

Cod:

typedef struct
{
char NumeIngr[25];
int cantitate;
} Ingredient;

Ingredient A[101] // declari vectorul ingredient

In concluzie vei sorta acest vector cu bubble sort si gata problema !

Mult succes si sper sa te ajute!

Multumesc frumos pentru raspuns.

Mi-ai putea da si mie sursa prin PM te rog frumos? Din moment ce eu nu mai am idei de rezolvare mi-ar fi de mare ajutor.

Multumesc.

L.E. : Recurenta intr-un fel sau altul era gresita!

[minimul]

Deque-ul acela pastreaza doar minimul pe intervalul [i + L - U,i], pentru fiecare i de la [0,N-L] (pozitiile negative nu se iau in seama). Cred ca asa ar fi o descriere mai usoara a problemei . Dupa care cu minimul respectiv si i + L cred ca stiti ce sa faceti.
Spor la treaba !

Salut la toata lumea.

Am o rezolvare in O(N^2) pe care cred ca o pot si demonstra prin inductie, cu toate acestea iau 0 puncte. Imi puteti spune va rog daca afirmatia mea e corecta? Recursivitatea este asa:

  -  Daca pe pozitia A[ i ][ j ] este 0 si pe A[ i-1 ][ j ] == 0 si A[ i ][ j-1 ] == 0 ( adica si sus si la stanga sa fie 0 ) recursivitatea este A[ i ][ j ] = A[ i-1 ][ j ] + A[ i ][ j-1 ] + 1 - A[ i-1 ][ j-1 ]
  -  Daca A[ i-1 ][ j ] ( cea de deasupra ) e 1 atunci A[ i ][ j ] va lua doar numarul de 0-uri de la stanga
  -  Daca A[ i ][ j-1 ] (cea de la dreapta ) e 1 atunci A[ i ][ j ] va lua doar numarul de 0-uri de deasupra

Este corecta aceasta rezolvare?
Eu am testat aceasta rezolvare pe mai multe teste, chiar am si verificat cu o solutie brute force, si toate imi dau corect.
De ex pentru testul :

Cod:

18
010101010101010111
111000101011010111
111000101011010101
111000101011111010
001010110101010101
111000101011010100
111000101011010100
111000101011111000
001010110101010100
111000101011010100
111000101011010100
111000101011111000
001010111110001000
101101011110001000
101101011110001000
101111100010101100
000000000000000000
000000000000000000

Da 1250 ?

Va rog frumos sa ma ajutati.
Multumesc!

Salut la toata lumea!

Imi poate explica cineva ce are sursa mea de ia 0 pct ?
Imi da pentru orice test as baga raspunsul corect, inclusiv testele oficiale de la ONI. Banuiesc ca este o problema de la Linux ... din moment ce eu lucrez pe Windows nu stiu care ar fi problema. Am o abordare recursiva (care da Incorrect, nu depaseste stiva). Citesc cu fgets() si am o functie asa :

Cod:

void sterge(int A[])
{
	for(int i=1;i<=30;i++)
		A[i] = 0;
}

Cand introduc matricea in functie, mi-o intoarce modificata (cum face pe Windows), sau se intoarce asa cum a intrat? Alta problema nu vad care ar putea sa fie.

Multa bafta tuturor!

Edit : Acum iau 100 pct cu exact aceeasi sursa... Nu pot sa inteleg cum o limita de la 30-40 poate sa incurce un vector care imi trebuia doar pana la 26 ...

Ok ... nu inteleg. Imi poate explica cineva ce este gresit la rezolvarea mea va rog ?

Cod:

int solve(void)
{
	Deckmin[1] = A[1]; //vectorul unde se pastreaza max
	Deckmax[1] = A[1]; //vectorul unde se pastreaza min
	int c = 1;
	Pmin[1] = 1; //vectorul unde editez lungimile secventei pentru deque min
	Pmax[1] = 1; //vectorul unde editez lungimile secventei pentru deque max
	for(int i=2;i<=N;i++)
	{
		Backmin ++;
		while(Backmin>=Frontmin && Deckmin[--Backmin] > A[i]);
		Deckmin[++Backmin] = A[i];
		Pmin[Backmin] = ++c;
		Backmax ++;
		while(Backmax>=Frontmax && Deckmax[--Backmax] < A[i]);
		Deckmax[++Backmax] = A[i];
		Pmax[Backmax] = c;
		if(Deckmax[Frontmax]-Deckmin[Frontmin]>K)
		{
			if(Frontmin == Backmin)
			{
				while(Deckmax[++Frontmax]-Deckmin[Frontmin]>K);
				c -= Pmax[Frontmax];
			}
			else
			{
				while(Deckmax[Frontmax]-Deckmin[++Frontmin]>K);
				c -= Pmin[Frontmin];
			}
			c ++;
		}
		if(MAX<c)
			MAX = c;
	}
	return 0;
}

L.E. : ... ulterior mi-am dat seama ca incercarea mea de rezolvare este utopica. Distantele dintre secvente se calculeaza altfel, deque-ul e bun .

Evaluatorul nu a returnat un numar la stdout pe testul 1 (se ignora spatii, newline, etc)

Am incercat de 3 ori, cu fopen, freopen ... de afisat afisez, ce are ?

Imi poate da si mie cineva un Hint pentru O(sqrt(N)), sau pentru formula ! Nu pot sa trec de 85 pct in O(sqrt(N) + D^2).

L.E. : Pentru a-i ajuta si pe ceilalti, sa caute in solutiile de la ONI 2010 clasa a 9-a, la problema cmmmc. Acolo este explicata cu de-amanuntul formula si evident o rezolvare mai rapida pentru aceasta problema .

In sfarsit mi-a dat si mie cu memorie O(1) ! E una dintre probleme "mici" de la care ai ce invata.

A fost super editia aceasta a Algoritmiadei... tineti-o tot asa .

Nu mai merge evaluatorul !

Fiecare procesor poate procesa numai o singura bere la un moment dat ?

Numarul din fisierul de iesire intra pe 64 de biti ?

Imi poate explica si mie cineva de ce trebuia declarat vectorul long long, deoarece 1...10000 intra si in int!

Hei e clar ca exista si caractere necorespunzatoare  !
Cer, daca OJI a trecut, macar aici sa se faca ceva.

Nu stiu daca am dreptate ... s-ar putea ca in teste sa fie si numere mai mari de 2 miliarde, care trebuiesc tratate de rangul "sutelor de milioane", nu miliarde propriu zis ( cu toate ca in restrictii spune clar nri<=2.000.000.000 ). Sper sa va ajute!

Multumesc frumos !

Salut la toata lumea!

Imi poate da cineva o idee la problema aceasta ?

Parcurgerea aceea (in latime, adancime) nu se face la intamplare. Trebuie sa iei punctul de unde incepe sau de unde se sfarseste linia!

Salut la toata lumea.

Imi poate oferi cineva un exemplu mai concludent? Iau pe primele 8 incorect, si tot ce pun eu in exemplu imi da corect. Nu pot sa-mi dau seama unde gresesc...

De ex:

Cod:

15
1 2
1 3
3 4
3 5
5 6
5 7
2 8
8 10
10 11
4 9
9 12
9 13
6 14
7 15
1 2 3 3 3 2 1 2 2 1 3 3 2 1 1

Imi da :

Cod:

1 5
2 2
3 4
2 2
1 3
1 1
1 2
1 1
2 2
1 1
3 1
3 1
2 1
1 1
1 1

Salut la toata lumea! Imi poate da si mie cineva o solutie pentru aceasta problema? Ma chiunui de cateva zile sa o fac si nu reusesc deloc sa trec de 20 pct, si acelea trase de par. As fi recunoscator daca mi-ati da un hint (sursele nu m-au ajutat prea mult sa inteleg algoritmul, un mesaj pe privat cu algoritmul ar fi binevenit) !

Sirul, propozitia, linia, daca citesti caracter cu caracter, se termina cu '\n' la sfarsit deci n-ai nicio sansa !

Nota : In C !

Salut la toata lumea! Puteti sa mai dati niste exemple pentru aceasta problema? Pe toate exemplele mele merge bine si nu ma prind unde crapa, pentru ca atunci cand il introduc in evaluator iau 0 pct   !

Uitati de exemplu pentru :

Cod:

Se da un text format din litere mari si mici ale alfabetului englez precum si semnele de punctuatie: "," (virgula), "." (punct), "!" (semnul exclamarii), "?" (semnul intrebarii), "..." (puncte de suspensie). Textul se poate intinde pe mai multe linii. Stim ca o fraza se termina cu unul din semnele de punctuatie ".", "?", "!" sau "...". Vrem sa determinam cate fraze sunt si cate cuvinte contine fiecare fraza.
Deoarece textul este intr-o limba neoficiala, cuvintele pot incepe si cu litera mica si pot contine litere mari in interior sau la final.
Atentie, cuvintele pot fi separate de oricate spatii si pot exista spatii la inceputul si la sfarsitul frazelor.

Imi da :

Cod:

13
21
3
4
4
4
8
13
2
2
3
1
12
23

Asa trebuie sa dea si daca da de ce as lua 0 pct ?

Salut la toata lumea! Vreau si eu sa stiu cu ce gresesc. Fac un backtracking recursiv de n+m elemente. Multimea variabilelor pe care poate sa le ia e 1/-1, cum trebuie sa fac ca sa il optimizez, deoarece imi depaseste timpul pe 5 teste. Multumesc!

LE : Am reusit s-o fac facand backtracking de n elemente si calculand maximul dintre coloane : 100 pct !