10026 - Shoemaker's Problem

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

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10026 - Shoemaker's Problem

Post by brianfry713 » Tue Sep 17, 2013 9:52 pm

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
Check input and AC output for thousands of problems on uDebug!

Salam!
New poster
Posts: 7
Joined: Tue Sep 10, 2013 7:14 pm

Re: 10026 - Shoemaker's Problem

Post by Salam! » Wed Sep 18, 2013 5:25 pm

Thanks I Got Ac

saju10
New poster
Posts: 8
Joined: Mon Nov 18, 2013 12:09 am

Re: 10026 - Shoemaker's Problem

Post by saju10 » Sun Dec 15, 2013 3:32 pm

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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10026 - Shoemaker's Problem

Post by brianfry713 » Tue Dec 17, 2013 11:16 pm

Change line 19 to:
if(array[max]<array)
Check input and AC output for thousands of problems on uDebug!

ssavi
New poster
Posts: 28
Joined: Thu Nov 20, 2014 9:57 pm

Re:

Post by ssavi » Sat Nov 22, 2014 9:58 am

Jan wrote: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 .
I know I am a Failure Guy . :(

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10026 - Shoemaker's Problem

Post by brianfry713 » Mon Nov 24, 2014 11:55 pm

What do you think the output should be?
Check input and AC output for thousands of problems on uDebug!

ehsanulbigboss
New poster
Posts: 32
Joined: Tue Jul 22, 2014 1:17 am

Re: 10026 - Shoemaker's Problem

Post by ehsanulbigboss » Tue Dec 09, 2014 12:00 am

Why WA?

Code: Select all

Thanks to brianfry713
Last edited by ehsanulbigboss on Thu Feb 05, 2015 9:56 pm, edited 1 time in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10026 - Shoemaker's Problem

Post by brianfry713 » Wed Dec 10, 2014 1:10 am

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.
Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 100 (10000-10099)”