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:
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...