725  Division
Moderator: Board moderators
Refa, why don't you change your algorithm.
Somebody , including me, can give you some hints.
But i am not sure if my algorithm is perfect. Still it gets accepted P.E.
in a reasonable time. It is in C++.
Or ?
Do you just need some test data ?
I think this problem is not that hard so it makes no sense
you use so brutal approach
like generating code and so on.
Somebody , including me, can give you some hints.
But i am not sure if my algorithm is perfect. Still it gets accepted P.E.
in a reasonable time. It is in C++.
Or ?
Do you just need some test data ?
I think this problem is not that hard so it makes no sense
you use so brutal approach
like generating code and so on.
Sure, you're welcome.
Here is a small hint.
 Iterate through all possible values for K2 = fghij
 Iterate through all possible values N.
 Generate K1 = K2 * N.
Check if K1 has exactly five digits and that none of them is in the set {f, g, h, i, j }
This would mean you have a solution.
Just make sure you generate and print the solutions in the order the problem
wants you to print them.
And one more thing  I think leading zeros were allowed in K1 = abcde and K2 = fghij
The algorithm will work within the the time limit especially if written
in C/C++ and not in Java.
Here is a small hint.
 Iterate through all possible values for K2 = fghij
 Iterate through all possible values N.
 Generate K1 = K2 * N.
Check if K1 has exactly five digits and that none of them is in the set {f, g, h, i, j }
This would mean you have a solution.
Just make sure you generate and print the solutions in the order the problem
wants you to print them.
And one more thing  I think leading zeros were allowed in K1 = abcde and K2 = fghij
The algorithm will work within the the time limit especially if written
in C/C++ and not in Java.

 Experienced poster
 Posts: 131
 Joined: Sat Jul 17, 2004 4:09 am
 Location: Lima, Per

 New poster
 Posts: 11
 Joined: Sat Jul 22, 2006 8:45 pm
 Location: Sylhet, Bagladesh
 Contact:
725 RTE ?
Sorry, Not TLE
Last edited by Masud_CSE_SUST on Thu Jul 27, 2006 11:21 pm, edited 3 times in total.
725  How to optimize?
i'm using the following algorithm:
abcde / fghij = N
i dont know how to optimize it further. this algo is taking 23 minutes in my 866 MHz PC to generate solutions from 2 to 79. can anyone help me to optimize it?
abcde / fghij = N
Code: Select all
1. starting from 50123, iterate through all possible valid permutation of abcde.
2. obtain the minimum value of fghij. if abcde / fghij < N then obtain next abcde and continue this step.
3. iterate through all possible permutations of fghij. for every abcde == fghij * N, that is a solution. break this iteration as soon as a solution is found and obtain next abcde. go to step 2.

 New poster
 Posts: 7
 Joined: Tue Jul 25, 2006 2:01 pm
 Contact:
725 Wrong Answer
Hi all,
I tried to solve 725 "Division" problem but i m getting wrong answer.
I am posting my code. Please give me some more test cases, so that i can find my error.
thanx very much..
I tried to solve 725 "Division" problem but i m getting wrong answer.
I am posting my code. Please give me some more test cases, so that i can find my error.
thanx very much..
Last edited by Anupam Pathak on Tue Oct 31, 2006 6:07 am, edited 1 time in total.
Trying to reduce complexity of the World.
Try the I/O set
Input:
Output:
Hope it helps.
Input:
Code: Select all
44
53
0
Code: Select all
58476 / 01329 = 44
59268 / 01347 = 44
67892 / 01543 = 44
69432 / 01578 = 44
95348 / 02167 = 44
65879 / 01243 = 53
75896 / 01432 = 53
84376 / 01592 = 53
92538 / 01746 = 53
Ami ekhono shopno dekhi...
HomePage
HomePage

 New poster
 Posts: 7
 Joined: Tue Jul 25, 2006 2:01 pm
 Contact:
725 why PE ?
Code: Select all
int main(){
int i,n,k,b;
while(scanf("%d",&n)&&n){
b=0;
for(i=((1000/n)*n+n)*n; i<100000; i+=n){
k=i/n;
if(rozne(i,k)){
printf("%05d / %05d = %d\n",i,i/n,n);
b=1;
}
}
if(b==0)printf("There are no solutions for %d.\n",n);
printf("\n");
}
return 0;
}