Zadanie Tetris 3D z OI C++ - złe wyniki

Rejestracja:prawie 10 lat
Ostatnio:około 9 lat
Postów:12

Witam, mam problem z zadaniem Tetris 3D z XIII OI - http://main.edu.pl/pl/archive/oi/13/tet , próbowałem sam to zrobić przed przeczytaniem wzorowego rozwiązania z książeczki. Większość testów jest wykonywana bezbłędnie (w niektórych na mainie zwraca mi program wywłaszczony), ale są 3 testy w jakich mam zły wynik (testy: tet3d, tet4d, tet13b) - są to duże testy i sam sobie nie poradzę, algorytm według jakiego działa program moim zdaniem nie wydaje się być zły, ale zastanawia mnie dlaczego te wyniki są nie takie jak powinny.
Schemat programu wygląda następująco - tworzone jest drzewo na wskaźnikach, następnie dla każdego klocka wyszukiwany jest najwyższy punkt, który potem zwiększam o wysokość danego klocka, potem aktualizuję tą wysokość na całym obszarze na jaki spada klocek.

Kopiuj

 
#include <cstdio>
using namespace std;

// x, y - początek wieżchołka
// d_x, d_y długości klocków
// wielk - wielkość jaką będziemy uzupełniać
short x, y, d_x, d_y;
int wielk;

// struktura drzewa 
// ilosc - przechowuje jaka na danym węźle została zaktualiziwana wysokość
// ilosc_max - jaka wysokość jest masymalna w danym przedziale dla jakiego jest węzeł
// wskaźniki xy - prowadzą do przedziału dla pierwszej połowy z zakresu X i zakresy Y
// tam gdzie większa litera to przedział dla tej zmiennej będzie w większej połowie
// konstruktor odpowiednio zeruje zmienne na 0
struct ss {
	int ilosc;
	int ilosc_max;
	ss *xy, *xY, *Xy, *XY;
	ss() {
		ilosc_max = 0;
		ilosc = 0;
	}
};
// zwraca większą liczbę
int max(int a, int b) {
	if (a > b)
		return a;
	return b;
}

// uzupełnienie na dodawaniu rozgałęzień o mniejszym przedziale pól
void uzupelnij(ss *pocz, short pocz_x, short kon_x, short pocz_y, short kon_y) {
	// tu się nie rozgalezia, bo pole elementarne 1x1
	if (pocz_x == kon_x - 1 && pocz_y == kon_y - 1)
		return;

	else if (pocz_y == kon_y - 1) {
		// jak rozgalezia sia na OX bo Y ma szer 1
		int sr = (pocz_x + kon_x) / 2;

		(*pocz).xy = new ss;
		(*pocz).Xy = new ss;

		uzupelnij((*pocz).xy, pocz_x, sr, pocz_y, kon_y);
		uzupelnij((*pocz).Xy, sr, kon_x, pocz_y, kon_y);
	}

	else if (pocz_x == kon_x - 1) {
		// jak rozgalezia sia na OY bo X ma szer 1
		int sr = (pocz_y + kon_y) / 2;

		(*pocz).xy = new ss();
		(*pocz).xY = new ss();

		uzupelnij((*pocz).xy, pocz_x, kon_x, pocz_y, sr);
		uzupelnij((*pocz).xY, pocz_x, kon_x, sr, kon_y);
	}

	else {
		// jak rozgalezia sią na OX i OY
		int sr_y = (pocz_y + kon_y) / 2;
		int sr_x = (pocz_x + kon_x) / 2;

		(*pocz).xy = new ss;
		(*pocz).Xy = new ss;
		(*pocz).xY = new ss;
		(*pocz).XY = new ss;

		uzupelnij((*pocz).xy, pocz_x, sr_x, pocz_y, sr_y);
		uzupelnij((*pocz).xY, pocz_x, sr_x, sr_y, kon_y);
		uzupelnij((*pocz).Xy, sr_x, kon_x, pocz_y, sr_y);
		uzupelnij((*pocz).XY, sr_x, kon_x, sr_y, kon_y);
	}
}

// znalenienie maxa na danym przedziale polega na przeszukiwaniu
// tylko tych węzłów na których może znajdować się szukany fragment pola,
// na którym chcemy znaleźć maxa
// jak przedział cały zawiera się w polu to bierzemy ilosc_max - bo interesuje
// nas najwyższa wartość, natomiast jak tylko część to bieszemy ilosc,
// bo jeśli ta ilość jest najwyższa to nie znajdziemy jej w mniejszych przedziałach
int max_wysokosc(ss *el, short pocz_x, short kon_x, short pocz_y, short kon_y) {
	// jak fragmencik się zawiera centralnie w przedziale szukanym
	if (x <= pocz_x && kon_x <= x + d_x
		&& y <= pocz_y && kon_y <= y + d_y)
		return (*el).ilosc_max;

	// jak szukamy odpowiednich orzedziałów
	int sr_y = (pocz_y + kon_y) / 2;
	int sr_x = (pocz_x + kon_x) / 2;
	int max_wys = (*el).ilosc;

	// jak pierwszy x i y
	if 	(x < sr_x && y < sr_y)
		max_wys = max(max_wys, max_wysokosc((*el).xy, pocz_x, sr_x, pocz_y, sr_y));

	// jak drugi x i pierwszy y
	if (pocz_x < kon_x - 1
		&& sr_x < x + d_x
		&& y < sr_y)
		max_wys = max(max_wys, max_wysokosc((*el).Xy, sr_x, kon_x, pocz_y, sr_y));

	// jak pierwszy x i drugi y
	if (pocz_y < kon_y - 1
		&& x < sr_x
		&& sr_y < y + d_y)
		max_wys = max(max_wys, max_wysokosc((*el).xY, pocz_x, sr_x, sr_y, kon_y));

	// jak drugi x i y
	if (pocz_y < kon_y - 1 && pocz_x < kon_x - 1
		&& sr_x < x + d_x
		&& sr_y < y + d_y)
		max_wys = max(max_wys, max_wysokosc((*el).XY, sr_x, kon_x, sr_y, kon_y));

	return max_wys;
}

// uzupełnienie obszaru daną wysokością polega na znaleznieniu (taką metodą jak we
// wcześniejszych funkcjach) obszaru który całkowicie podlega pod dany zakres na którym dodajemy
// na takim węźle uzupełniamy ilosc_max i ilosc bo obie te watrtści się zmienią
// na wyżaszch przesziałach dajemy w ilosc_max wyiększą wartość z pośród obecnej ilosci_max i wielkości jaką dodajemy
void uzupelnij_obszar_wielkoscia(ss *el, short pocz_x, short kon_x, short pocz_y, short kon_y) {
	// jak fragmencik się zawiera centralnie w przedziale szukanym
	if (x <= pocz_x && kon_x <= x + d_x
		&& y <= pocz_y && kon_y <= y + d_y) {
		(*el).ilosc = wielk;
		(*el).ilosc_max = wielk;
		return;
	}

	// ustalanie maksymalnej wielkości na weźle i obliczenie śr
	(*el).ilosc_max = max(wielk, (*el).ilosc_max);
	short sr_y = (pocz_y + kon_y) / 2;
	short sr_x = (pocz_x + kon_x) / 2;

	// jak pierwszy x i y
	if (x < sr_x && y < sr_y)
		uzupelnij_obszar_wielkoscia((*el).xy, pocz_x, sr_x, pocz_y, sr_y);

	// jak drugi x i pierwszy y
	if (pocz_x < kon_x - 1
		&& sr_x < x + d_x
		&& y < sr_y)
		uzupelnij_obszar_wielkoscia((*el).Xy, sr_x, kon_x, pocz_y, sr_y);

	// jak pierwszy x i drugi y
	if (pocz_y < kon_y - 1
		&& x < sr_x
		&& sr_y < y + d_y)
		uzupelnij_obszar_wielkoscia((*el).xY, pocz_x, sr_x, sr_y, kon_y);

	// jak drugi x i y
	if (pocz_y < kon_y - 1 && pocz_x < kon_x - 1
		&& sr_x < x + d_x
		&& sr_y < y + d_y)
		uzupelnij_obszar_wielkoscia((*el).XY, sr_x, kon_x, sr_y, kon_y);
}

int main() {
	// wczytanie wiersza z głównymi danymi
	short X, Y, N;
	scanf("%hd%hd%hd", &X, &Y, &N);

	// utworzenie drzewa z korzeniem w pocz
	ss *pocz = new ss();
	uzupelnij(pocz, 0, X, 0, Y);

	// obsługa dodań kolejnych klocków
	int w; // wysokość klocka
	for (int a = 0; a < N; a++) {
		scanf("%hd%hd%d%hd%hd", &d_x, &d_y, &w, &x, &y);
		wielk = max_wysokosc(pocz, 0, X, 0, Y) + w;
		uzupelnij_obszar_wielkoscia(pocz, 0, X, 0, Y);
	}

	// wyświetlenie wyniku
	printf("%d", (*pocz).ilosc_max);

 	return 0;
}

Jeżeli coś źle napisałem to przypadkowo, sam uczę się algorytmiki, C++ też i pewnie mój kod nie jest idealny, ale bardzo proszę o pomoc :)

Tetris.cpp (5 KB) - ściągnięć: 196

Afish 2016-01-09 20:25

Chyba prościej będzie, jeżeli po prostu przeczytasz wzorcówkę z niebieskiej książeczki.

markowanga

2016-01-10 11:16

markowanga2016-01-10 11:16

Rejestracja:prawie 10 lat
Ostatnio:około 9 lat
Postów:12

No dobra, ale czy widzi ktoś błąd w tym drzewie czwórkowym?

_13th_Dragon

2016-01-10 12:29

_13th_Dragon2016-01-10 12:29

Rejestracja:ponad 19 lat
Ostatnio:2 miesiące

Nie wiem jak ci to powiedzieć, od ciebie spodziewano się czegoś w stylu: http://ideone.com/raLvIw

Kopiuj

#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

typedef vector<unsigned> row;

int main()
  {
   unsigned W,H,N;
   cin>>W>>H>>N;
   vector<row> tb(H,row(W));
   while(N--)
     {
      unsigned w,h,z,sx,sy,zmax=0;
      cin>>w>>h>>z>>sx>>sy;
      w+=sx;
      h+=sy;
      for(unsigned y=sy;y<h;++y) for(unsigned x=sx;x<w;++x) zmax=max(zmax,tb[y][x]);
      zmax+=z;
      for(unsigned y=sy;y<h;++y) for(unsigned x=sx;x<w;++x) tb[y][x]=zmax;
     }
   unsigned zmax=0;  
   for(unsigned y=0;y<H;++y) for(unsigned x=0;x<W;++x) zmax=max(zmax,tb[y][x]);
   cout<<zmax<<endl;
   return 0;
  }

Natomiast to co stworzyłeś, to jakiś potwór GMO który nie ma prawa żyć.

Zobacz pozostałe 2 komentarze

Afish 2016-01-10 14:50

Próbuje rozwiązać zadanie przy pomocy drzewa czwórkowego.

_13th_Dragon 2016-01-10 14:59

Rozpoznałeś to z tego kodu czy jednak wiesz co miał próbować zrobić?

Afish 2016-01-10 15:05

Autor sam napisał, że według niego jest to drzewo czwórkowe, kod przypomina ideowo jego implementację, więc można przyjąć, że właśnie tej struktury autor chciał użyć do rozwiązania zadania. Twoje rozwiązanie wygląda na brutala, więc jeżeli twierdzisz, że „spodziewano się czegoś w stylu” Twojego kodu, to chyba nie zrozumiałeś idei OI.

_13th_Dragon 2016-01-10 15:11

Nie przeczytałem tekst, spojrzałem na zadanie i kod - no nie wygląda mi to na drzewo czwórkowe, bardziej na rekursywnego zakodowanego brutala. Na OI bardzo często sensownie napisane brutale przechodzą.

markowanga 2016-01-10 18:21

Jak to nie wygląda na drzewo czwórkowe? Może implementacja nie jest taka jak być powinna (podejrzewam, lepiej by było zrobić tablicę i poruszać się odpowiednio po indeksach a nie wskaźnikach jak ja to robię :P ) ale idea jest taka, że najpierw jestem korzeniu drzewa x∈[0, 10], y∈[0, 10] potem jak poszukuję pola o mniejszych wymiarach to mam od razu odniesienia do czterech pól dzielących ten obszar na mniejszy - na obszary (x∈[0, 5], y∈[0, 5]), (x∈[5, 10], y∈[0, 5]), (x∈[0, 5], y∈[5, 10]), (x∈[5, 10], y∈[5, 10]) to w jak to może przypominać brutala?

Afish

2016-01-10 15:02

Afish2016-01-10 15:02

Rejestracja:prawie 18 lat
Ostatnio:12 dni

markowanga napisał(a):

No dobra, ale czy widzi ktoś błąd w tym drzewie czwórkowym?

Spróbuj ten przykład:

Kopiuj

10 10 2
10 10 1 1 5
1 1 5 5 5

Na moje oko źle porównujesz krawędzie przy ustawianiu maksimum.

edytowany 1x, ostatnio: Afish 2016-01-10 15:05

markowanga 2016-01-10 18:25

po pierwsze dane są złe, bo klocek wychodzi poza plansze gry, wynik wychodzi mi 6 :P

Afish 2016-01-10 18:38

A dobra, pomieszałem indeksy i dlatego mi się nie zgodziło.

markowanga

2016-01-11 21:14

markowanga2016-01-11 21:14

Rejestracja:prawie 10 lat
Ostatnio:około 9 lat
Postów:12

Dobra :P Dalej nie wiem gdzie jest błąd, ale postanowiłem, sobie w wolnej chwili ten kod uprościć, w taki sposób, że przedziałami elementarnymi nie są współrzędne początku i końca a sam nr odcinka od początku (początek == koniec dla współrzędnych X i Y) pozamieniałem warunki w funkcjach i chodzi :D (no za wolne jest nadal niestety), umieszczam kod jakby komuś się przydał xD

Kopiuj

#include <cstdio>
using namespace std;

// x, y - początek wieżchołka
// d_x, d_y długości klocków
// wielk - wielkość jaką będziemy uzupełniać
// wielkości te są odpowiednio zwiększane żeby poupraszczać 
// zakresy w przedziałach -> tak zajmujemy się numerami konkretneych odcinków,
// a nie współrzędnymi (współrzędne początku zwiększamy o 1 a długości skracamy o 1)
short x, y, d_x, d_y;
int wielk;

// struktura drzewa 
// ilosc - przechowuje jaka na danym węźle została zaktualiziwana wysokość
// ilosc_max - jaka wysokość jest masymalna w danym przedziale dla jakiego jest węzeł
// wskaźniki xy - prowadzą do przedziału dla pierwszej połowy z zakresu X i zakresy Y
// tam gdzie większa litera to przedział dla tej zmiennej będzie w większej połowie
// konstruktor odpowiednio zeruje zmienne na 0
struct ss {
	int ilosc;
	int ilosc_max;
	ss *xy, *xY, *Xy, *XY;
	ss() {
		ilosc_max = 0;
		ilosc = 0;
	}
};
// zwraca większą liczbę
int max(int a, int b) {
	if (a > b)
		return a;
	return b;
}

// uzupełnienie na dodawaniu rozgałęzień o mniejszym przedziale pól
void uzupelnij(ss *pocz, short pocz_x, short kon_x, short pocz_y, short kon_y) {
	// tu się nie rozgalezia, bo pole elementarne 1x1
	if (pocz_x == kon_x && pocz_y == kon_y)
		return;

	else if (pocz_y == kon_y) {
		// jak rozgalezia sia na OX bo Y ma szer 1
		int sr = (pocz_x + kon_x) / 2;

		(*pocz).xy = new ss;
		(*pocz).Xy = new ss;

		uzupelnij((*pocz).xy, pocz_x, sr, pocz_y, kon_y);
		uzupelnij((*pocz).Xy, sr + 1, kon_x, pocz_y, kon_y);
	}

	else if (pocz_x == kon_x) {
		// jak rozgalezia sia na OY bo X ma szer 1
		int sr = (pocz_y + kon_y) / 2;

		(*pocz).xy = new ss();
		(*pocz).xY = new ss();

		uzupelnij((*pocz).xy, pocz_x, kon_x, pocz_y, sr);
		uzupelnij((*pocz).xY, pocz_x, kon_x, sr + 1, kon_y);
	}

	else {
		// jak rozgalezia sią na OX i OY
		int sr_y = (pocz_y + kon_y) / 2;
		int sr_x = (pocz_x + kon_x) / 2;

		(*pocz).xy = new ss;
		(*pocz).Xy = new ss;
		(*pocz).xY = new ss;
		(*pocz).XY = new ss;

		uzupelnij((*pocz).xy, pocz_x, sr_x, pocz_y, sr_y);
		uzupelnij((*pocz).xY, pocz_x, sr_x, sr_y + 1, kon_y);
		uzupelnij((*pocz).Xy, sr_x + 1, kon_x, pocz_y, sr_y);
		uzupelnij((*pocz).XY, sr_x + 1, kon_x, sr_y + 1, kon_y);
	}
}

// znalenienie maxa na danym przedziale polega na przeszukiwaniu
// tylko tych węzłów na których może znajdować się szukany fragment pola,
// na którym chcemy znaleźć maxa
// jak przedział cały zawiera się w polu to bierzemy ilosc_max - bo interesuje
// nas najwyższa wartość, natomiast jak tylko część to bieszemy ilosc,
// bo jeśli ta ilość jest najwyższa to nie znajdziemy jej w mniejszych przedziałach
int max_wysokosc(ss *el, short pocz_x, short kon_x, short pocz_y, short kon_y) {
	// jak fragmencik się zawiera centralnie w przedziale szukanym
	if (x <= pocz_x && kon_x <= x + d_x
		&& y <= pocz_y && kon_y <= y + d_y)
		return (*el).ilosc_max;

	// jak szukamy odpowiednich orzedziałów
	int sr_y = (pocz_y + kon_y) / 2;
	int sr_x = (pocz_x + kon_x) / 2;
	int max_wys = (*el).ilosc;

	// jak pierwszy x i y
	if 	(x <= sr_x && y <= sr_y)
		max_wys = max(max_wys, max_wysokosc((*el).xy, pocz_x, sr_x, pocz_y, sr_y));

	// jak drugi x i pierwszy y
	if (pocz_x < kon_x // teraz wiem, że istnieje drugi x
		&& sr_x + 1 <= x + d_x
		&& y <= sr_y)
		max_wys = max(max_wys, max_wysokosc((*el).Xy, sr_x + 1, kon_x, pocz_y, sr_y));

	// jak pierwszy x i drugi y
	if (pocz_y < kon_y
		&& x <= sr_x
		&& sr_y + 1 <= y + d_y)
		max_wys = max(max_wys, max_wysokosc((*el).xY, pocz_x, sr_x, sr_y + 1, kon_y));

	// jak drugi x i y
	if (pocz_y < kon_y && pocz_x < kon_x
		&& sr_x + 1 <= x + d_x
		&& sr_y + 1 <= y + d_y)
		max_wys = max(max_wys, max_wysokosc((*el).XY, sr_x + 1, kon_x, sr_y + 1, kon_y));

	return max_wys;
}

// uzupełnienie obszaru daną wysokością polega na znaleznieniu (taką metodą jak we
// wcześniejszych funkcjach) obszaru który całkowicie podlega pod dany zakres na którym dodajemy
// na takim węźle uzupełniamy ilosc_max i ilosc bo obie te watrtści się zmienią
// na wyżaszch przesziałach dajemy w ilosc_max wyiększą wartość z pośród obecnej ilosci_max i wielkości jaką dodajemy
void uzupelnij_obszar_wielkoscia(ss *el, short pocz_x, short kon_x, short pocz_y, short kon_y) {
	// jak fragmencik się zawiera centralnie w przedziale szukanym
	if (x <= pocz_x && kon_x <= x + d_x
		&& y <= pocz_y && kon_y <= y + d_y) {
		(*el).ilosc = wielk;
		(*el).ilosc_max = wielk;
		return;
	}

	// ustalanie maksymalnej wielkości na weźle i obliczenie śr
	(*el).ilosc_max = max(wielk, (*el).ilosc_max);
	short sr_y = (pocz_y + kon_y) / 2;
	short sr_x = (pocz_x + kon_x) / 2;

	// jak pierwszy x i y
	if (x <= sr_x && y <= sr_y)
		uzupelnij_obszar_wielkoscia((*el).xy, pocz_x, sr_x, pocz_y, sr_y);

	// jak drugi x i pierwszy y
	if (pocz_x < kon_x // teraz wiem, że istnieje drugi x
		&& sr_x + 1 <= x + d_x
		&& y <= sr_y)
		uzupelnij_obszar_wielkoscia((*el).Xy, sr_x + 1, kon_x, pocz_y, sr_y);

	// jak pierwszy x i drugi y
	if (pocz_y < kon_y
		&& x <= sr_x
		&& sr_y + 1 <= y + d_y)
		uzupelnij_obszar_wielkoscia((*el).xY, pocz_x, sr_x, sr_y + 1, kon_y);

	// jak drugi x i y
	if (pocz_y < kon_y && pocz_x < kon_x
		&& sr_x + 1 <= x + d_x
		&& sr_y + 1 <= y + d_y)
		uzupelnij_obszar_wielkoscia((*el).XY, sr_x + 1, kon_x, sr_y + 1, kon_y);
}

int main() {
	// wczytanie wiersza z głównymi danymi
	short X, Y, N;
	scanf("%hd%hd%hd", &X, &Y, &N);

	// utworzenie drzewa z korzeniem w pocz
	ss *pocz = new ss();
	//uzupelnij(pocz, 0, X, 0, Y);
	uzupelnij(pocz, 1, X, 1, Y);

	// obsługa dodań kolejnych klocków
	int w; // wysokość klocka
	for (int a = 0; a < N; a++) {
		scanf("%hd%hd%d%hd%hd", &d_x, &d_y, &w, &x, &y);
		x++;
		y++;
		d_x--;
		d_y--;
		wielk = max_wysokosc(pocz, 1, X, 1, Y) + w;
		uzupelnij_obszar_wielkoscia(pocz, 1, X, 1, Y);
	}

	// wyświetlenie wyniku
	printf("%d", (*pocz).ilosc_max);

 	return 0;
}

Tetris.cpp (6 KB) - ściągnięć: 186

withelm

2016-01-18 11:09

withelm2016-01-18 11:09

Rejestracja:około 15 lat
Ostatnio:około 9 lat

Nie czytałem Twojego rozwiązania.
Jednak samemu zrobiłem je stosując drzewo przedziałowe gdzie w węzłach trzymałem drzewo przedziałowe (incepcja :P).

Jak chcesz o testować czy dobrze napisałeś "pojedyncze" drzewo polecam zadanie "http://main.edu.pl/pl/user.phtml?op=showtask&task=tet&con=ALG". Tylko haczyk jest taki, że w tym zadaniu napisz te drzewo w ładnej klasie.

markowanga 2016-01-18 18:42

Wiem, tam w książeczce jest napisane że w węźle mam mieć 4 wartości a mam 2 i to spowalnia wszystko :P , z tym, że nie wiem jak to użyć, nie rozumiem tego :P

markowanga 2016-01-18 18:44

a co do klas, to wiele przeglądam rozwiązań z OI i klasy tam jeszcze nie widziałem :D

withelm 2016-01-18 19:10

No tak bo to drzewo ma być leniwe, tzn jak cały "obszar" jest zajęty to nie aktualizujesz w dół.

markowanga 2016-01-18 19:33

No ale co? Uzupełniając w dół tylko wydłużam sprawę

Naitoreivun

2016-01-19 00:05

Naitoreivun2016-01-19 00:05

Rejestracja:ponad 10 lat
Ostatnio:prawie 5 lat
Postów:68

Tak jak napisał @withelm najpierw musisz nauczyć się klepać drzewo przedziałowe i to przedział - przedział, czyli wykonujesz coś na przedziale i pytasz o przedział. W tym przypadku to chyba będzie drzewo(max, max). Jeśli chcesz podobne zadanie gdzie wystarczy jedno drzewo a nie drzewo drzew to Koleje z OIa.

Co do materiałów: http://was.zaa.mimuw.edu.pl/?q=node/8 no i niebieskie książeczki :3

Zobacz pozostały 1 komentarz

markowanga 2016-01-19 05:27

Tylko miitłując wydaje mi się że będę miał większą złożonosc

markowanga 2016-01-19 12:31

Dobra - rano zaspany byłem i nie zaczaiłem :P mam zrobić coś takiego jak w koleje tylko na drzewie czwórkowym?

Naitoreivun 2016-01-19 16:08

nie pamiętam dokładnie, zajrzyj do tych materiałów, szczególnie niebieskiej książeczki z omówieniem; na pewno przyda Ci sie drzewo (max, max); w kolejach się używało (+, max);

markowanga 2016-01-19 16:21

No ok, patrzyłem - nie wiem jak sie to moje drzewo nazywa, ale działa podobnie, tylko oni tam jeszcze 2 zmienne dodają do węzłów, których nie rozumiem

Naitoreivun 2016-01-19 16:32

Drzewa przedział - przedział są dość ciężkie do zrozumienia, serio, a do wytłumaczenia jeszcze trudniejsze, więc nie będę się porywał, bo jeszcze coś pomylę. W notatkach na tych wykładach was.zaa.mimuw.edu.pl są w miarę wytłumaczone, w sumie innej lepszej strony nie znalazłem (może słabo szukałem). Ogólnie jedna zmienna nie wystarczy żeby obsłużyć pytanie o przedział i nakładanie na przedział. Dlatego że psuje się gdy np. nałożymy coś na przedział A i pytamy o przedział B, podczas gdy rozkłady na przedziały bazowe A i B są zupełnie różne. No musisz poświęcić kilka godzin ^^

withelm

2016-01-19 20:05

withelm2016-01-19 20:05

Rejestracja:około 15 lat
Ostatnio:około 9 lat

Te dodatkowe zmienne to int i bool. int odpowiada za max wartości na tym przedziale, a bool to jest informacja czy dany przedział jest wypełniony tym maksem.

Gdy wprowadzasz przedział to sprawdzasz czy ten podprzedział pokrywa się z podprzedziałem (drzew) jak tak to już nie wchodzisz głębiej w drzewo a ustalasz bool na true.
Gdy jednak musisz wejść głębiej a dany podprzedział ma flagę true to:

kopiujesz int'a i boola z przedziału <a,b> na <a1, b1>, <a2, b2>.
usuwasz true z przedział <a,b>
Idziesz rekurencją niżej.
Przy powrocie ustalasz <a,b> = max(<a1,b1>, <a2,b2>)

Gdy masz odczytać maksimum z przedziału robisz dokładnie to samo rozbijasz <a,b> na małe podprzedziały <a1,b1> <a2,b2> itd i wyciągasz maksa. Pamiętaj tylko aby sprawdzać boola czy nie oznacza całego przedziału. W takim przypadku nie wchodzisz głębiej

Najłatwiej takie drzewo napisać rekurencyjnie. Funkcje do wprowadzenia i odczytu z przedziału są bardzo podobne do siebie

markowanga 2016-01-19 20:26

wydaje mi się, że moja wersja jest szybsza - bo mam max jaki jest najwyższy w danym przedziale i najniższa wysokośc jaka jest na tym przedziale. Jak szukam wysokości max to wchodzę w mniejsze przedziały i patrzę tylko na wysokość maksymalną, natomiast jak dodaję to wysokość maksymalna to max z wysokości dotychczas i nowej wys, a na przedziale aktualizowanym w minimalnej wys daję nową wys

withelm 2016-01-19 20:39

nie za bardzo rozumiem o co Ci chodzi z minimalną wysokościa :/. Co do złożoności to może się różnić o jakaś stałą <10. Te moje drzewa drzew działa w O(n log^2 (n))

markowanga 2016-01-19 20:59

minimalna wysokość - taką albo wyższą wysokość mają wszystkie punkty w poddrzewie, max - najwyższa wysokość osiągalna przez poddrzewo

Liczba odpowiedzi na stronę

Treść *

Treść

Podgląd

Kliknij, aby dodać treść...

Kliknij, aby dodać załącznik lub wklej ze schowka.

Instrukcja obsługi Markdown

Pomoc 1.18.8

Typografia

Edytor obsługuje składnie Markdown, w której pojedynczy akcent *kursywa* oraz _kursywa_ to pochylenie. Z kolei podwójny akcent **pogrubienie** oraz __pogrubienie__ to pogrubienie. Dodanie znaczników ~~strike~~ to przekreślenie.

Możesz dodać formatowanie komendami , , oraz .

Ponieważ dekoracja podkreślenia jest przeznaczona na linki, markdown nie zawiera specjalnej składni dla podkreślenia. Dlatego by dodać podkreślenie, użyj underline.

Komendy formatujące reagują na skróty klawiszowe: Ctrl+B, Ctrl+I, Ctrl+U oraz Ctrl+S.

Linki

By dodać link w edytorze użyj komendy lub użyj składni [title](link). URL umieszczony w linku lub nawet URL umieszczony bezpośrednio w tekście będzie aktywny i klikalny.

Jeżeli chcesz, możesz samodzielnie dodać link: <a href="link">title</a>.

Wewnętrzne odnośniki

Możesz umieścić odnośnik do wewnętrznej podstrony, używając następującej składni: [[Delphi/Kompendium]] lub [[Delphi/Kompendium|kliknij, aby przejść do kompendium]]. Odnośniki mogą prowadzić do Forum 4programmers.net lub np. do Kompendium.

Wspomnienia użytkowników

By wspomnieć użytkownika forum, wpisz w formularzu znak @. Zobaczysz okienko samouzupełniające nazwy użytkowników. Samouzupełnienie dobierze odpowiedni format wspomnienia, zależnie od tego czy w nazwie użytkownika znajduje się spacja.

Znaczniki HTML

Dozwolone jest używanie niektórych znaczników HTML: <a>, , , <kbd>, <del>, , <dfn>, <pre>, <blockquote>, <hr/>, ,  oraz <img/>.

Skróty klawiszowe

Dodaj kombinację klawiszy komendą notacji klawiszy lub skrótem klawiszowym Alt+K.

Reprezentuj kombinacje klawiszowe używając taga <kbd>. Oddziel od siebie klawisze znakiem plus, np <kbd>Alt+Tab</kbd>.

Indeks górny oraz dolny

Przykład: wpisując H2O i m2 otrzymasz: H₂O i m².

Składnia Tex

By precyzyjnie wyrazić działanie matematyczne, użyj składni Tex.

<tex>arcctg(x) = argtan(\frac{1}{x}) = arcsin(\frac{1}{\sqrt{1+x^2}})</tex>

Kod źródłowy

Krótkie fragmenty kodu

Wszelkie jednolinijkowe instrukcje języka programowania powinny być zawarte pomiędzy obróconymi apostrofami: `kod instrukcji` lub ``console.log(`string`);``.

Kod wielolinijkowy

Dodaj fragment kodu komendą . Fragmenty kodu zajmujące całą lub więcej linijek powinny być umieszczone w wielolinijkowym fragmencie kodu. Znaczniki ``` lub ~~~ umożliwiają kolorowanie różnych języków programowania. Możemy nadać nazwę języka programowania używając auto-uzupełnienia, kod został pokolorowany używając konkretnych ustawień kolorowania składni:

```javascript document.write('Hello World'); ```

Możesz zaznaczyć również już wklejony kod w edytorze, i użyć komendy by zamienić go w kod. Użyj kombinacji Ctrl+`, by dodać fragment kodu bez oznaczników języka.

Tabelki

Dodaj przykładową tabelkę używając komendy . Przykładowa tabelka składa się z dwóch kolumn, nagłówka i jednego wiersza.

Wygeneruj tabelkę na podstawie szablonu. Oddziel komórki separatorem ; lub |, a następnie zaznacz szablonu.

nazwisko;dziedzina;odkrycie
Pitagoras;mathematics;Pythagorean Theorem
Albert Einstein;physics;General Relativity
Marie Curie, Pierre Curie;chemistry;Radium, Polonium

Użyj komendy by zamienić zaznaczony szablon na tabelkę Markdown.

Lista uporządkowana i nieuporządkowana

Możliwe jest tworzenie listy numerowanych oraz wypunktowanych. Wystarczy, że pierwszym znakiem linii będzie * lub - dla listy nieuporządkowanej oraz 1. dla listy uporządkowanej.

Użyj komendy by dodać listę uporządkowaną.

1. Lista numerowana
2. Lista numerowana

Użyj komendy by dodać listę nieuporządkowaną.

* Lista wypunktowana
* Lista wypunktowana
** Lista wypunktowana (drugi poziom)

Składnia Markdown

Edytor obsługuje składnię Markdown, która składa się ze znaków specjalnych. Dostępne komendy, jak formatowanie , dodanie tabelki lub fragmentu kodu są w pewnym sensie świadome otaczającej jej składni, i postarają się unikać uszkodzenia jej.

Dla przykładu, używając tylko dostępnych komend, nie możemy dodać formatowania pogrubienia do kodu wielolinijkowego, albo dodać listy do tabelki - mogłoby to doprowadzić do uszkodzenia składni.

W pewnych odosobnionych przypadkach brak nowej linii przed elementami markdown również mógłby uszkodzić składnie, dlatego edytor dodaje brakujące nowe linie. Dla przykładu, dodanie formatowania pochylenia zaraz po tabelce, mogłoby zostać błędne zinterpretowane, więc edytor doda oddzielającą nową linię pomiędzy tabelką, a pochyleniem.

Skróty klawiszowe

Skróty formatujące, kiedy w edytorze znajduje się pojedynczy kursor, wstawiają sformatowany tekst przykładowy. Jeśli w edytorze znajduje się zaznaczenie (słowo, linijka, paragraf), wtedy zaznaczenie zostaje sformatowane.

Ctrl+B - dodaj pogrubienie lub pogrub zaznaczenie
Ctrl+I - dodaj pochylenie lub pochyl zaznaczenie
Ctrl+U - dodaj podkreślenie lub podkreśl zaznaczenie
Ctrl+S - dodaj przekreślenie lub przekreśl zaznaczenie

Notacja Klawiszy

Alt+K - dodaj notację klawiszy

Fragment kodu bez oznacznika

Alt+C - dodaj pusty fragment kodu

Skróty operujące na kodzie i linijkach:

Alt+L - zaznaczenie całej linii
Alt+, Alt+ - przeniesienie linijki w której znajduje się kursor w górę/dół.
Tab/⌘+] - dodaj wcięcie (wcięcie w prawo)
Shit+Tab/⌘+[ - usunięcie wcięcia (wycięcie w lewo)

Dodawanie postów:

Ctrl+Enter - dodaj post
⌘+Enter - dodaj post (MacOS)

Zadanie Tetris 3D z OI C++ - złe wyniki

markowanga napisał(a):

Smileys & People

Animals & Nature

Food & Drink

Travel & Places

Activities

Objects

Symbols

Typografia

Linki

Wewnętrzne odnośniki

Wspomnienia użytkowników

Znaczniki HTML

Skróty klawiszowe

Indeks górny oraz dolny

Składnia Tex

Kod źródłowy

Krótkie fragmenty kodu

Kod wielolinijkowy

Tabelki

Lista uporządkowana i nieuporządkowana

Składnia Markdown

Skróty klawiszowe