## 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

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
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

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

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

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

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

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

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

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

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

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

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

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

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

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

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.