438 Sea2

[•astronomy]

Aici puteţi discuta despre problema Sea2.

[•cos_min]

Nu vor exista doua vase cu aceeasi coordonata x sau aceiasi coordonata y

Asta vrea sa spuna ca nu pot fi teste de genul :

Cod:

3           
1 2
1 3
1 4

sau

Cod:

3
1 2
2 2
3 2

[•pauldb]

Da.

[•cos_min]

Cat ar trebui sa dea pentru :

Cod:

25
42 18468
6335 26501
19170 15725
11479 29359
26963 24465
5706 28146
23282 16828
9962 492
2996 11943
4828 5437
32392 14605
3903 154
293 12383
17422 18717
19719 19896
5448 21727
14772 11539
1870 19913
25668 26300
17036 9895
28704 23812
31323 30334
17674 4665
15142 7712
28254 6869

[•crawler]

Cod:

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

[•Bit_Master]

Cum e posibil ca o functie recursiva in care nu apare absolut in nici un loc in codul ei vre-un apel al unui vector, sa-i modifice totusi valoarea elementelor? Functia nu apeleaza nici o alta functie, decat pe ea, si vectorul respectiv nu e mentionat nicaieri in codul functiei???
O fi problema tot de la MinGW (ruleaza haotic programul)? Am mai patit in MinGW sa-mi rulez programul si sa nu merga nici exemplul, dar cand am trimis nemodificat codul pe infoarena, am luat 100 de puncte.

[•blasterz]

Depinde ce faci in acea functie

sa-ti dau un exemplu:

Cod:

#include <cstdio>

int x[10], y[10];


int main()
{
	for(int i = 1 ;i <= 20; ++i)
		x[i] = i;
	
	printf("%d\n", y[1]);
	
	return 0;
}

vezi ce se intampla

[•Bit_Master]

Depinde ce faci in acea functie

sa-ti dau un exemplu:

Cod:

#include <cstdio>

int x[10], y[10];


int main()
{
	for(int i = 1 ;i <= 20; ++i)
		x[i] = i;
	
	printf("%d\n", y[1]);
	
	return 0;
}

vezi ce se intampla

In acea functie construiesc un arbore si sunt sigur ca nu depaseste.

Cod:

void construire_arb_y_max (int st, int dr, int poz)
{
	if (st == dr)
	{
		frz_arb_y_max[st]=poz;
		return;
	}
	int mij = (st+dr)/2;
	construire_arb_y_max (st,mij,2*poz);
	construire_arb_y_max (mij+1,dr,2*poz+1);
}

void construire_arb_y_min (int st, int dr, int poz)
{
	arb_y_min[poz] = INF;
	if (st == dr)
	{
		frz_arb_y_min[st]=poz;
		return;
	}
	int mij = (st+dr)/2;
	construire_arb_y_min (st,mij,2*poz);
	construire_arb_y_min (mij+1,dr,2*poz+1);
}

Dupa ce apelez construire_arb_y_max, cred ca functia calculeaza bine frunzele in frz_arb_y_max, numai ca pune si niste valori ciudate in frz_arb_y_min (cam jumatate din cele din max).
Cand apelez construire_arb_y_min, se formeaza valorile din frz_arb_y_max, numai cu o pozitie mai in fata (si fara prima valoare). Astfel, cand ajunge sa calculeze ultima frunza in frz_arb_y_min, crapa.

[•blasterz]

vectorul frz_arb_y_min de cat l-ai alocat?

[•Bit_Master]

Ambii de marime 524288 (2^19)
Daca-i declar 1<<20 (2^20), crapa altfel (alt cod de iesire din program).

_________________________________

Pana la urma cred ca am aflat care era problema...

[•assa98]

am si eu o problema. folosesc set-uri din STL (e prima oara, dar trebuia sa le invat odata) . am un set de structuri (x,y) care este sortat crescator dupa x. la problema aceasta  elementele din set vor fi sortate si descrescator dupa y. cum pot sa caut binar in functie de y?

[•paunmatei7]

Cu upper_bound  sau lower_bound
asa se foloseste :
#include <iostream>
#include <set>

int main ()
{
  std::set<int> myset;
  std::set<int>::iterator itlow,itup;

  for (int i=1; i<10; i++) myset.insert(i*10); // 10 20 30 40 50 60 70 80 90

  itlow=myset.lower_bound (30);                //       ^
  itup=myset.upper_bound (60);                 //                   ^

  myset.erase(itlow,itup);                     // 10 20 70 80 90

  std::cout << "myset contains:";
  for (std::set<int>::iterator it=myset.begin(); it!=myset.end(); ++it)
    std::cout << ' ' << *it;
  std::cout << '\n';

  return 0;
}