10048 - Audiophobia

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

Moderator: Board moderators

deddy one
Experienced poster
Posts: 120
Joined: Tue Nov 12, 2002 7:36 pm

10048 - Audiophobia

Post by deddy one » Thu Apr 17, 2003 3:24 am

Hi I just learn a little bit called floyd warshall and try
to solve 10048, but no luck there, it always WA.
I'll patch the code here, could someone tell me
what went wrong, is my floyd warshall understanding
is wrong or what

thx

[c
cut off because it's just a simple mistake


[/c]
Last edited by deddy one on Thu Apr 17, 2003 7:38 pm, edited 1 time in total.

turuthok
Experienced poster
Posts: 193
Joined: Thu Sep 19, 2002 6:39 am
Location: Indonesia
Contact:

Post by turuthok » Thu Apr 17, 2003 10:24 am

Deddy, ... I haven't solved this problem yet, but I noticed that you will get a WA when there is an input with 0 dB. For some reason, you replaced it with 9999 ... Why don't you fill out with 9999 first and then read the input.

Good luck,

-turuthok-
The fear of the LORD is the beginning of knowledge (Proverbs 1:7).

deddy one
Experienced poster
Posts: 120
Joined: Tue Nov 12, 2002 7:36 pm

Post by deddy one » Thu Apr 17, 2003 5:12 pm

ow, I replaced it with 9999 , so that I will
know when there is no path.

I've tried to fill out 9999 first
but still no luck either.

anyway thx very much for
pointing that I'll get WA for
0 decibels.

Any suggestion what I should do ?

turuthok
Experienced poster
Posts: 193
Joined: Thu Sep 19, 2002 6:39 am
Location: Indonesia
Contact:

Post by turuthok » Thu Apr 17, 2003 6:59 pm

Deddy, perhaps it's the following ...

[c]printf ("Case #%d:\n",++set);[/c]

The output doesn't have ':' there ...

-turuthok-
The fear of the LORD is the beginning of knowledge (Proverbs 1:7).

deddy one
Experienced poster
Posts: 120
Joined: Tue Nov 12, 2002 7:36 pm

Post by deddy one » Thu Apr 17, 2003 7:35 pm

HAHHAHAHAHAHA

oh my goodness
you're right

it get AC now ummm PE actually

thx turuthok

HAVE A NICE DAY :D :lol: :P

zilnus
New poster
Posts: 9
Joined: Sat Mar 08, 2003 11:59 am

10048 WA

Post by zilnus » Mon Sep 08, 2003 11:06 am

I don't know why WA. Is any special test case ?
[c]
int min(int a,int b);
int max(int a,int b);

int main()
{
int weight[100][100],d[100][100],hasil[1000];
int C,S,Q,a,b,berat,i,j,k,kasus = 1;

while (scanf("%d %d %d",&C,&S,&Q))
{
if (!C&&!S&&!Q) break;
for (i=0;i<C;i++)
for (j=0;j<C;j++)
weight[j] = IMP;

for (i=0;i<S;i++)
{
scanf("%d %d %d",&a,&b,&berat);
weight[a-1][b-1] = weight[b-1][a-1] = berat;
}
/* Floyd Warshall */
for (i=0;i<C;i++)
for (j=0;j<C;j++)
d[j] = weight[j];
for (i=0;i<C;i++)
d = 0;
for (k=0; k<C; k++)
for (i=0; i<C; i++)
for (j=0; j<C; j++)
d[j] = min(d[j], max(d[k], d[k][j]));
for (i=0;i<Q;i++)
{
scanf("%d %d",&a,&b);
hasil = d[a-1][b-1];
}
if (kasus > 1) printf ("\n");
printf ("Case #%d\n",kasus);
kasus++;
for(i=0;i<Q;i++)
{
if (hasil == IMP) printf ("no path\n");
else printf ("%d\n",hasil[i]);
}

}
return 0;
}

int min(int a,int b)
{
int x;

if (a < b) x = a;
else x = b;

return x;
}

int max(int a,int b)
{
int x;

if (a > b) x = a;
else x = b;

return x;
}[/c]

Thanx.

changgica
New poster
Posts: 3
Joined: Mon Sep 16, 2002 6:27 pm
Location: Singapore

Re: 10048 WA

Post by changgica » Mon Sep 22, 2003 6:12 pm

zilnus wrote:I don't know why WA. Is any special test case ?
int weight[100][100],d[100][100],hasil[1000];
it should be hasil[10000]
:wink:

ken

udvat
New poster
Posts: 29
Joined: Thu Aug 07, 2003 9:56 pm

10048

Post by udvat » Tue Nov 11, 2003 7:24 pm

** I tried to solve it by floyd's(minimax)
algo.but getting WA again n again. wud anybody plz help me to get the bug?

// code removed
Last edited by udvat on Wed Nov 12, 2003 2:06 pm, edited 1 time in total.

titid_gede
Experienced poster
Posts: 187
Joined: Wed Dec 11, 2002 2:03 pm
Location: Mount Papandayan, Garut

Post by titid_gede » Wed Nov 12, 2003 6:23 am

try this input :

Code: Select all

100 0 1
1 2
0 0 0
output should be :

Code: Select all

Case #1
no path
hope this helps,
-titid gede-
Kalo mau kaya, buat apa sekolah?

udvat
New poster
Posts: 29
Joined: Thu Aug 07, 2003 9:56 pm

got AC

Post by udvat » Wed Nov 12, 2003 2:09 pm

thankx titid. you are right. it was the error in my code. i corrected it and got AC.thank u very much :D

efr_shovo
New poster
Posts: 38
Joined: Wed Sep 22, 2004 9:09 am

10048 Why Run Time Error (SIGSEGV)

Post by efr_shovo » Wed Oct 06, 2004 12:24 pm

Here Is My Code

#include<stdio.h>


int Path[100][100];
int C,S,Q,c1,c2,d,q1,q2;

int Min(int n1,int n2)
{
if(n1<n2)
return n1;
else
return n2;
}

int Max(int n1,int n2)
{
if(n1>n2)
return n1;
else
return n2;
}

void FW()
{
int k,i,j;
for(i=1;i<=C;i++)
Path=0;

for(k=1;k<=C;k++)
for(i=1;i<=C;i++)
for(j=1;j<=C;j++)
Path[j] = Min( Path[j], Max( Path[k], Path[k][j] ) );
}

void main()
{
int i,j,ca=0;
while(1)
{
scanf("%d %d %d",&C,&S,&Q);
if(C<=0||S<=0||Q<=0)
break;

for(i=1;i<=C;i++)
for(j=1;j<=C;j++)
Path[j]=10000;

for(i=1;i<=S;i++)
{
scanf("%d %d %d",&c1,&c2,&d);
Path[c1][c2]=d;
Path[c2][c1]=d;
}

FW(); /* Floyed Warshall Alg Function*/

if(ca>0)
printf("\n");
printf("Case #%d\n",++ca);
for(i=1;i<=Q;i++)
{
scanf("%d %d",&q1,&q2);
if(Path[q1][q2]==10000)
printf("no path\n");
else
printf("%d\n",Path[q1][q2]);
}
}
}


Junayeed
New poster
Posts: 50
Joined: Sat Oct 26, 2002 9:02 am
Location: Dhaka, Bangladesh

Post by Junayeed » Thu Oct 07, 2004 2:49 am

The size of the array is not sufficient. Use 210 instead of 100.

Hope this will work.
Junayeed

efr_shovo
New poster
Posts: 38
Joined: Wed Sep 22, 2004 9:09 am

Post by efr_shovo » Thu Oct 07, 2004 6:58 am

Thanks This Is worked. But Why Array limite 210 instead of 100? Please
Describe me.

jambon_vn
New poster
Posts: 15
Joined: Wed Sep 29, 2004 6:03 am

Post by jambon_vn » Thu Oct 07, 2004 7:17 am

I think you refer to the out size of the array.

int Path[100][100];

You can only use Path[0][0] to Path[99][99].

When C = 100. See the following code (for example)

for(i=1;i<=C;i++) Path=0;

You assign Path[100][100] --> Run Time Error.

You should change to: Path[101][101]. It will be okie, I do not think you have to chane the size of array to 210.

tRipper
New poster
Posts: 22
Joined: Sun Mar 13, 2005 5:04 pm
Location: out there

10048 Audiophobia WA

Post by tRipper » Sun Mar 13, 2005 5:17 pm

I've been trying to get AC on this one for some while but without succes. I use floyd warshall algorithm to find the optimal way between all pairs of vertices in the graph

Code: Select all


/* program audiophobia */
#include <iostream>
#include <climits>

using namespace std;

int max(int a, int b) {
    if (a>b) return a;
    else return b;
}    

int main() {
    int c,s,n,count;
    cin >> c >> s >> n;
    while (c || s || n) {
        int sound[100][100];
        int i,j,k,q;
        int c1,c2,d;
        
        if (count) cout << endl;
        cout << "Case #" << ++count << endl;
        
        //parse
        for (i=0; i<c; i++) 
            for (j=0; j<c; j++) 
                sound[i][j]=INT_MAX;
       
        for (i=0; i<s; i++) {
            cin >> c1 >> c2 >> d;
            sound[c1-1][c2-1]=sound[c2-1][c1-1]=d;
        }    
        
        // floyd-warshall
        for (k=0; k<c; k++ )
            for (i=0; i<c; i++)
                for (j=0; j<c; j++) {
                    q=max(sound[i][k],sound[k][j]);
                    if (q<sound[i][j])
                       sound[i][j]=sound[j][i]=q;
               }   

        //writesol
        for (i=0; i<n; i++) {
            cin >> c1 >> c2;
            if (sound[c1-1][c2-1]<2000000000)
              cout << sound[c1-1][c2-1] << endl;
            else cout << "no path\n";
        }   
   
        cin >> c >> s >> n;
    }    
    return 0;
}  

Post Reply

Return to “Volume 100 (10000-10099)”