10959 - The Party, Part I

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

Moderator: Board moderators

Wei-Ming Chen
Experienced poster
Posts: 122
Joined: Sun Nov 13, 2005 10:25 am
Location: Taiwan

10959 - The Party, Part I

Post by Wei-Ming Chen » Sun Nov 13, 2005 10:30 am

I wrote 10959 and got WA.....
Can someone give me some I/O?
thanks...

polone
New poster
Posts: 43
Joined: Sun May 08, 2005 2:31 am
Location: Taiwan

Post by polone » Sun Nov 13, 2005 4:48 pm

Code: Select all

3 3
0 1
1 2
0 2

Code: Select all

1
1

Soarer
New poster
Posts: 14
Joined: Wed Nov 09, 2005 8:17 pm

Post by Soarer » Sun Nov 13, 2005 8:37 pm

Hi, I got WA too, can anyone give some more complicated inputs? Thanks.

Wei-Ming Chen
Experienced poster
Posts: 122
Joined: Sun Nov 13, 2005 10:25 am
Location: Taiwan

Post by Wei-Ming Chen » Mon Nov 14, 2005 7:20 am

Can you give me more output?
My code run this output is right

polone
New poster
Posts: 43
Joined: Sun May 08, 2005 2:31 am
Location: Taiwan

Post by polone » Mon Nov 14, 2005 1:02 pm

Maybe you can post your code :D

Wei-Ming Chen
Experienced poster
Posts: 122
Joined: Sun Nov 13, 2005 10:25 am
Location: Taiwan

Post by Wei-Ming Chen » Mon Nov 14, 2005 2:36 pm

#include <stdio.h>
int main()
{
return 0;
}
Last edited by Wei-Ming Chen on Mon Nov 14, 2005 4:26 pm, edited 2 times in total.

misof
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm

Post by misof » Mon Nov 14, 2005 3:08 pm

First, this line: printf("%d %d %d %d %d %d\n",a[1],a[2],a[3],a[4],a[5],a[6]);
is at least strange and clearly doesn't belong into the final version of your code.

Second, the algorithm is wrong.
Consider the following input:

Code: Select all

1

3 2
1 2
0 1
Here the correct output is

Code: Select all

1
2

Wei-Ming Chen
Experienced poster
Posts: 122
Joined: Sun Nov 13, 2005 10:25 am
Location: Taiwan

Post by Wei-Ming Chen » Mon Nov 14, 2005 3:11 pm

Oh~ That line is check code. I will delete when I submit it.
And why the outputs are 1 & 2
I thought it was 1 & (can't wrote it)

misof
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm

Post by misof » Mon Nov 14, 2005 3:36 pm

Wei-Ming Chen wrote:Oh~ That line is check code. I will delete when I submit it.
And why the outputs are 1 & 2
I thought it was 1 & (can't wrote it)
The order of the dances doesn't matter. Even if 2 danced with 1 before 1 danced with Don Guilianni, the D. G. number of 2 is still 2.

Wei-Ming Chen
Experienced poster
Posts: 122
Joined: Sun Nov 13, 2005 10:25 am
Location: Taiwan

Post by Wei-Ming Chen » Mon Nov 14, 2005 4:25 pm

I thought you are right.
I changed my code and got AC
Thank you

Soarer
New poster
Posts: 14
Joined: Wed Nov 09, 2005 8:17 pm

Post by Soarer » Mon Nov 14, 2005 8:18 pm

Can anyone check it for me? Thanks.

#include<iostream>
#include<math.h>
using namespace std;

int main(){
int num_of_cases, loop = 1;
cin >> num_of_cases;
while(loop <= num_of_cases){

int num_of_people;
long num_of_dance, loop_2 = 1;
cin >> num_of_people >> num_of_dance;

int danced[num_of_people][num_of_people], number[num_of_people];

//initialization
for(int n = 0; n < num_of_people; n++){
number[n] = num_of_people;
}
number[0] = 0;

while(loop_2 <= num_of_dance){
int part_1, part_2;
cin >> part_1 >> part_2;

danced[part_1][part_2] = 1;
danced[part_2][part_1] = 1;

loop_2 ++ ;
}
for(int j = 0; j < num_of_people; j++){
for(int k = 0; k < num_of_people; k++){
if(number[k] == j){
for(int m = 0; m < num_of_people; m++){
if(number[m] > j && danced[k][m] == 1){
number[m] = j+1;
}
}
}
}
}

for(int k = 1; k < num_of_people; k++){
cout << number[k] << endl;
}

loop ++ ;
}
return 0;
}

ayon
Experienced poster
Posts: 161
Joined: Tue Oct 25, 2005 8:38 pm
Location: buet, dhaka, bangladesh

Post by ayon » Fri Nov 18, 2005 9:37 pm

believe it or not, this problem is nothing but bfs; better use bfs, that will make your life easier...
ishtiak zaman
----------------
the world is nothing but a good program, and we are all some instances of the program

Soarer
New poster
Posts: 14
Joined: Wed Nov 09, 2005 8:17 pm

Post by Soarer » Sat Nov 19, 2005 9:14 am

ayon wrote:believe it or not, this problem is nothing but bfs; better use bfs, that will make your life easier...
What is bf?

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Post by Observer » Sat Nov 19, 2005 9:44 am

Soarer wrote:What is bf?
I guess it's not "bf", but "bfs" (Breadth First Search). :wink:
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

ayon
Experienced poster
Posts: 161
Joined: Tue Oct 25, 2005 8:38 pm
Location: buet, dhaka, bangladesh

Post by ayon » Sat Nov 19, 2005 11:23 am

did i write bf? i think it's bfs(breadth first search), not bf(boyfriend).
ishtiak zaman
----------------
the world is nothing but a good program, and we are all some instances of the program

Post Reply

Return to “Volume 109 (10900-10999)”