Page 6 of 11

Posted: Wed Aug 17, 2005 9:04 am
by wdg
I tested it very carfully, but I could not find the wrong place.

Code: Select all

program p105;
var
  cache:array[1..100,1..2] of integer;
  l,h,r,n,size,k,t:integer;
procedure print_n_clear(j:integer);
{ ouput except the nth elements and so on remain; so does clear operation }
var i:integer;
begin
  for i:=1 to j do write(cache[i][1],' ',cache[i][2],' ');
  for i:=j+1 to size do begin
    cache[i-j][1]:=cache[i][1]; cache[i-j][2]:=cache[i][2];
    end;
  size:=size-j;
end;
procedure insert(a,b,loct:integer);
var i:integer;
begin
  for i:=size downto loct do begin
    cache[i+1][1]:=cache[i][1]; cache[i+1][2]:=cache[i][2]; end;
  cache[loct][1]:=a; cache[loct][2]:=b; inc(size);
end;
begin
  fillchar(cache,sizeof(cache),0);
  read(l,h,r); cache[1][1]:=l; cache[1][2]:=h;
  cache[2][1]:=r; cache[2][2]:=0; size:=2;
  while not eof do begin
    read(l,h,r);
    n:=1; while (n<=size) and (l>cache[n][1]) do inc(n);
    if n=size+1 then begin
      print_n_clear(size); cache[1][1]:=l; cache[1][2]:=h;
      cache[2][1]:=r; cache[2][2]:=0; size:=2;
    end
    else begin
      if cache[n-1][2]<h then begin
        if cache[n][1]>r then begin
          insert(r,cache[n-1][2],n); insert(l,h,n);
        end
        else if cache[n][1]<r then begin
          insert(l,h,n); inc(n);
          while (n<=size) and (r>cache[n][1]) do begin
            h:=cache[n][2];
            for k:=n to size-1 do begin
              cache[k][1]:=cache[k+1][1]; cache[k][2]:=cache[k+1][2]; end;
            dec(size); end;
          if n=size+1 then begin cache[n][1]:=r;
            cache[n][2]:=0; inc(size); end
          else insert(r,h,n);
        end
      end
      else if cache[n-1][2]>h then begin
        if cache[n][1]<r then
          if cache[n][2]<h then begin
            t:=cache[n][2]; cache[n][2]:=h; h:=t; inc(n);
            while (n<=size) and (r>cache[n][1]) do begin
              h:=cache[n][2];
              for k:=n to size-1 do begin
              cache[k][1]:=cache[k+1][1]; cache[k][2]:=cache[k+1][2]; end;
              dec(size); end;
            if (n=size+1) then insert(r,0,n)
            else insert(r,h,n);
          end
          else begin
            t:=cache[n][2]; n:=n+1;
            while (n<=size) and (r>cache[n][1]) do begin
              if cache[n][2]<h then begin
                t:=cache[n][2]; cache[n][2]:=h; end;
              inc(n);
            end;
            if n=size+1 then insert(r,0,n)
            else insert(r,t,n);
          end;
      end;
    end;
  end;
  print_n_clear(size);
end.

Posted: Wed Aug 17, 2005 11:08 am
by little joey
As to your first posting:
-sure you need to read all data before you print your answer; you can only calculate the skyline after you know all the buildings.
- I'm not sure how it works in XP (I use Linux), but I think <CTRL>-Z followed by <ENTER> should pass an eof to the program. Personally I prefer to write an input file and pipe it to the program. But with Pascal be carefull with extra blank lines within and at the end of the input.

I have not looked deep into your program, but I think you should rethink and restart from scratch. It is way too complicated (my program is only 17 lines of Pascal). There are only 9999 possible values for the coordinate, so the height of the skyline can be easily stored in an array and adjusted for all buildings.

105 WA? Why?

Posted: Thu Sep 08, 2005 3:35 pm
by Endless
Hi.

Which is the right output to this input:

Code: Select all

1 11 5
2 6 7
3 13 9
12 7 16
14 3 25
19 18 22
23 13 29
24 4 28
28 10 39
39 20 39
39 20 39
40 10 50
100 2 101
101 2 300
300 2 500
500 1 520
510 1 540
541 5 542
542 4 542
550 4 560
My output:

Code: Select all

1 11 3 13 9 0 12 7 16 3 19 18 22 3 23 13 29 10 39 20 39 0 40 10 50 0 100 2 500 1 540 0 541 5 542 0 550 4 560 0

Posted: Sat Sep 17, 2005 1:06 pm
by roni
Out of AC code:

1 11 3 13 9 0 12 7 16 3 19 18 22 3 23 13 29 10 39 20 39 0 40 10 50 0 100 2 500 1 540 0 541 5 542 0 550 4 560 0

105 - The Skyline Problem

Posted: Wed Sep 28, 2005 4:02 pm
by moja
Hello, I don't know in what condition my code will get WA
Could everyone give me some test cases?
Thank you very much!!

The following are test data which I passed.

Code: Select all

input:
0 11 5

output:
0 11 5 0

Code: Select all

input:
3 2 4 
3 1 7 
5 2 6 

output:
3 2 4 1 5 2 6 1 7 0

Code: Select all

input:
1 11 5 
2 6 7 
3 13 9 
12 7 16 
14 3 25 
19 18 22 
23 13 29 
24 4 28 
28 10 39 
39 20 39 
39 20 39 
40 10 50 
100 2 101 
101 2 300 
300 2 500 
500 1 520 
510 1 540 
541 5 542 
542 4 542 
550 4 560

output:
1 11 3 13 9 0 12 7 16 3 19 18 22 3 23 13 29 20 39 20 39 0 40 10 50 0 100 2 500 1 540 0 541 5 542 0 550 4 560 0

Code: Select all

input:
-5 5 1 
1 6 2 
1 2 7 
3 12 10 
4 3 5 
7 5 20 
8 15 12 
11 12 13 
16 14 19 
21 2 22 
23 1 30 
26 10 28 
26 12 27 
32 5 36 
34 3 38 
34 3 40 
37 2 42 
38 2 44 
45 1 46 

output:
-5 5 1 6 2 2 3 12 8 15 12 12 13 5 16 14 19 5 20 0 21 2 22 0 23 1 26 12 27 10 28 1 30 0 32 5 36 3 40 2 44 0 45 1 46 0
The following is my code.

Code: Select all

//* Q105 The Skyline Problem */ 
#include <stdio.h> 

typedef struct _NODE_T
{
    int                h; /* height */
    int                r; /* right */
    struct _NODE_T*    next;
}NODE_T;

NODE_T*    pt_head      = {0};
NODE_T*    pt_tail      = {0};
NODE_T*    pt_free_node = {0};
int        left         = -1;

NODE_T* mymalloc(void)
{
    NODE_T*    pt_node;

    if(pt_free_node != NULL) {
        pt_node      = pt_free_node;
        pt_free_node = pt_free_node->next;
    }
    else {
        pt_node = (NODE_T*)malloc(sizeof(NODE_T));
    }

    return pt_node;
}

void myfree(NODE_T* pt_node)
{
    if(pt_free_node) {
        pt_node->next = pt_free_node;
        pt_free_node  = pt_node;
    }
    else {
        pt_free_node  = pt_node;
        pt_node->next = NULL;
    }
}

/* reduce duplicate item */
void reduce_result(void)
{
    NODE_T*    pt_node;
    NODE_T*    pt_node2;

    for(pt_node = pt_head; pt_node != NULL; pt_node = pt_node->next) {
        if(pt_node->next) {
            if(pt_node->r == pt_node->next->r) {
                if(pt_node->h < pt_node->next->h) {
                    pt_node->h = pt_node->next->h;
                }
                pt_node->next = pt_node->next->next;
            }
        }
    }
}

void calculate(int l, int h, int r) 
{
    NODE_T*    pt_node;
    NODE_T*    pt_node2;
    NODE_T*    pt_node3;

    if(pt_head == NULL) {
        pt_node       = mymalloc();
        pt_node->h    = h;
        pt_node->r    = r;
        pt_node->next = NULL;

        pt_head       = pt_node;
        pt_tail       = pt_node;
        return;
    }

    /* check if left bigger than rightest node */
    if(l > pt_tail->r) {
        pt_node        = mymalloc();
        pt_node->h     = 0;
        pt_node->r     = l;

        pt_node2       = mymalloc();
        pt_node2->h    = h;
        pt_node2->r    = r;

        pt_node->next  = pt_node2;
        pt_node2->next = NULL;

        pt_tail->next  = pt_node;
        pt_tail        = pt_node2;

        return;
    }

    for(pt_node = pt_head; pt_node != NULL; pt_node = pt_node->next) {
        if(l <= pt_node->r) {
            if(h == pt_node->h) {
                if(r <= pt_node->r) { /* new input is under pt_node */
                    return;
                }
                else {
                    l = pt_node->r;
                    continue;
                }
            }
            else if(h < pt_node->h) {
                if(r <= pt_node->r) {
                    return;
                }
                else {
                    l = pt_node->r;
                    continue;
                }
            }
            else {
                if(r == pt_node->r) {
                    pt_node2       = mymalloc();
                    pt_node2->h    = h;
                    pt_node2->r    = r;

                    pt_node2->next = pt_node->next;

                    pt_node->r     = l;
                    pt_node->next  = pt_node2;

                    if(pt_node == pt_tail) {
                        pt_tail = pt_node2;
                    }
                    return;
                }
                else if(r < pt_node->r) {
                    pt_node2    = mymalloc();
                    pt_node2->h = h;
                    pt_node2->r = r;

                    pt_node3    = mymalloc();
                    pt_node3->h = pt_node->h;
                    pt_node3->r = pt_node->r;

                    pt_node->r  = l;

                    pt_node2->next = pt_node3;
                    pt_node3->next = pt_node->next;
                    pt_node->next  = pt_node2;

                    if(pt_node == pt_tail) {
                        pt_tail = pt_node3;
                    }
                    return;
                }
                else {
                    pt_node2      = mymalloc();
                    pt_node2->h   = h;
                    pt_node2->r   = r;

                    pt_node->r    = l;
                    pt_node3      = pt_node->next;

                    pt_node->next = pt_node2;

                    while(pt_node3 != NULL) {
                        if(pt_node3->r > r) {
                            break;
                        }

                        pt_node2->next = pt_node3->next;
                        myfree(pt_node3);
                        pt_node3 = pt_node2->next;
                    }

                    if(pt_node3 == NULL) {
                        pt_tail = pt_node2;
                    }
                    else {
                        pt_node2->next = pt_node3;
                    }

                    return;
                }
            }
        }
    }

    if(h == pt_tail->h) {
        pt_tail->r = r;
        return;
    }

    pt_node       = mymalloc();
    pt_node->h    = h;
    pt_node->r    = r;
    pt_node->next = NULL;

    pt_tail->next = pt_node;
    pt_tail       = pt_node;

    return;
}

void print_result(void)
{
    NODE_T*    pt_node;

    printf("%d", left);
    for(pt_node = pt_head; pt_node != NULL; pt_node = pt_node->next) {
        printf(" %d %d", pt_node->h, pt_node->r);
    }

    printf(" 0\n");
}

int main(void) 
{ 
    int l, h, r;

    while (scanf("%d %d %d", &l, &h, &r)==3) 
    { 
        if(left == -1) {
            left = l;
        }
        calculate(l, h, r);
    } 

    reduce_result();
    print_result();

    return 0;
}

105 why WA?

Posted: Mon Oct 03, 2005 7:13 pm
by wrcstar
This is my code. Why WA?

program Task105;

var skyline : array [0..10000] of integer;
i,l,h,r : integer;
blank : integer;
begin
for i:=0 to 10000 do skyline:=0;
while EoF(input) do begin
ReadLn(l,h,r);
for i:= l to r-1 do
if(skyline < h) then skyline:=h;
end;


blank:=0;
for i:=1 to 10000 do
if(skyline[i-1] <> skyline) then begin
if(blank = 0) then begin
Write(i,' ',skyline);
blank:=blank+1;
end
else Write(' ',i,' ',skyline);
end;


end.

Posted: Sat Oct 08, 2005 8:05 pm
by BJM
For your third case the answer is:

1 11 3 13 9 0 12 7 16 3 19 18 22 3 23 13 29 10 39 0 40 10 50 0 100 2 500 1 540 0 541 5 542 0 550 4 560 0

Not

1 11 3 13 9 0 12 7 16 3 19 18 22 3 23 13 29 20 39 20 39 0 40 10 50 0 100 2 500 1 540 0 541 5 542 0 550 4 560 0

Also, you don't need to worry about negatives since the problem states that all coordinates are positive integers <10,000.

Posted: Thu Nov 17, 2005 11:21 am
by Ming Han

Code: Select all

#include <stdio.h>

int main(){
    
    int dat[5000][4] = {0};
    int c = 0;
    int pos[20010] = {0};
    int i;
    
    while(scanf("%d %d %d",&dat[c][0],&dat[c][1],&dat[c][2])==3){
        for (i=dat[c][0];i<=dat[c][2];i++){
            if (dat[c][1]>pos[i]) pos[i] = dat[c][1];
        }
        c++;
    }
    int last = 0;
    
    
    for (i=dat[0][0];i<=dat[c-1][2]+2;i++){
        if (pos[i]>last){
            printf("%d %d ",i,pos[i]);
            last = pos[i];
        }else if (pos[i]<last){
            if (i==dat[c-1][2]+2) printf("%d %d",(i-1),pos[i]);
            else printf("%d %d ",(i-1),pos[i]); 
            last = pos[i];
        }
    }
    return 0;
}
this is weird! I keep getting PE!

Posted: Tue Dec 06, 2005 1:50 pm
by nukeu666
i need help...dunno why im getting WA

Code: Select all

#include<stdio.h>
int main()
{
  int ht,h[10000],right=0,a,t=0,l[10000],r[10000];
  for(a=0;a<10000;a++)
    h[a]=0;
  while(scanf("%d %d %d",&l[t],&ht,&r[t])==3)
    {
      if(l[t]>right)
        right=l[t];
      if(r[t]>right)
        right=r[t];
      for(a=l[t];a<r[t];a++)
        if(h[a]<ht)
          h[a]=ht;
      t++;
    }
  ht=0;
  for(a=0;a<=right;a++)
    {
      if(h[a]!=h[a+1]&&ht==1)
        printf(" %d %d",a+1,h[a+1]);
      if(h[a]!=h[a+1]&&ht==0)
        {ht=1;printf("%d %d",a+1,h[a+1]);}
    }
}
its working fine for all inputs in this thread

105 Presentation error

Posted: Wed Dec 14, 2005 11:15 am
by gladiatorcn
What is a presentation error?

#include <iostream>
#include <iterator>
#include <algorithm>

using namespace std;

int main()
{
int space[10000], ans[10000];
ostream_iterator<int> outS(cout," ");

fill(space,space+10000,0);

int i,j,h;
while(cin>>i>>h>>j)
{
for(int p=i;p<j;p++)
{
if(h>space[p]) space[p]=h;
}
}

//output
int last=0;
int end=0;
for(int p=1;p<10000;p++)
{
if(space[p]!=last)
{
ans[end++]=p;
ans[end++]=space[p];
last=space[p];
}
}
copy(ans,ans+end,outS);
cout<<endl;

return 0;
}

Posted: Wed Dec 14, 2005 11:44 am
by Evan Tsang
Looks like you have a space after the last 0.

105... Help!

Posted: Fri Feb 17, 2006 2:33 am
by f.eliel
I know these way to read the multiple inputs:

Code: Select all

while (scanf("%d %d %d", &li, &hi, &ri)==3) {
But i don't know how to make it stop reading.
I looked at a lot of topics but i couldn't find it.
Can anyone help me?
Thanks.

Posted: Fri Feb 17, 2006 5:27 am
by f.eliel
I realized tha i was not doing anything wrong, i just didn't the problem...
But now i having trouble in the output. I don't know how to get the space after the last zero of...

Posted: Fri Feb 17, 2006 10:01 am
by ImLazy
I don't understand what you mean. But I know there is no space after the last zero.

105 WA

Posted: Mon Feb 27, 2006 5:12 pm
by f.eliel
I don't understand why i got WA...