10026 - Shoemaker's Problem

[brianfry713]

input

Code: Select all

2

4
3 4
1 1000
2 2
5 5

4
3 4
1 1000
2 2
5 5

output should be

Code: Select all

2 1 3 4

2 1 3 4

[Salam!]

Thanks I Got Ac

[saju10]

why wrong ans....here is my code

Code: Select all

#include<stdio.h>
int main()
{
    double a,b,array[1003];
    int text,n,i,j;
    scanf("%d",&text);
    while(text--)
    {
        scanf("%d",&n);
        for(i=1;i<=n;i++)
        {
            scanf("%lf%lf",&a,&b);
            array[i]=b/a;
        }
        for(j=1;j<=n;j++)
        {
            int max=0;
            for(i=1;i<=n;i++)
                if(double(max)<array[i])
                    max=i;
            array[max]=0;
            if(j<n)
                printf("%d ",max);
            else
                printf("%d\n",max);
        }
        if(text!=0)
        printf("\n");
    }
    return 0;
}

[brianfry713]

Change line 19 to:
if(array[max]<array)

[ssavi]

My accepted code returns...

Output:

Code: Select all

1 2 3 4 5 6 7 8 9 10

4 1 2 3 5

1 2 3 4 5

1 2 3 4 5 6

10 8 6 2 4 1 3 5 7 9

2 4 6 8 10 1 3 5 7 9

2 1 4 6 3 8 10 5 7 9

17 14 15 16 19 13 6 4 7 11 2 5 1 10 3 12 8 9 18 20

Hope it helps.

I Don't understand the 4th output ... Can You please explain the 4th one . As far i can guess subtraction from b to a is the answer . and then sort it . But it doesn't match this case .

[brianfry713]

What do you think the output should be?

[ehsanulbigboss]

Why WA?

Code: Select all

Thanks to brianfry713

[brianfry713]

Try the random input at:
http://www.udebug.com/UVa/10026

You are losing precision in these lines:
f = ((double)b/(double)a)*10000;
array = orginal = (int)f;

Either keep the ratio as a double or if you want to use integer then use rational math.