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

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Thu Dec 14, 2006 8:18 am

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

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

Re: 725 - Division

Post by arcadia » Mon Jun 15, 2009 12:47 am

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

Post by yure666 » Wed Nov 11, 2009 7:11 pm

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

Post by Sawon90 » Sun Feb 05, 2012 5:10 am

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
New poster
Posts: 11
Joined: Wed Nov 23, 2011 1:28 am

Re: 725 - Division

Post by Sawon90 » Sun Feb 05, 2012 6:39 am

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

Post by DO? » Wed Jul 11, 2012 9:48 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;
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?
New poster
Posts: 2
Joined: Wed Jul 11, 2012 9:42 am

725 - Division, please help me

Post by DO? » Wed Jul 11, 2012 9:56 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;
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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 725 - Division, please help me

Post by brianfry713 » Tue Jul 17, 2012 1:07 am

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

Post by brianfry713 » Tue Jul 17, 2012 1:07 am

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

Post by _ashik » Wed Aug 08, 2012 1:46 pm

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

Post by sonjbond » Mon Feb 04, 2013 11:45 am

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

Post by brianfry713 » Mon Feb 04, 2013 11:24 pm

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

Post by sonjbond » Wed Feb 06, 2013 1:32 pm

THANK YOU .... SOLVED :)

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

Re: 725 - Division

Post by Mukit Chowdhury » Wed Feb 06, 2013 7:33 pm

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

Post by Yusif » Thu Jul 11, 2013 12:22 am

wa, plz help!

Code: Select all

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

Post Reply

Return to “Volume 7 (700-799)”