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

valkov
New poster
Posts: 20
Joined: Tue Jul 20, 2010 3:11 pm

Re: 10026 - Shoemaker's Problem

Post by valkov » Thu Jul 29, 2010 10:04 am

Just got AC on this problem.
At least for me it was tricky one, because in order to find the ratio I was doing int division :lol:
Good explanation on the problem can be found here : http://www.algorithmist.com/index.php/UVa_10026
You can avoid second comparison (based on the index) by just using stable sort algorithm!
Sample comparison function should contain

Code: Select all

job1.penalty/job1.days > job2.penalty/job2.days

kawsar
New poster
Posts: 12
Joined: Thu Aug 05, 2010 7:40 pm

Re: 10026 - Shoemaker's Problem

Post by kawsar » Sun Aug 08, 2010 4:22 am

Can any one help me to find out , why i getting presentation error ???
several times i submit this code, but every time i got presentation error.
Please help me ...........
Here is my code,

Code: Select all

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


int compair(const void *a, const void *b){
	float *x = (float*)a ;
	float *y = (float*)b ;

	if(*x > *y) return 1 ;
	if(*x < *y) return -1 ;
	return 0;
}


int main(){
	int n, m, x, y, i, j ;
	float a[1000], b[1000] ;
	bool xy[1000] ;

	scanf("%d",&n);
	while(n--){
		scanf("%d",&m);
		memset(xy,true,sizeof(xy));

		for(i=0; i<m; i++){
			scanf("%d %d",&x,&y);
			a[i] = x / (float)y ;
			b[i] = a[i] ;
		}
		qsort(a, m, sizeof(a[0]), compair);


		for(i=0; i<m; i++){
			for(j=0; j<m; j++){
				if(xy[j]){
					if(a[i]==b[j]){
						if(i==0)
							printf("%d",j+1) ;
						else
							printf(" %d",j+1) ;
						xy[j] = false;
					}
				}
			}
		}
		printf("\n");

		if(n > 0)
			printf("\n");
		
	}
	return 0;
}

Zwergesel
New poster
Posts: 11
Joined: Tue Jul 27, 2010 7:29 pm

Re: 10026 - Shoemaker's Problem

Post by Zwergesel » Mon Aug 09, 2010 6:15 pm

Try this testcase:

Code: Select all

1

5
1 1
1 1
1 1
1 1
1 1
Output should be:

Code: Select all

1 2 3 4 5
But your program prints:

Code: Select all

12345

kawsar
New poster
Posts: 12
Joined: Thu Aug 05, 2010 7:40 pm

Re: 10026 - Shoemaker's Problem

Post by kawsar » Tue Aug 10, 2010 11:47 am

Thanks, Zwergesel.

I got accepted.
Thanks for reply....
bye.

leonardoferrari
New poster
Posts: 5
Joined: Mon Mar 14, 2011 4:59 am

Re: 10026 - Shoemaker's Problem

Post by leonardoferrari » Mon Apr 04, 2011 11:06 am

my code looks a lot like kawsar's, but I can't get AC:

Code

Code: Select all

got AC
The input that is not outputting correct :

Code: Select all

20
200 10
190 10
190 9
200 11
199 10
199 11
200 11
200 9
201 9
201 10
201 11
191 9
10000 9999
9999 10000
10000 10000
9999 9999
5 10000
10000 5
5 5
My output:

Code: Select all

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

Code: Select all

17 14 15 16 19 13 6 4 7 11 2 5 1 10 3 12 8 9 18 20
To clear things up, my output is correct (UVA ACCEPTED IT), the problem was, i forgot a cout << endl after every case !

Thanks !
Last edited by leonardoferrari on Tue Apr 05, 2011 9:37 pm, edited 2 times in total.

nexodg
New poster
Posts: 2
Joined: Mon Apr 04, 2011 1:43 am

Re: 10026 - Shoemaker's Problem

Post by nexodg » Mon Apr 04, 2011 3:31 pm

I had that too.

Code: Select all

20
200 10
...
55
its only 19 jobs.

Code: Select all

#include <iostream>
#include <algorithm>

using namespace std;
struct robota
{
    int ktora;//number_of_work
    double srednio;//pay/day.
};

bool operator<(const robota& a, const robota& b) {
    return a.srednio < b.srednio;
}

int main()
{
    int nr,zestaw;
    double temp1,temp2;
    robota temp;
    cin>>zestaw;
    for(int j=0;j<zestaw;j++)
    {
    cin>>nr;
    robota robot[1000];
    for(int i=0;i<nr;i++) 
    {
        cin>>temp1>>temp2;
        robot[i].ktora=i;
        robot[i].srednio=temp2/temp1;
    }
    for(int i=0;i<nr/2;i++)//ive gonna cout in reverse way, so i needed reverse-stability?
    {
        temp=robot[i];
        robot[i]=robot[nr-i-1];
        robot[nr-i-1]=temp;
    }


    stable_sort (robot-1,robot+nr);
     for(int i=nr-1;i>=0;i--)
    {
        cout<<robot[i].ktora+1;
        if(i!=0)
        {
            cout<<" ";
        }
    }
    if(j+1!=zestaw)
    {
    cout<<endl;
    }
    
    }
    cout<<endl;
    return 0;
}


What is wrong which that?

infinlty
New poster
Posts: 1
Joined: Tue Feb 14, 2012 12:41 pm

Re: 10026 - Shoemaker's Problem

Post by infinlty » Tue Feb 14, 2012 12:48 pm

Hi,

I am confused by the phrasing: "If multiple solutions are possible, print the first lexicographically."
What does it mean here? For example, for the input:

Code: Select all

1

10
1 1
2 2
3 3
4 4
5 5
6 6
7 7
8 8
9 9
10 10
the accepted output is

Code: Select all

1 2 3 4 5 6 7 8 9 10
However, my understanding of lexicographical order is

Code: Select all

1 10 2 3 4 5 6 7 8 9
My guess is that it means a stable sorting algorithm is required.

arboreal
New poster
Posts: 2
Joined: Fri Apr 19, 2013 7:32 am

Re: 10026 - Shoemaker's Problem

Post by arboreal » Fri Apr 19, 2013 7:45 am

This is my code. The results should be correct, but I'm keep geting presentation error. Can someone help me?

Code: Select all


Last edited by arboreal on Sat Apr 20, 2013 2:12 am, 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 » Sat Apr 20, 2013 12:33 am

Print a newline at the end of the last line.
Check input and AC output for thousands of problems on uDebug!

arboreal
New poster
Posts: 2
Joined: Fri Apr 19, 2013 7:32 am

Re: 10026 - Shoemaker's Problem

Post by arboreal » Sat Apr 20, 2013 2:11 am

:D Thank you so much! It's solved

webo
New poster
Posts: 2
Joined: Mon Jun 24, 2013 11:57 am

Re: 10026 - Shoemaker's Problem

Post by webo » Mon Jun 24, 2013 12:01 pm

Can somebody come up with a case where my code fails? Or point me as to why I am getting WA.

Code: Select all

Got AC.
Last edited by webo on Tue Jun 25, 2013 12:37 am, 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 » Tue Jun 25, 2013 12:23 am

The outputs of two consecutive cases will be separated by a blank line. Don't print an extra blank line at the end.
Check input and AC output for thousands of problems on uDebug!

webo
New poster
Posts: 2
Joined: Mon Jun 24, 2013 11:57 am

Re: 10026 - Shoemaker's Problem

Post by webo » Tue Jun 25, 2013 12:36 am

Woah, I can't believe it didn't give me PE for that. Kinda ridiculous I spent so much time trying to find a logic error.

Thanks brianfry713.

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 Jun 25, 2013 10:36 pm

Missing or extra newlines will usually cause WA, don't ever count on getting PE.
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! » Tue Sep 17, 2013 9:05 pm

Hey I'm getting Wa on my code
I think my algorithm is correct but ...
plz helppp mee

Code: Select all

Removed After AC
Last edited by Salam! on Wed Sep 18, 2013 5:25 pm, edited 1 time in total.

Post Reply

Return to “Volume 100 (10000-10099)”