10026 - Shoemaker's Problem

[valkov]

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]

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]

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]

Thanks, Zwergesel.

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

[leonardoferrari]

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 !

[nexodg]

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]

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]

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

Code: Select all

[brianfry713]

Print a newline at the end of the last line.

[arboreal]

Thank you so much! It's solved

[webo]

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.

[brianfry713]

The outputs of two consecutive cases will be separated by a blank line. Don't print an extra blank line at the end.

[webo]

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]

Missing or extra newlines will usually cause WA, don't ever count on getting PE.

[Salam!]

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

Code: Select all

Removed After AC