Am o intrebare, folosesc invers modular ca sa calculez Aranjamente(N, K) % 666013. Factorialul imi da la un anumit moment % 666013 valoarea 0, si deci Factorial[N]*invmod(Factorial[N-K]) va da 0. Dar daca as avea, sa zicem A(666015, 1) % 666013, raspunsul ar fi 2. Poate cineva sa imi explice va rog de ce? Multumesc anticipat.

Numerele intregi, de exemplu 0, trebuia sa fie afisate cu ".0" la final neaparat? Ca normal nu ar prea conta ) Si am luat 0, iar pe testele oficiale asta e singura diferenta dintre raspunsurile mele si raspunsurile bune.

) Ok.

L.E.: Am reusit dupa cateva zile de inmultit matrici pe la scoala sa ajung la un rezultat. Parca ma simt mai bine decat daca mi-ati fi trantit rezultatul in fata ) Deci, multumesc!

Imi poti spune te rog cum arata matricea fixata pentru fib de 3? Nu gasesc niciun pattern fata de fib de 2.

Merge cu o idee asemanatoare sa faci in timp logaritmic si al k-lea termen fibonacci de 3, 4, 5 s.a.m.d. ?(fib de 3 fiind Fn=Fn-1+Fn-2+Fn-3)

Problema are legatura cu puterile lui 5, nu cu raspunsurile pentru anumite puteri ale lui 5 din fisierul de intrare.
Ca sa ai un 0 la final la rezultatul factorialului, trebuie sa observi din ce se formeaza.

Mersi, mi-am dat seama ce greseam, oricum n-am (inca) solutia buna ca sa iau 100 p ).

Iau incorect pe majoritatea testelor si nu inteleg ce gresesc. Ma puteti ajuta cu niste teste va rog?

In cazuri exceptionale (ex: boala) un concurent poate fi insotit si de parinte. Trebuie facuta o cerere la inspectorat, care va fi trimisa apoi la inspectoratul din Bihor (unde se tine ONI de la gimnaziu), dupa care, daca o aproba, poate sa vina si parintele si sa fie cazat in aceeasi locatie cu elevul, asta in cazul in care se doreste cazarea parintelui in aceeasi locatie.

In primul rand nu trebuia sa postezi aici, ci la sectiunea "Informatica", dar probabil iti va muta un admin thread-ul.
Problema se rezolva asa, daca nu stii vectori:
- Parcurgi cifrele de la 0 la 9
- Verifici daca cifra i se gaseste in cele doua numere
- Ai grija sa nu strici numele, fiindca apoi la pasul urmator nu mai poate sa afle programul cifrele comune.

O implementare a unui astfel de cod fara vectori ar fi asta: (n-am mai declarat variabile etc., l-am scris direct, te descurci tu probabil)

Cod:

for(i=0; i<=9; i++)
{
aux=n;
aux2=m;
okn=0;
okm=0;
while(aux)
{
if(aux%10==i)
okn=1;
aux/=10;
}
while(aux2)
{
if(aux2%10==i)
okm=1;
aux2/=10;
}
if(okn && okm)
cout<<i<<" ";
}

Se putea fara niciun vector.

Da ia de 2x timpu pe care il ia cu vector de 50k Nu ca ar conta, eram doar curios

Cu stream-uri fara vectori ia cu 14 ms mai mult doar

salut, am cateva intrebari. Am alocat memorie statica si nu-mi da MLE din primele teste! de ce? si am alocat 100002 int!
si daca poate cineva sa imi dea o idee cum as putea sa rezolv cu limita de memorie. cu un vector int de 50002 componente iau 70 de puncte si pe doua teste e incorect.

Rezolva fara niciun vector.

Asta era! Mersi mult

Intr-adevar, dar se pare ca nu asta e problema. Am initializat maxim cu maxim=-10000000000000LL; si tot WA iau. Mersi pentru raspunsul prompt oricum

Iau 90 cu TLE pe primul test, pe al doilea am 24ms cel mai bine. Idei de optimizare ?

Iau 90 puncte cu WA pe testul 8. Folosesc un multiset in care bag la fiecare pas s[i+U-1] si scot s[i+L-2] (s fiind sume partiale). Nu inteleg ce ar putea fi gresit ?.

http://campion.edu.ro/arhiva/index.php?page=problem&action=view&id=1344

Am facut o solutie care pare buna (am testat-o pe mai multe teste si se pare ca da bine). Am procedat asa: am facut o matrice "jos", continand matricea de pe fata 1 si mai jos de ea matricea de pe fata 2 intoarsa cu capul in jos (pentru ca nr care urca pe prima fata este primul nr de pe fata 2), si o matrice "stanga", unde am pus matricea de pe fata 1 si la dreapta (stiu ca trebuia sa o numesc "dreapta") am pus cea de pe fata 2.
Apoi, bazandu-ma pe periodicitate, am facut operatiile in M*2N (refac linia/coloana curenta de pe matricea "jos" si "stanga"), punand rezultatul intr-o alta matrice.
La final, afisez rezultatul...

Am si sursa aici:

Cod:

#include <fstream>
using namespace std;
char x[5001];
int incln[1001], inccl[1001];
short mat[1001][1001], jos[2002][1001], stanga[2001][1001], vec[2002];
int k, i, n, nr, m, as, df, j;
char cr;
int main()
{
	ifstream f("slide.in");
	ofstream g("slide.out");
	f>>n;
	f.getline(x, 10);
	for(i=1; i<=n; i++)
	{
		f.getline(x, 5001);
		int p=strlen(x);
		k=0;
		incln[i]=1;
		for(j=0; j<p; j++)
		{
			if(isdigit(x[j]))
			{
				nr=0;
				while(isdigit(x[j]))
				{
					nr=nr*10+x[j]-48;
					j++;
				}
				k++;
				inccl[i]=i;
				incln[i]=1;
				mat[i][k]=nr;
			}
		}
	}
	int l2=2*n, k2;
	for(i=1; i<=n; i++)
	{
		f.getline(x, 5001);
		int p=strlen(x);
		k=0;
		k2=n+1;
		for(j=0; j<p; j++)
		{
			if(isdigit(x[j]))
			{
				nr=0;
				while(isdigit(x[j]))
				{
					nr=nr*10+x[j]-48;
					j++;
				}
				k++;
				jos[i][k]=mat[i][k];
				k2--;
				jos[l2][k]=nr;
				stanga[i][k]=mat[i][k];
				stanga[i][k+n]=nr;
			}
		}
		l2--;
	}
	f>>m;
	int contor;
	for(int t=1; t<=m; t++)
	{
		f>>cr>>as>>df;
		if(cr=='C')
		{
			inccl[as]=2*n-(df%(2*n))+1;
			contor=0;
			for(i=inccl[as]; contor<2*n; i++)
			{
				if(i>2*n)
					i=1;
				contor++;
				if(contor<=n)
					mat[contor][as]=jos[i][as];
				vec[contor]=jos[i][as];
			}
			for(i=1; i<=2*n; i++)
			{
				jos[i][as]=vec[i];
				if(i<=n)
					stanga[i][as]=vec[i];
			}
		}
		if(cr=='L')
		{
			incln[as]=2*n-(df%(2*n))+1;
			contor=0;
			for(i=incln[as]; contor<2*n; i++)
			{
				if(i>2*n)
					i=1;
				contor++;
				if(contor<=n)
					mat[as][contor]=stanga[as][i];
				vec[contor]=stanga[as][i];
			}
			for(i=1; i<=2*n; i++)
			{
				stanga[as][i]=vec[i];
				if(i<=n)
					jos[as][i]=vec[i];
			}
		}
	}
	for(i=1; i<=n; i++)
	{
		for(j=1; j<=n; j++)
		{
			g<<mat[i][j]<<" ";
		}
		g<<"\n";
	}
}

Mersi anticipat!

Una din posibilele reguli de umplere a matricii este:

Cod:

if(i+j<=n+1)
{
	mat[i][j]=i+j-1;
}
else
{
	mat[i][j]=2*n-i-j+1;
}

Succes!

Mi-am dat seama.

Faci un algoritm de fill care sa-ti numere insulele cu 1, cu 2, respectiv cu 3. Bineinteles, tre sa schimbi valoarea unui 1, 2 sau 3 cand treci prin el pentru a nu trece din nou. Eu le-am inlocuit cu 100001, 100002 si 100003.

Dupa aceea, faci un lee de la fiecare punct din matrice cu 1, care sa treaca doar prin 0-urile din matrice. Apoi iei fiecare punct cu 2 din matrice si verifici daca elementele din sus, stanga, dreapta sau jos sunt 0. Daca unul e 0, actualizezi minimul (daca e cazul), cu ce ai in matricea in care ai facut lee-ul.

Succes!

Desi inainte de chestia cu 1 000 000 aveam o gramada de idei pentru kinetic, dupa aceea s-au dus toate, si am bagat brute-ul  .

Runda a fost foarte reusita, felicitari organizatorilor!

Se poate scrie orice dreapta care intersecteaza toate segmentele?

Ce seamana formula aia cu cea de la aranjamente

Hopa, se vede ca inca n-am facut combinatorica la scoala ).

Este o problema de backtracking pentru BAC.

logic ar fi 6! = 720 ?

sau aranjamente de 6 luate cate 3 ?

Insa , variantele sunt :

a.   180       b. 120          c. 2          d. 18

Pareri ?

Stiu ca la Bac n-ai cum sa faci programul, dar facandu-l, am observat ca raspunsul corect e 120.
Cert e ca sunt permutari (aranjamente nu pot fi, pentru ca nu poti avea 2 prieteni cu acelasi numar), dar nu sunt permutari de N, ci sunt permutari de N pe K locuri [nu stiu daca asta e denumirea corecta].
Sunt aranjamente!!!
Formula descoperita cu ajutorul programului e:
n!/(n-k)!

Motivul pentru care e asa e pentru ca ai mai multe permutari care au acelasi inceput daca luam doar primele 3, dar sunt distincte mai incolo, ca exemplu:
1 2 3 (4 5 6)
1 2 3 (5 4 6)
1 2 3 (6 5 4) ...
Astea se scad de la solutie
Succes!

P.S.: ca sa vezi daca nu cumva ai un element care deja s-a bagat, iti sugerez sa folosesti ori set (bagi elementul in set, si daca deja exista, nu mai il baga inca odata), ori sa folosesti un map (de ce? pentru ca nu are rost sa declari un vector de 1 000 000 000, cand tu ai maxim 100 000 elemente, pe care map-ul ti le pune astfel in memorie incat sa nu ai probleme). Succes

Unde vezi tu 1.000.000.000 in enuntul problemei? eu vad 1.000.000

Oops, imi cer scuze pentru inducerea in eroare. Nu stiu ce am avut la momentul cand am citit problema de am citit asa. In cazul asta merge f. bine si cu un bool de 1 milion. Scuze inca odata :-".