273 - Jack Straws

All about problems in Volume 2. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Jordan Gordeev
New poster
Posts: 14
Joined: Tue Nov 12, 2002 6:04 pm
Location: Bulgaria

Incorrect problem description (probem 273)

Post by Jordan Gordeev »

I think that the description of problem 273 is wrong.
It states that 1 < n < 13, but when I sent my solution, I received Runtime Error.
When I enlarged my arrays to hold more than 12 sticks, I got Wrong Answer.
Then I submitted a solution that would go into an endless loop if n is not between 1 and 13, and I got Time Limit Exceeded (the endless loop was entered).
It is also possible that the test data is incorrect, not the problem description.

Administrators' comments will be appreciated.
Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski »

I don't think so ....
In my opinion IO for this problem is OK . But I don't know, do you see that is multiply input problem ? Maybe it's your problem Jordan ?

Dominik
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)
eloha
New poster
Posts: 38
Joined: Thu Oct 31, 2002 8:24 am
Location: Taiwan

273 - Jack Straws

Post by eloha »

I always got WA for this problem.
Please tell me the output for the follow input. Thanks.

Code: Select all

1

2
2 76 99 85
61 85 86 48
2 1
0 0
Adil
Learning poster
Posts: 57
Joined: Sun Sep 29, 2002 12:00 pm
Location: in front of the monitor :-)
Contact:

Post by Adil »

Hello. my AC prog gives this output:
CONNECTED
hope this helps.
Runtime_Error
New poster
Posts: 5
Joined: Sat Oct 05, 2002 8:01 pm
Location: Yerevan, Armenia
Contact:

273 (Jack Straws)

Post by Runtime_Error »

whats wrong with my code? i got WA after 0,184 sec working!
is there any trick in this problem?

help please :)
Last edited by Runtime_Error on Sun May 11, 2003 10:52 pm, edited 1 time in total.
A Runtime Error Has Occured, Do You Wish To Debug?
Dmytro Chernysh
Experienced poster
Posts: 146
Joined: Sat Apr 26, 2003 2:51 am

Here you are..

Post by Dmytro Chernysh »

Take a look at
http://www.csie.ntu.edu.tw/~b88062/acm/acmsource.html
and find the tests to this problem...
Runtime_Error
New poster
Posts: 5
Joined: Sat Oct 05, 2002 8:01 pm
Location: Yerevan, Armenia
Contact:

thank you

Post by Runtime_Error »

thanks for you help :D i got AC now :wink:
A Runtime Error Has Occured, Do You Wish To Debug?
Jemerson
Learning poster
Posts: 59
Joined: Mon Feb 02, 2004 11:19 pm
Contact:

CAN'T UNDERSTAND

Post by Jemerson »

Hi guys, in the mentioned input above, which is the official one, there are some cases that my program just can't satisfy and i'm getting wrong answer all time.
I've already drawn the case and saw that the suggested output is impossible!

Can anyone please try this?

Code: Select all

1

8
2 76 99 85
62 96 29 98
8 2 64 50
95 87 16 72
8 90 43 9
61 90 87 20
83 6 34 89
61 85 86 48
4 2
6 2
The output suggested shows the following:

Code: Select all

CONNECTED
CONNECTED
But it really doesn't make sense since line 2 has no connection with any other line! Can someone please help me?

Thanx in advance
UFCG Brazil - Computer Science graduate student
http://acm.uva.es/problemset/usersnew.php?user=54806 ... and going up!
asif_rahman0
Experienced poster
Posts: 209
Joined: Sun Jan 16, 2005 6:22 pm

273

Post by asif_rahman0 »

thnx sohel vai... mone hoi i was sleeping ;).
really stupid. so silly mistake.
have to do it by pencil and paper.
and also got it accepted
:)
Last edited by asif_rahman0 on Sat Jun 17, 2006 10:00 pm, edited 1 time in total.
asif_rahman0
Experienced poster
Posts: 209
Joined: Sun Jan 16, 2005 6:22 pm

Post by asif_rahman0 »

can someone tell me now that am i correct about my theory or not??
just tell me.ok
otherwise i will be trouble in future.
so plz help me:)
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

pan - paper..

Post by sohel »

You have two line segments:

L1 - (0, 0) - (2, 2)
L2 - (1, 1) - (3, 3)

Get a pen and a paper.
Draw these two line-segments with two different colored pens.
You will realize why these two intersect and hence why 1 and 2 are connected... :wink:

Hope it clears your confusion.
Hecton
New poster
Posts: 4
Joined: Sat Oct 06, 2007 3:38 pm

Could anyone check my code for me? for 273!!

Post by Hecton »

I tested it with the inputs that I can find and all passed!
so what't wrong with it...Plz help! thx!

Code: Select all

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

struct rod
    {
        int x1;
        int y1;
        int x2;
        int y2;     
    };
struct rod t[13];  
int map[13][13];


int main(void)
{
    int dataset  = 0;/* how many testing datasets*/
    int rodnumber= 0;
    int x        = -1;
    int y        = -1;
    int a=0,b=0,c=0;
    int a1=0,b1=0,c1=0;
    int i=0,j=0,k=0,h=0,t1=0,t2=0;
    int u1=0,u2=0,u3=0,u4=0;
    for (i = 0; i < 13; i++)
      {
        t[i].x1 = -1;
        t[i].y1 = -1;
        t[i].x2 = -1;
        t[i].y2 = -1;
        for (j = 0; j < 13; j++)
           map[i][j] = -1;
      }    


scanf( "%d" , &dataset );
for (h = 0;h < dataset;h++)
{        
    /* initialization */
    for (i = 0; i < 13; i++)
      {
        t[i].x1 = -1;
        t[i].y1 = -1;
        t[i].x2 = -1;
        t[i].y2 = -1;
        for (j = 0; j < 13; j++)
           map[i][j] = 0;
      }    
    scanf("%d",&rodnumber);
    /* read in rod's coordinates*/
    for (i = 0; i < rodnumber; i++)
      scanf("%d %d %d %d",&t[i].x1,&t[i].y1,&t[i].x2,&t[i].y2);
 
      
   
    /*set up connetion table*/   
    k = 0;j = 0; t1 = 0; t2 = 0;    
    for ( k = 0; k < rodnumber; k++)   
      {
         /* see the relative positon of x,y of t[k] rod*/
           
           a = -(t[k].x2 - t[k].x1);
           b = t[k].y2 - t[k].y1; 
           c = (b*t[k].x1 + a*t[k].y1);
           
          /*t[j] for checking, t[k] for ref. */
           for ( j = 0; j < rodnumber; j++)
             {
               a1 = -(t[j].x2 - t[j].x1);
               b1 = t[j].y2 - t[j].y1; 
               c1 = (b1*t[j].x1 + a1*t[j].y1);
              
               t1 = (b*t[j].x1 + a*t[j].y1 - c)*(b*t[j].x2 + a*t[j].y2 - c);
               t2 = (b1*t[k].x1 + a1*t[k].y1 - c1)*(b1*t[k].x2 + a1*t[k].y2 - c1);
               u1 = (b*t[j].x1 + a*t[j].y1 - c);
               u2 = (b*t[j].x2 + a*t[j].y2 - c);
              /* t1: substitute t[j] into t[k]'s equation
                  t2:            t[k] into t[j]'s equation
               */
             
           
               if (t1 <= 0 && t2 <= 0) /*if on the line equation*/ 
                {          
                           
                  /* two possible case: */
                  if ( t1 == 0 && t2 == 0)
                  {
                    if ( u1 == 0)
                        {
                                           
                             if (t[j].x1 < t[k].x1 && t[j].x1 < t[k].x2 && t[j].y1 < t[k].y1 && t[j].y1 < t[k].y2)
                                 continue;
                                       
                             if (t[j].x1 > t[k].x1 && t[j].x1 > t[k].x2 && t[j].y1 > t[k].y1 && t[j].y1 > t[k].y2)
                                 continue;              
                                
                             if (t[j].x1 == t[k].x1 && t[j].x2 == t[k].x2)                        
                               if ((t[j].y1 > t[k].y1 && t[j].y1 > t[k].y2) || (t[j].y1 < t[k].y1 && t[j].y1 < t[k].y2))
                                   continue;          
                           
                             if (t[j].y1 == t[k].y1 && t[j].y2 == t[k].y2)                        
                               if ((t[j].x1 > t[k].x1 && t[j].x1 > t[k].x2) || (t[j].x1 < t[k].x1 && t[j].x1 < t[k].x2))
                                   continue;          
                                   
                        }

                       if (u2 == 0)
                        {
                          if (t[j].x2 < t[k].x1 && t[j].x2 < t[k].x2 && t[j].y2 < t[k].y1 && t[j].y2 < t[k].y2)
                              continue;
                                       
                          if (t[j].x2 > t[k].x1 && t[j].x2 > t[k].x2 && t[j].y2 > t[k].y1 && t[j].y2 > t[k].y2)
                              continue;     
                              
                          if (t[j].x1 == t[k].x1 && t[j].x2 == t[k].x2)                        
                               if ((t[j].y2 > t[k].y1 && t[j].y2 > t[k].y2) || (t[j].y2 < t[k].y1 && t[j].y2 < t[k].y2))
                                   continue;          
                           
                             if (t[j].y1 == t[k].y1 && t[j].y2 == t[k].y2)                        
                               if ((t[j].x2 > t[k].x1 && t[j].x2 > t[k].x2) || t[j].x2 < t[k].x1 && t[j].x2 < t[k].x2)
                                   continue;               
                        }                    
                    
                  }    
                  /* make connection */
                  map[k][j] = 1;
                  map[j][k] = 1;
                }         
            }               
      }
     for( k=0 ; k<rodnumber ; ++k )
		for( i=0 ; i<rodnumber ; ++i )
			for( j=0 ; j<rodnumber ; ++j )
				if( i!=j&&map[i][k]&&map[k][j] ) map[i][j] = 1 ;
    while (1)
        {
          scanf("%d %d",&x,&y);               
          if (x == 0 && y == 0) break;
          if (map[x-1][y-1])
            puts( "CONNECTED" ) ;
	      else 
            puts( "NOT CONNECTED" ) ;
          
         }/*outer while*/
       if (h + 1) printf("\n");
                
}/*h for*/
/*}/*Most Outer while*/
return 0;


}

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan »

Edit : My code was wrong!!!
Last edited by Jan on Tue Oct 09, 2007 12:16 am, edited 1 time in total.
Ami ekhono shopno dekhi...
HomePage
Hecton
New poster
Posts: 4
Joined: Sat Oct 06, 2007 3:38 pm

Post by Hecton »

Sorry, I have a question. Line segment 6 overlaps all other line

segments. So the outputs should be "CONNECTED". Is that

ight? Or complete overlap of two lines does;nt constitue a

path to other line segments?
Jan wrote:Try the cases below:

Input:

Code: Select all

1

6
1 1 2 2
0 0 1 1
2 2 3 3
3 3 4 4
5 5 6 6
0 0 10 10
1 2
1 3
1 4
1 5
1 6
2 3
2 4
2 5
2 6
3 4
3 5
3 6
4 5
4 6
5 6
0 0
Output:

Code: Select all

CONNECTED
CONNECTED
CONNECTED
NOT CONNECTED
NOT CONNECTED
CONNECTED
CONNECTED
NOT CONNECTED
NOT CONNECTED
CONNECTED
NOT CONNECTED
NOT CONNECTED
NOT CONNECTED
NOT CONNECTED
NOT CONNECTED
Hope these help.
Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan »

If you can find a common point in boh lines then you can say they are connected.
Ami ekhono shopno dekhi...
HomePage
Post Reply

Return to “Volume 2 (200-299)”