725 - Division

All about problems in Volume 7. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

Post by refa » Tue Mar 22, 2005 11:54 pm

Anybody any idea, please?

Thank you

User avatar
Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

Post by Sedefcho » Wed Mar 23, 2005 3:01 am

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:

Post by refa » Wed Mar 23, 2005 12:45 pm

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 :)

User avatar
Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

Post by Sedefcho » Wed Mar 23, 2005 6:30 pm

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:

Post by refa » Sun Mar 27, 2005 11:55 am

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

Post by Antonio Ocampo » Sun Sep 04, 2005 2:18 am

Hi refa

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

Thx in advance :wink:

scidong
New poster
Posts: 45
Joined: Sat Jan 21, 2006 12:55 pm
Location: the four-dimensional world

Post by scidong » Mon Feb 20, 2006 12:22 pm

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

Post by scidong » Mon Feb 20, 2006 12:25 pm

Hmm.
Who are you GUEST?
Plz 'leave now & don`t come back!'
All living things are amazing thing.
一八???

User avatar
Masud_CSE_SUST
New poster
Posts: 11
Joined: Sat Jul 22, 2006 8:45 pm
Location: Sylhet, Bagladesh
Contact:

725 RTE ?

Post by Masud_CSE_SUST » Sat Jul 22, 2006 9:12 pm

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

Post by IRA » Sun Jul 23, 2006 9:03 pm

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

User avatar
Donotalo
Learning poster
Posts: 56
Joined: Sat Aug 20, 2005 11:05 am
Location: Bangladesh

725 - How to optimize?

Post by Donotalo » Fri Sep 01, 2006 10:05 am

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?
Image

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

725 Wrong Answer

Post by Anupam Pathak » Sun Oct 29, 2006 3:45 pm

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
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Mon Oct 30, 2006 4:13 pm

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:

Post by Anupam Pathak » Tue Oct 31, 2006 6:06 am

thanx sir,
though I have solve the problem,,
thanx very much :D
Trying to reduce complexity of the World.

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

725 why PE ?

Post by Spykaj » Thu Dec 14, 2006 12:19 am

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 :(

Post Reply

Return to “Volume 7 (700-799)”