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

Mohammad Mahmudur Rahman
Experienced poster
Posts: 154
Joined: Sat Apr 17, 2004 9:34 am
Location: EEE, BUET

Post by Mohammad Mahmudur Rahman » Mon Jun 13, 2005 3:51 pm

Hey, I've just got AC. I must confess that it was really a strange fault. I had been submitting it with a wrong problem number & started cracking my brain figuring out the error. :D. Such a stupidity.... :oops:
You should never take more than you give in the circle of life.

xinmeng
New poster
Posts: 2
Joined: Thu Oct 26, 2006 2:18 pm

10026 runtime error help!

Post by xinmeng » Sat Nov 04, 2006 7:55 pm

I compile and run my program. It solves ok and gives the correct answer on my computer. but, ACM gives me runtime error, the error message is Invalid memory reference. I cannot see where the error is. Can anyone help me or give me some test data? My main idea is to calculate the fine of all the permutations, find the smallest one.

#include <iostream>
using namespace std;

int count=0;
inline void swap( int & a, int & b){
int temp = a;
a = b;
b = temp;
}
void Perm( int a[], int k, int m, int ** array ){
// generate all permutations of list[ k:m ]
int i;
if( k == m ){
for( i = 0; i <=m; i++ )
array[count]= a[ i ];
count++;
}
else{
for( i = k; i <= m; i++ ){
swap( a[ k ], a[ i ] );
Perm( a, k+1, m,array );
swap( a[ k ], a[ i ]); // restore back to the original sequence
}
}
}

int main() {
int cases,n,i,t,k,j,tfine,min,mindex;
cin>>cases;
while(cases){
min=0;
mindex=0;
cases--;
t=1;
tfine=0;
cin>>n;
int *time=new int[n];
int *fine=new int[n];
for (i=0;i<n;i++)
cin>>time>>fine;
for (i=2;i<=n;i++)
t*=i;
int **atime=new int*[t];
for (i=0;i<t;i++)
atime=new int[n];
int **afine=new int*[t];
for (i=0;i<t;i++)
afine=new int[n];
count=0;
Perm(time,0,n-1,atime);
count=0;
Perm(fine,0,n-1,afine);

for (j=0;j<n;j++){
for (k=j+1;k<n;k++)
min+=atime[0][j]*afine[0][k];
}

for(i=1;i<t;i++){
for (j=0;j<n;j++){
for (k=j+1;k<n;k++)
tfine+=atime[j]*afine[k];
}
if (tfine<min){
min=tfine;
mindex=i;
}
tfine=0;
}

for(i=0;i<n;i++){
for (j=0;j<n;j++)
if (atime[mindex]==time[j])
cout<<j+1<<" ";
}
cout<<"\n";
delete []time;
delete []fine;
for (i=0;i<n;i++){
delete []atime;
delete []afine;
}
delete []atime;
delete []afine;
}
return 0;
} [/code]

<:3)~~
New poster
Posts: 16
Joined: Wed Dec 06, 2006 6:57 pm

Post by <:3)~~ » Mon Apr 02, 2007 4:45 pm

Can someone plzz explain me why this question is getting accepted by greedy!!!!
for the given test case the shomaker has to pay a fine of 2 cents.
But if he do the jobs in the order
2 3 1 4
he has to pay 0 cents!!

sunny
Experienced poster
Posts: 124
Joined: Sun Sep 11, 2005 10:22 pm
Location: Civil-BUET

Post by sunny » Mon Apr 02, 2007 5:53 pm

<:3)~~ wrote:Can someone plzz explain me why this question is getting accepted by greedy!!!!
for the given test case the shomaker has to pay a fine of 2 cents.
But if he do the jobs in the order
2 3 1 4
he has to pay 0 cents!!
read the problem description carefully.
u have to output a order of the jobs such that the total fine is minimized.

for each day the shoemaker has to pay fines for every other pending jobs.
suppose,
2
5 8
6 7
if he does the 1st job 1st then fine is 5*7=35
if he does the 2nd job 1st then fine is 6 8=42

thus,for the sample input "2 1 3 4" order yields a fine of (4+2+5)*1 + (2+5)*3 + 5*2 = 42
for the order "2 3 1 4" the fine is (4+2+5)*1 + (4+5)*2 + 5*3 = 44.

Diagnostic
New poster
Posts: 1
Joined: Tue Apr 10, 2007 7:47 am

10026 Shoemaker -- Test Data?

Post by Diagnostic » Tue Apr 10, 2007 8:08 am

Would someone who's gotten AC on this problem mind posting some test data? It would be greatly appreciated.

andysoft
Experienced poster
Posts: 109
Joined: Sat Jun 23, 2007 9:53 pm
Location: Brest, BELARUS
Contact:

Post by andysoft » Thu Aug 16, 2007 11:56 am

Hi guys!
I am trying to solve this prob, but I hit one problem: misunderstanding and total mess with the problem statement.

For example if we have:

Code: Select all

indx:    1     2    3    4
time:    3     1    2    5
fine:    4  1000    2    5
What is the fine for sequence:
2 1 3 4 (Sample Out)
?
4+8+40 = 52 (Whinii F.'s method of understanding of statement)
OR
11 + 21 + 10 = 42 (How I firstly understood the statement)

And I am doubting if Sample OUT is OPTIMAL....


THANX FOR ANY HELP!!!! :)
Now I lay me down to sleep...
my profile

Dao007forever
New poster
Posts: 2
Joined: Sun Sep 09, 2007 8:45 pm
Contact:

Compilation error??

Post by Dao007forever » Fri Sep 21, 2007 6:57 pm

I have my program compiled on Dev-C++.
But it keeps saying 'compilation error' on UVA. What can it be??

Marcelo
New poster
Posts: 6
Joined: Sun Sep 30, 2007 7:53 pm

I need help!

Post by Marcelo » Sun Sep 30, 2007 7:56 pm

Ahhh... somebody help-me?
what's the output for this input?

Input:

Code: Select all

8

10
1 1
1 1
1 1
1 1
2 2
3 3
2 2
2 2
4 4
3 3

5
10 10
10 10
10 10
10 11
10 10

5
1 1
1 1
1 1
1 1
1 1

6
1 1
2 2
3 3
4 4
5 5
6 6

10
1 1
1 2
2 2
2 4
3 3
3 9
4 4
4 16
5 5
5 25

10
1 1
1 2
2 2
2 3
3 3
3 4
4 4
4 5
5 5
5 6

10
1 1
1 2
2 1
2 2
3 1
3 2
4 1
4 2
5 1
5 2

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
----
Acho que penso, logo, acho que existo!

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Sun Sep 30, 2007 8:16 pm

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.
Ami ekhono shopno dekhi...
HomePage

Marcelo
New poster
Posts: 6
Joined: Sun Sep 30, 2007 7:53 pm

Post by Marcelo » Sun Sep 30, 2007 8:25 pm

thanks!

my code too...

but uva returns WA! :(
----
Acho que penso, logo, acho que existo!

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Sun Sep 30, 2007 8:27 pm

You can post your code...
Ami ekhono shopno dekhi...
HomePage

Marcelo
New poster
Posts: 6
Joined: Sun Sep 30, 2007 7:53 pm

Post by Marcelo » Sun Sep 30, 2007 8:40 pm

Thanks for your help!

My code is:

Code: Select all

...

Advice: My english is very poor and so badly! I'll try to write, but I dont believe that I will successful!![/code]
Last edited by Marcelo on Tue Oct 02, 2007 4:56 pm, edited 1 time in total.
----
Acho que penso, logo, acho que existo!

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Mon Oct 01, 2007 10:10 pm

Your code looks correct except one thing. Check the case carefully...

Input:

Code: Select all

1

5
8 9
11 9
12 19
8 9
12 19
Output:

Code: Select all

3 5 1 4 2^
where '^' represents a newline character. Hope it helps.
Ami ekhono shopno dekhi...
HomePage

Marcelo
New poster
Posts: 6
Joined: Sun Sep 30, 2007 7:53 pm

Post by Marcelo » Mon Oct 01, 2007 10:40 pm

Jan,

thanks!

My code is acepted now!
----
Acho que penso, logo, acho que existo!

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Tue Oct 02, 2007 11:48 am

You are welcome. It would be better if you remove your code. [After logging in, use the edit option]
Ami ekhono shopno dekhi...
HomePage

Post Reply

Return to “Volume 100 (10000-10099)”