Piratii prin apa au voie sa se deplaseze tot pe cele 8 directii?

Concursul "Simulare CNITV 2"a inceput dar nu se vad probleme, rog si eu un administrator daca poate sa rezolve problema, multumesc mult

Nu uitati cazul cand N = 1

Deci trebuie sa fixez doua puncte A, C(care reprezinta prima diagonala a patrulaterului) , avand cealalta diagonala : B-D. Daca avansez cu C atunci mi se pot intampla trei chestii:
1) avanseaza B-ul sau
2) avanseaza D-ul sau
3)avanseaza B-ul si D-ul
Asa este? Am implementat asa si nu iau decat 10 p

Ok, am inteles, ms, eu defapt intelesesem gresit problema deoarece credeam ca vor veni doar K persoane

Aceasta restrictie nu ne garanteaza doar faptul ca dupa ce un om a intrat in cabina acesta nu mai iese?
Nu inteleg ce legatura are cu exemplul meu

Am si eu o nelamurire:
avem n = 7 si k = 2
1 0 0 0 0 0 1

Cod:

Daca exista cel putin doua cabine adiacente, prima persoana care soseste va alege cabina cu indicele cel mai mare pentru care cabina vecina din dreapta este la randul ei libera

Deci prima persoana ar alege pozitia 5 si apoi a2a persoana poz 3
Dar solutia buna nu ar fi fost: prima pers pe poz 3 si a2a pe poz 4?

Ce inseamna piramida de latura 1? Adica e formata dintr-un singur "1"?

Pai atunci baga-l iar in coada dar ai grija ca sa nu aduni de mai multe ori acelasi drum.
Dupa ce relaxezi vecinii unui nod, NR[nod] = 0 (avand grija sa pastrezi in alt vector valoare NR[nod])

@ Mishu91
Ce vrei sa spui prin faptul ca Bellman ford nu genereaza intotdeauna solutia corecta?

Au ceva special testele 6 si 9? Nu stiu unde gresesc, ma poate ajuta cineva?

Cum fac daca vreau sa aflu cmlsc a 2 siruri si care sa fie maxim din punct de vedere lexicografic?

Nu am dreptul sa decid in cazul celor doi dar am sa va spun parerea mea. Nu cred ca ar trebui luate masuri drastice pentru ca a fost doar un concurs online, iar primii clasatii nu au castigat nimic. Pentru a se evita astfel de situatii ar trebui specificat in regulament ca nu este voie sa se participe in echipa, ci doar individual. Pana si titlul sugereaza participarea in echipa.

Numarul P se da in baza 10 sau in baza B?

vreo sugestie pt rezolvarea in O(N^2) ?
E: Never mind, am rezolvat

Cod:

"3904ms	50952kb	Time limit exceeded." 

Ce naiba?

E:Pt prima varianta de rezolvare din solutii:

Cod:

 Pentru aceasta, mai intai sa luam di = [log h] si dj = [log w]. Numarul cautat este gcd(V[di][dj][i][j], V[di][dj][i][j + w - dj], V[di][dj][i + h - di][dj], V[di][dj][i + h - di][j + w - dj]) 

Nu este cumva corect asa:

Cod:

  gcd(V[di][dj][i][j], V[di][dj][i][j + w - 2^dj], V[di][dj][i + h - 2^di][dj], V[di][dj][i + h - 2^di][j + w - 2^dj])

Motivul pt care cred eu ca trebuie pus 2^dx(x=i sau j)  este deoarece noi ne dorim 4  dreptunghiuri de laturi 2^di si 2^dj care suprapunandu-se sa formeze dreptunghiul cu colturile (i,j),(i+h-1)(j+w-1).

Cod:

 Putem apoi vedea in O(1) care este gcd-ul elementelor din dreptunghiul cu colturile in (i, j), (i + w - 1, j + h - 1) 

Nu trebuia

Cod:

 cu colturile in (i,j) , (i+h-1,j+w-1) 

?

LE: chiar nu raspunde nimeni nimeni?

Am reusit, multumesc mult amandurora

Da, cred ca ai dreptate...dar atunci dc nu iau 100? Ai vreo idee? Folosesc cumva o operatie costisitoare?

Am citit postul lui dar nu prea inteleg cum ajunge la complexitate totala finala O(B-A). Adica ia fiecare nr patrat perfect <=B ( O(sqrtB) ) si pt fiecare face ciur => O(sqrtB * (B-A)/(nr patrat perfect)) . Unde gresesc?

Am rezolvare in O(sqrt B *(B-A)) si iau 60 de pcte cu TLE. Aveti vreo idee unde gresesc?Lucrez pe char de 8 biti.

Cod:

for(i=2;i<=n;i++){ // n=sqrt(b);
		z=i*i;
		if(z<a)
			if(a%z) x=a/z+1;
			else x=a/z;
		else x=1;
		while((long long)z*x<=b){
			rezolva(z*x);
			x++;
		}
	}

Fctia rezolv marcheaza z*x care apartine int[a,b]

Of, nu reusesc sa iau mai mult de 40 de pcte, iau 6 WA-uri, desi nu inteleg unde am gresit. Am complexitatea O(2^N*S) si am facut asa backul recursiv:

Cod:

void back(int k,int w[]){
	for(int i=s[k-1]+1;i<=n;i++){
		s[k]=i;
		int t[S]={1,0};
		for(int j=0;j<=sum-v[i];j++)
			if(w[j]){
				t[j+v[i]]=1;
				sol++;
				if(j && !t[j]) sol++;
				t[j]=1;
			}
			else if(t[j]){
				t[j+v[i]]=1;
				sol++;
			}
		back(k+1,t);
	}
}

Limitele le-am verificat si sunt ok.Imi poate spune cineva unde am gresit? sau poate sa imi dea niste teste ? Ms anticipat


LE:Chiar nu stie nimeni?
LLE: Am rezolvat-o pana la urma

  am luat 100. ms mult wefgef. Tradu-mi si mie mai exact ce face functia f. Din cate inteleg eu e asa:

Cod:

 if(a>=d) return a-d; else return a; 

. Nu cred ca e corect, deoarece pt un exemplu banal nu e echivalent cu modul. ( 7 %3=1 ; f(7)=4 dupa mine) . De cate ori e mai rapida o fctie daca pui inline decat daca nu pui?

Vreo sugestie cum sa scap de TLE? Iau 85 de pcte

pf, ms savime, eu incercasem testul dar credeam ca raspunsul e 4, adica ma gandeam ca trebuie sa gasesc acel drum , dar fara pozitia de plecare..

asa am si facut...dar iau 80 de pcte....am incercat toate testele de pe forum si tot nu gasesc buba....imi puteti da cateva teste dificile?
LE: am scos 90
Am si eu probleme cu testul 7...