10026  Shoemaker's Problem
Moderator: Board moderators

 Experienced poster
 Posts: 154
 Joined: Sat Apr 17, 2004 9:34 am
 Location: EEE, BUET
10026 runtime error help!
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,n1,atime);
count=0;
Perm(fine,0,n1,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]
#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,n1,atime);
count=0;
Perm(fine,0,n1,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]
read the problem description carefully.<: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!!
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.

 New poster
 Posts: 1
 Joined: Tue Apr 10, 2007 7:47 am
10026 Shoemaker  Test Data?
Would someone who's gotten AC on this problem mind posting some test data? It would be greatly appreciated.

 Experienced poster
 Posts: 109
 Joined: Sat Jun 23, 2007 9:53 pm
 Location: Brest, BELARUS
 Contact:
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:
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!!!!
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
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
my profile

 New poster
 Posts: 2
 Joined: Sun Sep 09, 2007 8:45 pm
 Contact:
Compilation error??
I have my program compiled on DevC++.
But it keeps saying 'compilation error' on UVA. What can it be??
But it keeps saying 'compilation error' on UVA. What can it be??
I need help!
Ahhh... somebody helpme?
what's the output for this input?
Input:
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!
Acho que penso, logo, acho que existo!
My accepted code returns...
Output:
Hope it helps.
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
Ami ekhono shopno dekhi...
HomePage
HomePage
Thanks for your help!
My code is:
Advice: My english is very poor and so badly! I'll try to write, but I dont believe that I will successful!![/code]
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!
Acho que penso, logo, acho que existo!
Your code looks correct except one thing. Check the case carefully...
Input:
Output:
where '^' represents a newline character. Hope it helps.
Input:
Code: Select all
1
5
8 9
11 9
12 19
8 9
12 19
Code: Select all
3 5 1 4 2^
Ami ekhono shopno dekhi...
HomePage
HomePage
You are welcome. It would be better if you remove your code. [After logging in, use the edit option]
Ami ekhono shopno dekhi...
HomePage
HomePage