Witam, mam problem ze zrozumieniem zadania z kursu: http://main.edu.pl/pl/user.phtml?op=showtask&task=tet&con=ALG
Nie proszę o jego rozwiązanie tylko o jakieś pomocne wskazówki. Np. jaka struktura powinna reprezentować całą platformę, bo gdyby wziąć każdy punt osobno to wychodzi tablica [1000000][20000]. Kurs zrozumiałem, ale jakoś nie potrafię zastosować przedstawionych tam technik. Z góry dziękuję za każdą pomoc.
0
0
Do pamiętania istotnych parametrów wystarczy tablica tab typu int[1000000]. tab[k], to wysokość na której znajduje się najwyżej położony kwadracik nad k.
0
OK, dzięki za pomoc, napisałem program, ale nie wszystko liczy dobrze. W połowie testów jest zła odpowiedź. Może ktoś przeanalizować i powiedzieć co zrobiłem źle:
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int LEN = 1000;
int tab[1000000]; // Liczba/wysokość klocków, które nie objęły całego odcinka
int max_odc[LEN]; // Największa wartość na odcinku
int odc[LEN]; // Liczba klocków, które objęły cały odcinek
int d, n, l, x, iMax, h;
// d - szerokość platformy
// n - liczba klocków
// l - szerokość klocka
// x - pozycja klocka
// iMax - największa wartość w danym przedziale [a, b]
// h- wysokość
void find_max(int a, int b) {
iMax = 0;
while((a % LEN) != 0 && a <= b) {
iMax = max(iMax, tab[a] + odc[a/LEN]);
a++;
}
while((b % LEN) != (LEN - 1) && a <= b) {
iMax = max(iMax, tab[b] + odc[b/LEN]);
b--;
}
while(a <= b) {
iMax = max(iMax, max_odc[a/LEN]);
a += LEN;
}
iMax++;
}
void insert_block(int a, int b) {
while((a % LEN) != 0 && a <= b) {
tab[a] = iMax - odc[a/LEN];
max_odc[a/LEN] = max(max_odc[a/LEN], tab[a] + odc[a/LEN]);
a++;
}
while((b % LEN) != (LEN - 1) && a <= b) {
tab[b] = iMax - odc[b/LEN];
max_odc[b/LEN] = max(max_odc[b/LEN], tab[b] + odc[b/LEN]);
b--;
}
while(a <= b) {
odc[a/LEN]++;
max_odc[a/LEN]++;
a += LEN;
}
}
int main() {
scanf("%d%d", &d, &n);
while(n--) {
scanf("%d%d", &l, &x);
find_max(x, x+l-1);
//cout << "l: " << l << " x: " << x << '\n';
insert_block(x, x+l-1);
iMax > h ? h = iMax : h;
//cout << "h: " << h << '\n';
}
printf("%d", h);
//system("pause");
return 0;
}
0
Twojego algorytmu nie analizowałem dokładnie, wydaje mi się przekombinowany.
Moja wersja:
Spada nowy klocek, lewy koniec to k, prawy to r. Szukam max(tab[i]) dla k<=i<=r. Zwiększam tab[i] o 1 dla k<=i<=r.
Na końcu szukam max(tab[i]) po wszystkich i.
0
Początkowo tak zrobiłem, ale wtedy program nie mieści się w czasie. Musiałem zastosować do tego podział na przedziały, tak jak w ostanim zadaniu przykładowym z kursu: http://main.edu.pl/pl/user.phtml?op=lesson&n=30&page=algorytmika i tu właśnie coś jest nie tak.
0
Odświeżam, proszę o pomoc, bo nie mogę się doszukać błędu w programie, a ciągle źle liczy
0
Nie znalazłem błędu w Twoim algorytmie. Być może jest, ale mam hipotezę. Problemy może stwarzać to, że tablice max_odc oraz odc nie są wyzerowane na początku działania programu. Gdyby było to prawdą, to dla n > 1000 mogą powstawać losowe wyniki. Dlatego zawsze warto przy takich zadaniach na początku wyzerować używane tablice.
Edit: Mam dziwne wrażenie, że zły wynik może powstać także wtedy, gdy maksymalna wysokość wzrosła przy ostatnim klocku. Proponowałbym, by nie liczyć wartości h przy każdym klocku, a dopiero po zakończeniu gry. Wtedy trzeba podać cały przedział 1..n.
Jeszcze jedno, pod koniec edycji znalezione: w C++ numeracja tablic zaczyna się od 0 (czyli numeracja max_odc kończy się na 999 999 oraz odc na 999), zaś w zadaniu od 1 (da nam to numery odpowiednio 1 000 000 oraz 1 000). Przekroczenie zakresu może też tworzyć losowe wyniki. Na Twoim miejscu zwiększyłbym jeszcze zakresy ww. tablic o kilka wartości (nigdy nie zaszkodzi).
0
Wykorzystałem wszystkie Twoje wskazówki (zwiększenie tablic i ich wyzerowanie, sprawdzanie h na końcu poprzez analizę max_odc), ale nic to nie dało. Połowa zadań cięgle źle. Wyniki różnią się dość znacznie np. " wczytano '3485', a oczekiwano '3675' "
0
Cały czas niepokoi mnie fragment:
while(a <= b) {
odc[a/LEN]++;
max_odc[a/LEN]++;
a += LEN;
}
Mam wrażenie, że np. w takiej sytuacji:
- blok segmentów [1,1000] ma maksymalną wysokość 666
- blok segmentów [1001,2000] ma max wysokość 333
- blok segmentów [2001,3000] ma znowu 666
- kładziemy klocek o położeniu [1,3000]
Mam dziwne wrażenie, że wtedy wysokość każdego segmentu po prostu zwiększy się o 1, czyli blok [1001,2000] otrzyma wysokość 334, nie zaś żądane 667.
0
Masz rację, już poprawiłem, ale nadal coś jest nie tak, choć wyniki są już bardziej zbliżone ('3530' zamiast '3675'). Teraz jestem pewny, że coś jeszcze jest w tym fragmencie źle i chyba chodzi o tablicę odc. Gdy klocek zajmuje jakiś cały odcinek to odc[a/LEN] + tab[a] powinno być równe max_odc. Myślałem, żeby zmienić wartość tab[a] i powiększyć ją o te puste pola, ale nic to nie dało. Wyniki nawet pozostają te same
while(a <= b) {
odc[a/LEN]++;
for(int i = a; i < LEN; i++) {
tab[i] = iMax - odc[a/LEN];
}
max_odc[a/LEN] = iMax;
a += LEN;
}
0
Rozwiązanie podane przez Ciebie wyżej raczej nie powinno zmieścić się w czasie przy złośliwych testach.
Myślę obecnie nad taką zmianą:
- wyrzucić tablicę
odc - w tablicy
tabprzechowywać wysokość w danym segmencie (z późniejszym zastrzeżeniem) - w tablicy
max_odcwciąż przechowywać najwyższą wysokość w danym bloku - dodać tablicę bool-ową np.
wypelnioneo rozmiarze LEN. Jeżeli wartość dla i-tego bloku będzie wynosić true, znaczy to, że wszystkie segmenty mają taką samą wysokość (i wtedy posługujemy się tablicąmax_odcdo wyrażenia dowolnej wysokości w tym bloku zamiastodc); false oczywiście na odwrót. Na początku przypisać wtedy każdemu elementowi tablicy true, bo wszystkie segmenty mają w każdym bloku taką samą wysokość (równą 0).
Zauważ, że:
- jeżeli jakiś klocek przykryje cały blok o numerze
i, można ustawićwypelnione[i] = trueorazmax_odc[i] = iMax. I to jest "synonimem" przykrycia całego bloku jednym odcinkiem. - jeżeli klocek zachodzi tylko częściowo na blok
ii już wszystkie wysokości nie są sobie równe, to uaktualniasz tablicęodcdla danego bloku (chybaodc[LEN*i]=max_odc[i], potem tak samo dlaLEN*i+1,LEN*i+2itd. - pętla). Potem zrobiszwypelnione[i] = falsei wszystko jest już gotowe do położenia naszego klocka w danym fragmencie bloku. Zauważ, że dla każdego klocka będziemy musieli robić te czynności nie więcej niż 2 razy - dla każdego końca.
Uff.. rzadko się tak rozpisuję :D
0
Zrobiłem tak jak mówisz choć nie wiem czy dobrze wszystko zrozumiałem. W ostatnim punkcie chyba chodziło Ci o tablicę tab i zamiast max_odc[i] to iMax(wysokość na której jest nowy klocek). Jeszcze bardzie zbliżyłem się wyniku, ale ciągle to nie to (3620' zamiast '3675'). Za to program znacznie przyspieszył. Przedtem przy ostatnim teście ~0,41s, a teraz 0,12s. Oto jak to rozumiem:
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int LEN = 1000;
int tab[1000001];
int max_odc[LEN+1];
bool wypelnione[LEN+1];
int d, n, l, x, iMax, h;
// d - szerokość platformy
// n - liczba klocków
// l - szerokość klocka
// x - pozycja klocka
// h- wysokość
void find_max(int a, int b) {
iMax = 0;
if(wypelnione[a/LEN] == true)
iMax = max_odc[a/LEN];
else
while((a % LEN) != 0 && a <= b) {
iMax = max(iMax, tab[a]);
a++;
}
///////////////////////////////
if(wypelnione[b/LEN] == true)
iMax = max_odc[a/LEN];
else
while((b % LEN) != (LEN - 1) && a <= b) {
iMax = max(iMax, tab[b]);
b--;
}
///////////////////////////////
while(a <= b) {
iMax = max(iMax, max_odc[a/LEN]);
a += LEN;
}
iMax++;
}
void insert_block(int a, int b) {
if((a % LEN) != 0) {
wypelnione[a/LEN] = false;
max_odc[a/LEN] = max(max_odc[a/LEN], iMax);
while((a % LEN) != 0 && a <= b) {
tab[a] = iMax;
a++;
}
}
if((b % LEN) != (LEN - 1)) {
wypelnione[b/LEN] = false;
max_odc[b/LEN] = max(max_odc[b/LEN], iMax);
while((b % LEN) != (LEN - 1) && a <= b) {
tab[b] = iMax;
b--;
}
}
while(a <= b) {
wypelnione[a/LEN] = true;
for(int i = a; i < LEN; i++) {
tab[i] = iMax; }
max_odc[a/LEN] = iMax;
a += LEN;
}
}
int main() {
scanf("%d%d", &d, &n);
for(int i = 0; i < LEN + 1; i++) {
max_odc[i] = 0;
wypelnione[i] = true;
}
for(int i = 0; i < 1000001; i++) {
tab[i] = 0;
}
while(n--) {
scanf("%d%d", &l, &x);
find_max(x, x+l-1);
insert_block(x, x+l-1);
}
for(int i = 0; i <= LEN+1; i++) {
h = max(h, max_odc[i]);
}
printf("%d", h);
return 0;
}
0
Ha!
LEN+1 == 1001 :D
Oczywiście zamiast <= LEN+1 powinno być < n (bo analizujemy wszystkie segmenty od 0 do n-1). Tylko w tym razie musisz zamienić jeszcze fragment while(n--) na odpowiednią pętlę for, żeby pozostawić wartość n nienaruszoną; przykładowo for(int i = 0; i < n; i++) {. Powinno zadziałać.
0
Gdzie powinno być "< n" ? n to jest liczba klocków i nie pasuje to do ostatniej pętli, chyba, że znowu nie rozumiem ;)
0
#include <iostream>
using namespace std;
int main(){
unsigned int d,n,l,x, line=1;
cin>>d>>n; //width platform & number of blocks
bool b,arr[d+1][d+1];
for(int i=0; i<=d; i++)
for(int j=0; j<=d; j++)
arr[i][j]=false;
for(int i=0; i<n; i++){
cout<<line<<endl;
cin>>l>>x; //width block & vertices of the platform block line
do{
for(int j=x; j<=(l+x); j++){
if(arr[line][j]==false){
arr[line][j]=true;
b=true;
arr[line][x]=false;
arr[line][l+x]=false;
}
else{b=false; line++; break;}}
int c=0;
while(b==true && (line-c)>0){
c++;
for(int j=x; j<=(l+x); j++){
if(arr[line-c][j]==false){
arr[line-c][j]=true;
b=true;
arr[line-c][x]=false;
arr[line-c][l+x]=false;
}
else{b=false; break;}}
if(b==true)
for(int j=x; j<=(l+x); j++)
arr[line-(c-1)][j]=false;
else{b=true; break;}
}
cout<<line;
}while(b==false);
}
cout<<line;
return 0;
}
Ja rozwiązałem to tak, ale coś spieprzyłem... :]
0
@mnbvcX nie może być
for(int i = 0; i < n; i++){...} i
for(int i = 0; i < n; i++) {...}
próbowałem i nie działa, a poza tym nie pasuje, bo trzeba sprawdzić wszystkie elementy max_odc.
@:] zmień strukturę danych i algorytm, bo w najgorszym przypadku będziesz mieć tablicę arr[1000001][1000001] co jest niewykonalne.
EDIT: Zauważyłem literówkę w pętli:
for(int i = a; i < (a + LEN); i++) {
tab[i] = iMax;
}
Ale nic to nie dało, wyniki są ciągle złe i do tego program w dwóch ostatnich testach nie mieści się w czasie
EDIT2: W końcu udało mi się to rozwiązać :D Dzięki za pomoc ;)
Zamieszczam listing jakby kogoś interesowało:
#include <cstdio>
#include <algorithm>
using namespace std;
const int LEN = 1000;
int tab[1000000];
int max_odc[LEN];
int podstawa[LEN];
int d, n, l, x, iMax, h;
// d - szerokość platformy
// n - liczba klocków
// l - szerokość klocka
// x - pozycja klocka
// h- wysokość
void find_max(int a, int b) {
iMax = 0;
while((a % LEN) != 0 && a <= b) {
iMax = max(iMax, tab[a]);
iMax = max(iMax, podstawa[a/LEN]);
a++;
}
while((b % LEN) != (LEN - 1) && a <= b) {
iMax = max(iMax, tab[b]);
iMax = max(iMax, podstawa[b/LEN]);
b--;
}
while(a <= b) {
iMax = max(iMax, max_odc[a/LEN]);
a += LEN;
}
iMax++;
}
void insert_block(int a, int b) {
max_odc[a/LEN] = max(max_odc[a/LEN], iMax);
while((a % LEN) != 0 && a <= b) {
tab[a] = iMax;
a++;
}
max_odc[b/LEN] = max(max_odc[b/LEN], iMax);
while((b % LEN) != (LEN - 1) && a <= b) {
tab[b] = iMax;
b--;
}
while(a <= b) {
max_odc[a/LEN] = max(max_odc[a/LEN], iMax);
podstawa[a/LEN] = max_odc[a/LEN];
a += LEN;
}
}
int main() {
scanf("%d%d", &d, &n);
for(int i = 0; i < n; i++) {
scanf("%d%d", &l, &x);
find_max(x, x+l-1);
insert_block(x, x+l-1);
iMax > h ? h = iMax : h;
}
printf("%d", h);
return 0;
}