## 725 - Division

Moderator: Board moderators

refa
New poster
Posts: 8
Joined: Thu Mar 17, 2005 9:00 pm
Contact:

Thank you

Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria
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.

refa
New poster
Posts: 8
Joined: Thu Mar 17, 2005 9:00 pm
Contact:
Dear Sedefcho,

thank you for your response. I will try to
solve it again on my own on a different
way and with a different aproach if I don't
succedd I will ask you again..

Thank you pal

Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria
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.

refa
New poster
Posts: 8
Joined: Thu Mar 17, 2005 9:00 pm
Contact:
Thank you Sedefcho, I got the idea.

Btw I got accepted with my old code I forgot one more value for 17 and that's why I got wrong answer all the time! I will try to solve the problem also on the way you showed me.

Thank you

Best regards,
Refik

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

I got 27 values for 17 like you . Could you me give any hint?

scidong
New poster
Posts: 45
Joined: Sat Jan 21, 2006 12:55 pm
Location: the four-dimensional world
Oh my gosh.
plz speack English-!
All living things are amazing thing.

scidong
New poster
Posts: 45
Joined: Sat Jan 21, 2006 12:55 pm
Location: the four-dimensional world
Hmm.
Who are you GUEST?
Plz 'leave now & don`t come back!'
All living things are amazing thing.

Masud_CSE_SUST
New poster
Posts: 11
Joined: Sat Jul 22, 2006 8:45 pm
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.

IRA
Learning poster
Posts: 82
Joined: Sat Jan 07, 2006 6:52 am
It doesn't use long long to solve the problem.....
I see your method.It doesn't got TLE.
You must to check what step make infinite loop....

Donotalo
Learning poster
Posts: 56
Joined: Sat Aug 20, 2005 11:05 am

### 725 - How to optimize?

i'm using the following algorithm:

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.``````
i dont know how to optimize it further. this algo is taking 2-3 minutes in my 866 MHz PC to generate solutions from 2 to 79. can anyone help me to optimize it?

Anupam Pathak
New poster
Posts: 7
Joined: Tue Jul 25, 2006 2:01 pm
Contact:

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

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
Try the I/O set

Input:

Code: Select all

``````44
53
0``````
Output:

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``````
Hope it helps.
Ami ekhono shopno dekhi...
HomePage

Anupam Pathak
New poster
Posts: 7
Joined: Tue Jul 25, 2006 2:01 pm
Contact:
thanx sir,
though I have solve the problem,,
thanx very much
Trying to reduce complexity of the World.

Spykaj
New poster
Posts: 47
Joined: Sun May 21, 2006 12:13 pm

### 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;
}``````
Help plz PE