Page 8 of 11
Posted: Tue Sep 12, 2006 7:09 am
hi, how are you... for soyoja, there are NO negative numbers in the problem 105

### a clarification about 105 skyline problem

Posted: Sun Dec 03, 2006 12:00 pm
for sample input in the problem is I/o is as follows:

Sample 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

Sample Output:

1 11 3 13 9 0 12 7 16 3 19 18 22 3 23 13 29 0

and my output for the same input sample is :

1 11 3 13 9 0 12 7 16 3 19 18 23 13 29 0

and i got AC How can this be possible My head has stopped working !!!!!!!!! can anybuddy pls explain

Posted: Sun Dec 03, 2006 12:43 pm
This is a problem indeed. Post this problem in the Bugs and suggestions forum.

Posted: Sun Jan 07, 2007 11:21 pm
Print "\n" and you'll get AC

Posted: Thu Jun 28, 2007 9:17 am
Hi people. Can you tell me is it possible to get TLE here?? I got!
Please tell me what's wrong with my code, that makes it TLE:

Code: Select all

``````#include <cstdlib>
#include <iostream>
#include <math.h>

using namespace std;

int main(int argc, char *argv[]) {

int i = 0,l[5005],r[5005],h[5005],n;
while (cin >> l[i] >> h[i] >> r[i])
i++;
n = --i;

float x=-0.5;
int ch=0;

while (x<=r[n]+0.5) {
x += 1.0;
int chmax = ch;
for (i=0;i<=n;i++) {
if ((r[i]==floor(x-0.5))&&(h[i]==ch)) {
chmax = 0;
break;
}
}
for (i=0;i<=n;i++) {
if ((l[i] <= floor (x-0.5))&&(r[i] > floor(x-0.5))&&(h[i]>chmax)) {
chmax = h[i];
}
}

if (chmax != ch) {
cout << floor(x-0.5) << " " << chmax << " ";
ch= chmax;
}
}

return EXIT_SUCCESS;
}

``````

Posted: Thu Jun 28, 2007 11:24 am
If the maximum x coordinate is m, and the building number is n, your algorithm takes O(mn), which is too slow.

----
Rio

Posted: Thu Jun 28, 2007 11:29 am
thanx, rio. BTW, don't you know, is there any way to optimize such an algorithm or I have to think about a new one?

### I keep getting WA..

Posted: Thu Jul 26, 2007 8:10 pm
It works for all test cases here...I even tested for L>R and ignored when L=R. The Code works fine...it organizes the builings by its right and left coordenates..and after it, try to draw a line through its height(it saves the heights at a stack of ordered heights) ...

Code: Select all

``````#include <stdio.h>
#include <stdlib.h>
typedef struct predio{
long int x;
long int y;
struct predio *st;
struct predio *d;
struct predio *e;
}Tpredio;

Tpredio *criaPonto(long int x, long int y, Tpredio *st){
Tpredio *p;
p=(Tpredio*)malloc(sizeof(Tpredio));
(*p).x=x;
(*p).y=y;
(*p).st=st;
(*p).d=NULL;
(*p).e=NULL;
return p;
}
Tpredio* inserePonto(Tpredio *novo,Tpredio *ant, Tpredio *prim){
Tpredio *aux,*aux2;
if ((*novo).x>(*ant).x){
aux2=(*ant).d;
(*novo).d=aux2;
if (aux2!=NULL)
(*aux2).e=novo;
(*novo).e=ant;
(*ant).d=novo;
} else {
aux=ant;
if ((*novo).x==(*ant).x){
if (((*novo).y)>((*ant).y)){
while ((((*aux).e!=NULL) && ((*novo).x==(*((*aux).e)).x)) && ((*novo).y>(*((*aux).e)).y)){
aux=(*aux).e;
}
aux2=(*aux).e;
(*novo).e=aux2;
if (aux2!=NULL)
(*aux2).d=novo;
else
prim=novo;
(*novo).d=aux;
(*aux).e=novo;
}
else {
aux2=(*ant).d;
(*novo).d=aux2;
if (aux2!=NULL)
(*aux2).e=novo;
(*novo).e=ant;
(*ant).d=novo;
}
} else {
while (((*aux).e!=NULL) && ((*novo).x<(*((*aux).e)).x)){
aux=(*aux).e;
}

if (((*aux).e!=NULL) && ((*novo).x==(*((*aux).e)).x)){
if ((*novo).y>(*((*aux).e)).y) {
while ((((*aux).e!=NULL) && ((*novo).x==(*((*aux).e)).x)) && ((*novo).y>(*((*aux).e)).y)){
aux=(*aux).e;
}
}
}
aux2=(*aux).e;
(*novo).e=aux2;
if (aux2!=NULL)
(*aux2).d=novo;
else
prim=novo;
(*novo).d=aux;
(*aux).e=novo;
}
}
return prim;
}

Tpredio *defineAnt(Tpredio *novo,Tpredio *ant){
if ((*novo).x>(*ant).x)
return novo;
if (((*novo).x==(*ant).x) && ((*novo).y<=(*ant).y))
return novo;
else
return ant;
}

Tpredio *insereLista(Tpredio *prim, Tpredio *p){
Tpredio *l,*aux;
l=NULL; aux=NULL;
if (prim==NULL){
l=criaPonto((*p).x,(*p).y,(*p).st);
return l;
} else {
l=prim;
if ((l!=NULL) && ((*p).y<(*l).y)){
while (((*l).d!=NULL) && ((*p).y)<(*((*l).d)).y){
l=(*l).d;
}
aux=criaPonto((*p).x,(*p).y,(*p).st);
(*aux).d=(*l).d;
(*l).d=aux;
return prim;
} else {
aux=criaPonto((*p).x,(*p).y,(*p).st);
(*aux).d=prim;
return aux;
}

}
}
Tpredio *removeLista(Tpredio *prim, Tpredio *p){
Tpredio *l,*aux;
l=prim;
if (l!=NULL){
while (((*l).st!=p) && ((*l).d!=NULL)) {
aux=l;
l=(*l).d;
}
if (((*l).st)==p){
if (l==prim){
aux=(*prim).d;
(*prim).d=NULL;
free(prim);
prim=aux;
} else {
(*aux).d=(*l).d;
(*l).d=NULL;
free(l);
}
}
}
return prim;
}
int main(int argc, char** argv){
long int x1,x2,x3,y,h_max,h_ant,conta,x_prox;
Tpredio *ant,*novo,*prim,*aux,*plista;
conta=0;
novo=NULL;prim=NULL;
while (scanf("%ld %ld %ld",&x1,&y,&x2)!=EOF){
if (x1>x2){
x3=x1;
x1=x2;
x2=x3;
}
if ((x1!=x2) && (y>0)){
if (conta==0){

novo=criaPonto(x1,y,NULL);
ant=novo;
aux=novo;
novo=criaPonto(x2,y,NULL);
prim=aux;
prim=inserePonto(novo,ant,prim);
(*prim).st=novo;
ant=defineAnt(novo,ant);
conta++;
} else {
novo=criaPonto(x1,y,NULL);
prim=inserePonto(novo,ant,prim);
aux=novo;
ant=defineAnt(novo,ant);
novo=criaPonto(x2,y,NULL);
(*aux).st=novo;
prim=inserePonto(novo,ant,prim);
ant=defineAnt(novo,ant);
}}
}
aux=prim;
h_ant=0;
h_max=0;
plista=NULL;
while ((*aux).d!=NULL){
x_prox=(*(*aux).d).x;

if (plista!=NULL)
h_ant=(*plista).y;
else
h_ant=0;

if ((*aux).st==NULL)
plista=removeLista(plista,aux);
else
plista=insereLista(plista,aux);

while (((*aux).d!=NULL)&&(x_prox==(*aux).x)){
aux=(*aux).d;
if ((*aux).st==NULL)
plista=removeLista(plista,aux);
else
plista=insereLista(plista,aux);
if ((*aux).d!=NULL)
x_prox=(*(*aux).d).x;
}

if (plista!=NULL)
h_max=(*plista).y;
else
h_max=0;

if (h_max!=h_ant)
printf("%ld %ld ",(*aux).x,h_max);

if ((*aux).d!=NULL)
aux=(*aux).d;
}
printf("%ld 0\n",(*aux).x);
while ((*aux).e!=NULL){
novo=aux;
aux=(*aux).e;
(*novo).e=NULL;
(*novo).d=NULL;
free(novo);
}
(*aux).e=NULL;
(*aux).d=NULL;
free(aux);
return 0;
}
``````

What am I missing here? If a building such as 1 1 1 exists, what should I print? 1 1 1 0? or nothing? thanks

### 105 Compile error

Posted: Sun Dec 16, 2007 1:57 pm
I got compile error with cpp.
and i got runtime error with java.

two codes are same algorithm...

Code: Select all

``````#include <stdio.h>
#include <stdlib.h>
#include <iostream.h>

class Node {
public:
int point;
int data;
Node(int point, int data) {

this->point = point;
this->data = data;
}

void print() {
printf("%d %d", &point, &data);
while(loc != NULL) {
printf(" %d %d", loc->point, loc->data);
}
}
};

Node* addNode(Node* list, int start, int height, int end) {
Node *add = new Node(start, height);
Node *loc = list;
Node *prev = NULL;
Node *bprev = NULL;

if(list == NULL) {	// Add no element
Node* lastnode = new Node(end, 0);
return list;
}

else if(list->point > start) {	// Add first node
Node* lastnode = new Node(start, height);
}

while(loc != NULL && loc->point < start) {
bprev = prev;
prev = loc;
}
if(bprev!=NULL) {

}
// loc is equal to start or greater.
if(loc == NULL) {		// Last
Node* lastnode = new Node(end, 0);
return list;
}
else if (loc->point == start) {	// loc = start
if(loc->data < height) {		// loc is less than height
loc->data = height;
}
}
else {	// temp != start
if(prev->data < height) {	// height is greater than current height

//Change loc
bprev = prev;
}
}

while(loc != NULL && loc->point <= end) {	// Change mid of start and end
if(loc->data < height) {	// current height is less than new height
loc->data = height;

bprev = prev;
prev = loc;
}
else if(loc->data >= height) {// current height is greater than new height

bprev = prev;
prev = loc;
}
}

// End is null
if(loc == NULL) {
Node* lastnode = new Node(end, 0);
return list;
}
// end point is less than current end
if (loc->point > end) {

Node* lnode = new Node(end, bprev->data);

}
return list;

}

void main()
{
Node* data = NULL;
int start, height, end;
while(scanf("%d %d %d", &start, &height, &end)==3) {
data = addNode(data, start, height, end);
}
data->print();
}
``````

Code: Select all

``````import java.io.*;
import java.util.*;

class Node {
int point;
int data;
Node(int point, int data) {
this.point = point;
this.data = data;
}
public String toString() {
String ret;
ret = Integer.toString(point) + " " + Integer.toString(data);

int bdata = data;

while(temp!=null) {
if(bdata != temp.data)
ret += " " + Integer.toString(temp.point) + " " + Integer.toString(temp.data);
bdata = temp.data;
}
return ret;
}
}

class Sky {
public static Node addNode(Node list, int start, int height, int end) {
Node add = new Node(start, height);
Node loc = list;
Node prev = null;
Node bprev = null;

if(list == null) {	// Add no element
Node lastnode = new Node(end, 0);
return list;
}

else if(list.point > start) {	// Add first node
Node lastnode = new Node(start, height);
}

while(loc != null && loc.point < start) {
bprev = prev;
prev = loc;
}
if(bprev!=null) {

}
// loc is equal to start or greater.
if(loc == null) {		// Last
Node lastnode = new Node(end, 0);
return list;
}
else if (loc.point == start) {	// loc = start
if(loc.data < height) {		// loc is less than height
loc.data = height;
}
}
else {	// temp != start
if(prev.data < height) {	// height is greater than current height

//Change loc
bprev = prev;
}
}

while(loc != null && loc.point <= end) {	// Change mid of start and end
if(loc.data < height) {	// current height is less than new height
loc.data = height;

bprev = prev;
prev = loc;
}
else if(loc.data >= height) {// current height is greater than new height

bprev = prev;
prev = loc;
}
}

// End is null
if(loc == null) {
Node lastnode = new Node(end, 0);
return list;
}
// end point is less than current end
if (loc.point > end) {

Node lnode = new Node(end, bprev.data);

}
return list;

}

public static void main(String[] args) {

Node data = null;

try {
while(true) {
Scanner conIn = new Scanner(System.in);
int start, height, end;
start = conIn.nextInt();
height= conIn.nextInt();
end = conIn.nextInt();

data = addNode(data, start, height, end);
conIn = new Scanner(System.in);
}
}
catch (Exception ee) {
System.out.println(data);
}
}

}
``````

Posted: Fri Dec 21, 2007 11:53 am
When I compile your cpp program I got the following error

Code: Select all

``````c++ pro.cpp -lm -lcrypt -O2 -pipe -DONLINE_JUDGE
In file included from /usr/include/c++/4.1.3/backward/iostream.h:31,
from pro.cpp:3:
/usr/include/c++/4.1.3/backward/backward_warning.h:32:2: warning: #warning This file includes at least one deprecated or antiquated header. Please consider using one of the 32 headers found in section 17.4.1.2 of the C++ standard. Examples include substituting the <X> header for the <X.h> header for C++ includes, or <iostream> instead of the deprecated header <iostream.h>. To disable this warning use -Wno-deprecated.
pro.cpp:114: error: ::main must return int
``````
Changing in function main: void to int

Good luck

### input limit of 105

Posted: Fri Jan 18, 2008 1:06 pm
105 problem description clearly told about positve integers. and my code replys right outputs due to the possible inputs which i got on net but not for negatve co-ordinates. what i should do?

Posted: Sun Jan 20, 2008 9:21 am
Like some people said in other threads, I my AC programs gives
1 11 3 13 9 0 12 17 16 3 19 18 22 3 23 29 0
for the test case stated in the problem.

I solved it by printing the x,y coordinates of the corners in the generated image, which isn't what is described by the problem but it gives an accepted solution.

Posted: Thu Feb 07, 2008 4:38 am
I've made multiple versions of this, even trying to accomodate for the weird AC that shiggy got, but all get WA. This is the version that should accomodate for everything (gives the same output for the test input provided as the problem lists). I am completely stuck and can't find testcases that give this an answer which doesn't make sense.

Code: Select all

``````#include <stdio.h>
int top[20001];
int main() {
int a,a1,b,c,maxc=0;
for (int i = 0; i < 20000; i ++) {
top[i] = 0;
}

scanf("%d %d %d",&a1,&b,&c);
for (int i = 2*a1; i <= 2*c; i++) {
if (b > top[i]) top[i] = b;
}
if (c > maxc) maxc = c;

while (scanf("%d %d %d",&a,&b,&c) != EOF) {
if (c <= a) continue;
for (int i = 2*a; i <= 2*c; i++) {
if (b > top[i]) top[i] = b;
}
if (c > maxc) maxc = c;
}

printf("%d %d",a1,top[2*a1]);
for (int i = 2*a1+2; i <= 2*maxc; i+=2) {
if (top[i] > top[i+1]) {
printf(" %d %d",i/2,top[i+1]);
} else if (top[i-1] < top[i]) {
printf(" %d %d",i/2,top[i]);
}
}

return 0;
}
``````
Can anyone see anything wrong with the logic there?

### 105 RE Need help!

Posted: Wed Feb 27, 2008 6:43 pm
I use a 2-D array as a map to record the building block area
then I check the corner coordinate to gain the vector list

I got the same output as the problem statement.

and I checked the array boundary to see if there are any potential illegal reference, however , I found none.

Can anyone help me?
I would really really appreciate that.

The following is my code

Code: Select all

``````#include <stdio.h>
#define MAX 10002

int main(void)
{
int map[MAX][MAX];
int left,height,right;
int limitL,limitH,limitR;
int vector[MAX*2][2];
int vec_count=0;

int i,j;
for(i=0;i<MAX;i++)
for(j=0;j<MAX;j++)
map[i][j]=0;
for(i=0;i<MAX;i++)
map[0][i]=1;

limitL = MAX-1;
limitR = 1;
limitH = 1;

while( scanf("%d %d %d",&left,&height,&right)==3 )
{
if( left < limitL )
limitL = left;
if( right > limitR )
limitR = right;
if( height > limitH )
limitH = height;

for(i=1;i<=height;i++)
for(j=left;j<right;j++)
{
map[i][j]=1;
}
}

/* printf("%d %d %d\n",limitL,limitH,limitR); */
/* record coordinate into vector array */
for( j=limitL ; j<=limitR ; j++ )
{
i=0;
while( map[i][j] == 1 )
{
i++;
}
vector[vec_count][0]=j;
vector[vec_count][1]=i-1;
vec_count++;
}

/* print vector */
int row = vector[0][1];
printf("%d %d",vector[0][0],vector[0][1]);
for(i=0;i<vec_count;i++)
{
if( vector[i][1] == row )
continue;
row = vector[i][1];
printf(" %d %d",vector[i][0],vector[i][1]);
}
printf("\n");

return 0;
}
``````

### 105 Compilation Error

Posted: Fri Mar 14, 2008 2:07 pm
This is my first problem which i think i have solved

Correction Now This gives Runtime Error
I don't have linux so i can't really test this
Also this works in TurboC

#include<stdio.h>

struct dat
{
int x1;
int h;
int x2;
};
void main()
{
struct dat pos[100];
int arr[500];
int i=0,j,k=1,x;
int sbx1,sbx2,sbh,psbh=0;

while(scanf("%d %d %d",&pos.x1,&pos.h,&pos.x2)==3)
i++;

for(x=0;x<100;x++)
arr[x]=0;

arr[0]=sbx1=pos[0].x1;
arr[1]=sbh=pos[0].h;
arr[2]=sbx2=pos[0].x2;
k=3;
for(j=1;j<i;j++)
{
if(pos[j].x1<sbx2)
{
if(pos[j].x1<sbx1)
{
if(pos[j].x2<sbx2)
{
if(pos[j].h>sbh)
{
if(pos[j].h>psbh)
{
arr[k-3]=pos[j].x1;
arr[k-2]=pos[j].h;
arr[k-1]=pos[j].x2;
arr[k]=sbh;
arr[k+1]=sbx2;
}
else
{
arr[k-2]=pos[j].h;
arr[k-1]=pos[j].x2;
arr[k]=pos[j].h;
arr[k+1]=sbx2;
}
psbh=pos[j].h;
sbx1=pos[j].x2;

}

}
else
{
if(pos[j].h>sbh)
{
if(pos[j].h>psbh)
{
arr[k-3]=pos[j].x1;
arr[k-2]=pos[j].h;
arr[k-1]=pos[j].x2;
sbx1=pos[j].x1;
sbx2=pos[j].x2;
}
else
{
arr[k-2]=pos[j].h;
arr[k-1]=pos[j].x2;
sbx2=pos[j].x2;
}
k=k-2;
sbh=pos[j].h;

}

}

}
else
{
if(pos[j].h>sbh)
{
if(pos[j].x2<sbx2)
{
arr[k-1]=pos[j].x1;
arr[k]=pos[j].h;
arr[k+1]=pos[j].x2;
arr[k+2]=sbh;
arr[k+3]=sbx2;
sbx1=pos[j].x2;
psbh=pos[j].h;
k=k+2;
}
else
{
arr[k-1]=pos[j].x1;
arr[k]=pos[j].h;
arr[k+1]=pos[j].x2;
psbh=sbh;
sbh=pos[j].h;
sbx1=pos[j].x1;
sbx2=pos[j].x2;
}
}
else
{
if(pos[j].x2>sbx2)
{
arr[k]=pos[j].h;
arr[k+1]=pos[j].x2;
sbx1=sbx2;
sbx2=pos[j].x2;
psbh=sbh;
sbh=pos[j].h;
}
else k=k-2;
}

}

}
else
{

arr[k]=0;
psbh=0;
arr[k+1]=pos[j].x1;
arr[k+2]=pos[j].h;
arr[k+3]=pos[j].x2;
sbx1=pos[j].x1 ;
sbx2=pos[j].x2;
sbh=pos[j].h;
k=k+2;
}

k=k+2;
}
printf("\nOUTPUT \n");
for(x=0;x<=k;x++)
{
printf(" %d ",arr[x]);

}

}