725 - Division

[Jan]

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.

[arcadia]

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]

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]

please help me why I am getting WA.... here is my code..... please give me some critical case

//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]

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

[DO?]

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;
char answer[20],mem[20];

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)
    {
        answer[len-l]=(inp%10)+'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];

    int len=strlen(answer);
    if(len==5)
    {
        bool cek=0;
        for(int l=0;l<len;l++)
        {
            if(bil[answer[l]-'0']==0)bil[answer[l]-'0']=1;
            else {cek=1; break;}
        }
        if(cek==0)
        {
            jwb=1;
            printf("%s / %s = %s\n",answer,mem,inp);
        }
    }
}

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;
        memset(answer,'\0',sizeof(answer));
        permutasi(0,i);
        if(jwb==0)printf("There are no solutions for %s.\n",i);
    }
return 0;
}

please anyone help me. thanks

[DO?]

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;
char answer[20],mem[20];

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)
    {
        answer[len-l]=(inp%10)+'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];

    int len=strlen(answer);
    if(len==5)
    {
        bool cek=0;
        for(int l=0;l<len;l++)
        {
            if(bil[answer[l]-'0']==0)bil[answer[l]-'0']=1;
            else {cek=1; break;}
        }
        if(cek==0)
        {
            jwb=1;
            printf("%s / %s = %s\n",answer,mem,inp);
        }
    }
}

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;
        memset(answer,'\0',sizeof(answer));
        permutasi(0,i);
        if(jwb==0)printf("There are no solutions for %s.\n",i);
    }
return 0;
}

thanks a lot, please help

[brianfry713]

Separate the output for two different values of N by a blank line.

[brianfry713]

Separate the output for two different values of N by a blank line.

[_ashik]

I'm getting WA, need help..


found the bug, AC

[sonjbond]

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

[brianfry713]

Separate the output for two different values of N by a blank line. Don't print an extra blank line at the end.

[sonjbond]

THANK YOU .... SOLVED

[Mukit Chowdhury]

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

[Yusif]

wa, plz help!

Code: Select all

ac