## 725 - Division

Moderator: Board moderators

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
Search your problem in the board first. If you find a thread use it. Dont open a new one if one exists. And the problem states not to print a blank line after the last case, but your code does. So, you are getting PE.
Ami ekhono shopno dekhi...
HomePage

New poster
Posts: 1
Joined: Mon Jun 15, 2009 12:41 am

### Re: 725 - Division

Hi, I don't get why my solution isn't accepted.. output is correct, I checked some old I/O here and it's the same. Some advice?
Basically I generate all possible numerators, and then check if it's possible that numerator/N = correct denominator. Problem shouldn't be timeout.

Code: Select all

``````#include <iostream>
using namespace std;

int num_sol;

int contains (int den, int i)
{

for (int j = 10;j<100000;j*=10)
{
if((den%j -den%(j/10))/(j/10)== i)
{
return true;
}
}
return false;
}

int check_den(int den, int v[10])
{

for (int i = 0; i<10;i++)
{
if(v[i]!= -1 && !contains(den,i))
{
return false;
}

}
return true;
}

void divs (int num, int v[10],int res)
{
/**2<n<79*/
if(num/10000 > 0)
{
int den = num/res;
if((num%res)==0 && check_den(den,v))
{
num_sol++;
if(den < 10000)
{
cout<<num<<" / 0"<<num/res<<" = "<<res<<endl;
}
else
{
cout<<num<<" / "<<num/res<<" = "<<res<<endl;
}
}
return;
}

for(int i = 0;i<10;i++)
{
if(v[i]!= -1)
{
v[i] = -1;
divs(num*10+i, v,res);
v[i] = i;
}
}

}

int main() {

int n=0;
int v[10];
for (int i = 0;i <10;i++)
{
v[i] = i;
}
cin>>n;
while (n>0)
{
for (int i = 0;i <10;i++)
{
v[i] = i;
}
num_sol = 0;
divs(0,v,n);
if (num_sol == 0)
{
cout<<"There are no solutions for "<<n<<"."<<endl;
}
cin>>n;

cout<<endl;

}
}
``````

yure666
New poster
Posts: 2
Joined: Wed Nov 11, 2009 7:04 pm

### Re: 725 - Division

I can't see what is wrong in my code, I keep getting WA. Can someone post some cases? Here are some of mine:

Input:

Code: Select all

``````2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
7
7
55
55
23
2
23
23
0
11
12
13
14
15
16
17
33``````
Output:

Code: Select all

``````13458 / 06729 = 2
13584 / 06792 = 2
13854 / 06927 = 2
14538 / 07269 = 2
14586 / 07293 = 2
14658 / 07329 = 2
15384 / 07692 = 2
15846 / 07923 = 2
15864 / 07932 = 2
18534 / 09267 = 2
18546 / 09273 = 2
18654 / 09327 = 2
26970 / 13485 = 2
27096 / 13548 = 2
27690 / 13845 = 2
29076 / 14538 = 2
29370 / 14685 = 2
29670 / 14835 = 2
29706 / 14853 = 2
29730 / 14865 = 2
30972 / 15486 = 2
32970 / 16485 = 2
37092 / 18546 = 2
37290 / 18645 = 2
41358 / 20679 = 2
41538 / 20769 = 2
41586 / 20793 = 2
46158 / 23079 = 2
53418 / 26709 = 2
53814 / 26907 = 2
54138 / 27069 = 2
54186 / 27093 = 2
54618 / 27309 = 2
58134 / 29067 = 2
58146 / 29073 = 2
58614 / 29307 = 2
61458 / 30729 = 2
61584 / 30792 = 2
61854 / 30927 = 2
62970 / 31485 = 2
64158 / 32079 = 2
65418 / 32709 = 2
65814 / 32907 = 2
69702 / 34851 = 2
70296 / 35148 = 2
70962 / 35481 = 2
76290 / 38145 = 2
76902 / 38451 = 2
90276 / 45138 = 2
90372 / 45186 = 2
90762 / 45381 = 2
92370 / 46185 = 2
93702 / 46851 = 2
96270 / 48135 = 2
96702 / 48351 = 2
97026 / 48513 = 2
97032 / 48516 = 2
97062 / 48531 = 2
97230 / 48615 = 2
97302 / 48651 = 2

17469 / 05823 = 3
17496 / 05832 = 3
50382 / 16794 = 3
53082 / 17694 = 3
61749 / 20583 = 3
69174 / 23058 = 3
91746 / 30582 = 3
96174 / 32058 = 3

15768 / 03942 = 4
17568 / 04392 = 4
23184 / 05796 = 4
31824 / 07956 = 4
60948 / 15237 = 4
68940 / 17235 = 4
69408 / 17352 = 4
81576 / 20394 = 4
81756 / 20439 = 4
86940 / 21735 = 4
94068 / 23517 = 4
94860 / 23715 = 4

13485 / 02697 = 5
13845 / 02769 = 5
14685 / 02937 = 5
14835 / 02967 = 5
14865 / 02973 = 5
16485 / 03297 = 5
18645 / 03729 = 5
31485 / 06297 = 5
38145 / 07629 = 5
46185 / 09237 = 5
48135 / 09627 = 5
48615 / 09723 = 5
67290 / 13458 = 5
67920 / 13584 = 5
69270 / 13854 = 5
72690 / 14538 = 5
72930 / 14586 = 5
73290 / 14658 = 5
76920 / 15384 = 5
79230 / 15846 = 5
79320 / 15864 = 5
92670 / 18534 = 5
92730 / 18546 = 5
93270 / 18654 = 5

17658 / 02943 = 6
27918 / 04653 = 6
34182 / 05697 = 6

16758 / 02394 = 7
18459 / 02637 = 7
31689 / 04527 = 7
36918 / 05274 = 7
37926 / 05418 = 7
41832 / 05976 = 7
53298 / 07614 = 7
98532 / 14076 = 7

25496 / 03187 = 8
36712 / 04589 = 8
36728 / 04591 = 8
37512 / 04689 = 8
37528 / 04691 = 8
38152 / 04769 = 8
41896 / 05237 = 8
42968 / 05371 = 8
46312 / 05789 = 8
46328 / 05791 = 8
46712 / 05839 = 8
47136 / 05892 = 8
47328 / 05916 = 8
47368 / 05921 = 8
51832 / 06479 = 8
53928 / 06741 = 8
54312 / 06789 = 8
54328 / 06791 = 8
54712 / 06839 = 8
56984 / 07123 = 8
58496 / 07312 = 8
58912 / 07364 = 8
59328 / 07416 = 8
59368 / 07421 = 8
63152 / 07894 = 8
63528 / 07941 = 8
65392 / 08174 = 8
65432 / 08179 = 8
67152 / 08394 = 8
67352 / 08419 = 8
67512 / 08439 = 8
71456 / 08932 = 8
71536 / 08942 = 8
71624 / 08953 = 8
71632 / 08954 = 8
73248 / 09156 = 8
73264 / 09158 = 8
73456 / 09182 = 8
74528 / 09316 = 8
74568 / 09321 = 8
74816 / 09352 = 8
75328 / 09416 = 8
75368 / 09421 = 8
76184 / 09523 = 8
76248 / 09531 = 8
76328 / 09541 = 8
83672 / 10459 = 8
83752 / 10469 = 8
84296 / 10537 = 8
84632 / 10579 = 8
84736 / 10592 = 8
85392 / 10674 = 8
85432 / 10679 = 8
85936 / 10742 = 8
86352 / 10794 = 8
87456 / 10932 = 8
87536 / 10942 = 8
87624 / 10953 = 8
87632 / 10954 = 8
96584 / 12073 = 8
98456 / 12307 = 8
98760 / 12345 = 8

57429 / 06381 = 9
58239 / 06471 = 9
75249 / 08361 = 9
95742 / 10638 = 9
95823 / 10647 = 9
97524 / 10836 = 9

There are no solutions for 10.

There are no solutions for 11.

45792 / 03816 = 12
73548 / 06129 = 12
89532 / 07461 = 12
91584 / 07632 = 12

67392 / 05184 = 13
81549 / 06273 = 13
94653 / 07281 = 13

25746 / 01839 = 14
27384 / 01956 = 14
41538 / 02967 = 14
46158 / 03297 = 14
51492 / 03678 = 14
54768 / 03912 = 14
61572 / 04398 = 14
65982 / 04713 = 14

27945 / 01863 = 15
92745 / 06183 = 15

45936 / 02871 = 16
73296 / 04581 = 16
98352 / 06147 = 16

26843 / 01579 = 17
28543 / 01679 = 17
29546 / 01738 = 17
36958 / 02174 = 17
45713 / 02689 = 17
45781 / 02693 = 17
54689 / 03217 = 17
59126 / 03478 = 17
64957 / 03821 = 17
65297 / 03841 = 17
67184 / 03952 = 17
67218 / 03954 = 17
76823 / 04519 = 17
76891 / 04523 = 17
78132 / 04596 = 17
78523 / 04619 = 17
78591 / 04623 = 17
81532 / 04796 = 17
83572 / 04916 = 17
83657 / 04921 = 17
89437 / 05261 = 17
89471 / 05263 = 17
89641 / 05273 = 17
91426 / 05378 = 17
92837 / 05461 = 17
92871 / 05463 = 17
93126 / 05478 = 17

28674 / 01593 = 18

51984 / 02736 = 19
81567 / 04293 = 19

There are no solutions for 20.

There are no solutions for 21.

51678 / 02349 = 22

36294 / 01578 = 23
81627 / 03549 = 23
81972 / 03564 = 23

39528 / 01647 = 24
46872 / 01953 = 24

There are no solutions for 25.

42978 / 01653 = 26
56498 / 02173 = 26
61854 / 02379 = 26
67314 / 02589 = 26
67418 / 02593 = 26
76518 / 02943 = 26
82654 / 03179 = 26
89726 / 03451 = 26
92846 / 03571 = 26

39852 / 01476 = 27
49572 / 01836 = 27
69741 / 02583 = 27
96714 / 03582 = 27

75348 / 02691 = 28

37584 / 01296 = 29
73689 / 02541 = 29

There are no solutions for 30.

There are no solutions for 31.

75168 / 02349 = 32

There are no solutions for 33.

There are no solutions for 34.

48265 / 01379 = 35
63945 / 01827 = 35
64295 / 01837 = 35
74865 / 02139 = 35
93485 / 02671 = 35

There are no solutions for 36.

65934 / 01782 = 37

65892 / 01734 = 38
74328 / 01956 = 38

There are no solutions for 39.

There are no solutions for 40.

There are no solutions for 41.

There are no solutions for 42.

93654 / 02178 = 43

58476 / 01329 = 44
59268 / 01347 = 44
67892 / 01543 = 44
69432 / 01578 = 44
95348 / 02167 = 44

There are no solutions for 45.

58374 / 01269 = 46

There are no solutions for 47.

There are no solutions for 48.

There are no solutions for 49.

There are no solutions for 50.

There are no solutions for 51.

95472 / 01836 = 52

65879 / 01243 = 53
75896 / 01432 = 53
84376 / 01592 = 53
92538 / 01746 = 53

There are no solutions for 54.

There are no solutions for 55.

There are no solutions for 56.

There are no solutions for 57.

There are no solutions for 58.

73986 / 01254 = 59

There are no solutions for 60.

There are no solutions for 61.

79546 / 01283 = 62
94736 / 01528 = 62

There are no solutions for 63.

There are no solutions for 64.

There are no solutions for 65.

83754 / 01269 = 66

There are no solutions for 67.

98736 / 01452 = 68

There are no solutions for 69.

There are no solutions for 70.

There are no solutions for 71.

There are no solutions for 72.

There are no solutions for 73.

There are no solutions for 74.

There are no solutions for 75.

There are no solutions for 76.

There are no solutions for 77.

There are no solutions for 78.

There are no solutions for 79.

16758 / 02394 = 7
18459 / 02637 = 7
31689 / 04527 = 7
36918 / 05274 = 7
37926 / 05418 = 7
41832 / 05976 = 7
53298 / 07614 = 7
98532 / 14076 = 7
16758 / 02394 = 7
18459 / 02637 = 7
31689 / 04527 = 7
36918 / 05274 = 7
37926 / 05418 = 7
41832 / 05976 = 7
53298 / 07614 = 7
98532 / 14076 = 7

There are no solutions for 55.
There are no solutions for 55.

36294 / 01578 = 23
81627 / 03549 = 23
81972 / 03564 = 23

13458 / 06729 = 2
13584 / 06792 = 2
13854 / 06927 = 2
14538 / 07269 = 2
14586 / 07293 = 2
14658 / 07329 = 2
15384 / 07692 = 2
15846 / 07923 = 2
15864 / 07932 = 2
18534 / 09267 = 2
18546 / 09273 = 2
18654 / 09327 = 2
26970 / 13485 = 2
27096 / 13548 = 2
27690 / 13845 = 2
29076 / 14538 = 2
29370 / 14685 = 2
29670 / 14835 = 2
29706 / 14853 = 2
29730 / 14865 = 2
30972 / 15486 = 2
32970 / 16485 = 2
37092 / 18546 = 2
37290 / 18645 = 2
41358 / 20679 = 2
41538 / 20769 = 2
41586 / 20793 = 2
46158 / 23079 = 2
53418 / 26709 = 2
53814 / 26907 = 2
54138 / 27069 = 2
54186 / 27093 = 2
54618 / 27309 = 2
58134 / 29067 = 2
58146 / 29073 = 2
58614 / 29307 = 2
61458 / 30729 = 2
61584 / 30792 = 2
61854 / 30927 = 2
62970 / 31485 = 2
64158 / 32079 = 2
65418 / 32709 = 2
65814 / 32907 = 2
69702 / 34851 = 2
70296 / 35148 = 2
70962 / 35481 = 2
76290 / 38145 = 2
76902 / 38451 = 2
90276 / 45138 = 2
90372 / 45186 = 2
90762 / 45381 = 2
92370 / 46185 = 2
93702 / 46851 = 2
96270 / 48135 = 2
96702 / 48351 = 2
97026 / 48513 = 2
97032 / 48516 = 2
97062 / 48531 = 2
97230 / 48615 = 2
97302 / 48651 = 2

36294 / 01578 = 23
81627 / 03549 = 23
81972 / 03564 = 23
36294 / 01578 = 23
81627 / 03549 = 23
81972 / 03564 = 23``````
New lines have been copied as in the files, so there is no new line at the end of the input, neither the output.

Thanks

Sawon90
New poster
Posts: 11
Joined: Wed Nov 23, 2011 1:28 am

### Re: 725 - Division

//Bismillahir Rahmanir Rahim
#include<stdio.h>
#include<vector>
using namespace std;
long a[40000],b[100010],k,i0,i1,i2,i3,i4,i,n;
bool digit(long p,long q)
{
long x[11],y,z;
for(y=0;y<x[y];y++)
x[y]=0;
while(p)
{
x[p%10]=1;
p/=10;
}
if(q<10000 && x[0]==1)
return 0;
while(q)
{
z=q%10;
if(x[z]==1)
return 0;
q/=10;
}
return 1;
}
int main()
{
k=0;
for(i0=0;i0<=9;i0++)
{
for(i1=0;i1<=9;i1++)
{
if(i1==i0)
continue;
for(i2=0;i2<=9;i2++)
{
if(i2==i0 || i2==i1)
continue;
for(i3=0;i3<=9;i3++)
{
if(i3==i0 || i3==i1 || i3==i2)
continue;
for(i4=0;i4<=9;i4++)
{
if(i4==i0 || i4==i1 || i4==i2 || i4==i3)
continue;
a[k]=i4+(i3*10)+(i2*100)+(i1*1000)+(i0*10000);
b[a[k]]=1;
k++;
}
}
}
}
}
i3=0;
while(scanf("%ld",&n)&&n)
{
if(i3)
printf("\n");
else
i3=1;
i2=0;
for(i=0;i<k;i++)
{
i1=a*n;
if(i1>100000)
break;
if(b[i1]==1 && digit(i1,a) && i1>10000)
{
i2=1;
printf("%05ld / %05ld = %ld\n",i1,a,n);
}
}
if(i2==0)
printf("There are no solutions for %ld.\n",n);
}
return 0;
}

Sawon90
New poster
Posts: 11
Joined: Wed Nov 23, 2011 1:28 am

### Re: 725 - Division

i got acc, there was some silly mistake in my code according to problem statement.

DO?
New poster
Posts: 2
Joined: Wed Jul 11, 2012 9:42 am

### Re: 725 - Division

please tell why im getting WA.
this is my code

Code: Select all

``````#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;

bool numb[10],bil[10],jwb;

long long bilgen(char inp[])
{
int len=strlen(inp);
long long ans=0;
for(int l=0;l<len;l++)
{
ans*=10;
ans+=inp[l]-'0';
}
return ans;
}

void chargen(long long inp)
{
long long temp=inp,l=1;
int len=0;
while(temp>0)
{
len++;
temp/=10;
}
while(inp>0)
{
inp/=10;
l++;
}
}

void divis(char inp[])
{
long long kali=bilgen(inp),bilangan=bilgen(mem);
bilangan*=kali;
chargen(bilangan);
for(int l=0;l<10;l++)bil[l]=numb[l];

if(len==5)
{
bool cek=0;
for(int l=0;l<len;l++)
{
else {cek=1; break;}
}
if(cek==0)
{
jwb=1;
}
}
}

void permutasi(int pos, char inp[])
{
if(pos==5) divis(inp);
else
{
for(int l=0;l<10;l++)
{
if(numb[l]==0)
{
numb[l]=1;
mem[pos]=l+'0';
permutasi(pos+1,inp);
numb[l]=0;
}
}
}
}

int main()
{
char i[5];
while(scanf("%s",i) && strcmp(i,"0")!=0)
{
jwb=0;
for(int l=0;l<10;l++)numb[l]=0;
permutasi(0,i);
if(jwb==0)printf("There are no solutions for %s.\n",i);
}
return 0;
}
``````

DO?
New poster
Posts: 2
Joined: Wed Jul 11, 2012 9:42 am

please tell why im getting WA.
this is my code

Code: Select all

``````#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;

bool numb[10],bil[10],jwb;

long long bilgen(char inp[])
{
int len=strlen(inp);
long long ans=0;
for(int l=0;l<len;l++)
{
ans*=10;
ans+=inp[l]-'0';
}
return ans;
}

void chargen(long long inp)
{
long long temp=inp,l=1;
int len=0;
while(temp>0)
{
len++;
temp/=10;
}
while(inp>0)
{
inp/=10;
l++;
}
}

void divis(char inp[])
{
long long kali=bilgen(inp),bilangan=bilgen(mem);
bilangan*=kali;
chargen(bilangan);
for(int l=0;l<10;l++)bil[l]=numb[l];

if(len==5)
{
bool cek=0;
for(int l=0;l<len;l++)
{
else {cek=1; break;}
}
if(cek==0)
{
jwb=1;
}
}
}

void permutasi(int pos, char inp[])
{
if(pos==5) divis(inp);
else
{
for(int l=0;l<10;l++)
{
if(numb[l]==0)
{
numb[l]=1;
mem[pos]=l+'0';
permutasi(pos+1,inp);
numb[l]=0;
}
}
}
}

int main()
{
char i[5];
while(scanf("%s",i) && strcmp(i,"0")!=0)
{
jwb=0;
for(int l=0;l<10;l++)numb[l]=0;
permutasi(0,i);
if(jwb==0)printf("There are no solutions for %s.\n",i);
}
return 0;
}
``````

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Separate the output for two different values of N by a blank line.
Check input and AC output for thousands of problems on uDebug!

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 725 - Division

Separate the output for two different values of N by a blank line.
Check input and AC output for thousands of problems on uDebug!

_ashik
New poster
Posts: 1
Joined: Wed Aug 08, 2012 1:38 pm

### Re: 725 - Division

I'm getting WA, need help..

found the bug, AC

sonjbond
New poster
Posts: 19
Joined: Wed Jul 04, 2012 10:30 pm

### Why WA ? 725 - Division

Why I am getting WA .... Plz help me ................
My sample I/O is correct but .........

here is my code

Code: Select all

``````Code removed after AC :)
``````
plz help me
Last edited by sonjbond on Wed Feb 06, 2013 1:34 pm, edited 1 time in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 725 - Division

Separate the output for two different values of N by a blank line. Don't print an extra blank line at the end.
Check input and AC output for thousands of problems on uDebug!

sonjbond
New poster
Posts: 19
Joined: Wed Jul 04, 2012 10:30 pm

### Re: 725 - Division

THANK YOU .... SOLVED

Mukit Chowdhury
Learning poster
Posts: 98
Joined: Fri Aug 17, 2012 9:23 pm
Location: Dhaka
Contact:

### Re: 725 - Division

Have done with the help of backtracking ...
A very nice problem ...

Yusif
New poster
Posts: 27
Joined: Tue Jun 25, 2013 2:24 am

### Re: 725 - Division

wa, plz help!

Code: Select all

``ac``
Last edited by Yusif on Fri Jul 12, 2013 3:04 pm, edited 1 time in total.