471 - Magic Numbers

opportunity · Post by **opportunity** » Sat Sep 24, 2005 7:19 am

done!! it was really a silly mistake more likely to be committed by novice progs... i missed to append 'LL' at the end of long long type value.

.
i wrote '9876543210' instead of '9876543210LL'.
thanks for not answering!!!!

Darko · Post by **Darko** » Fri Sep 15, 2006 9:30 pm

Thanks for that, Sedefcho.

Now and then I would open this problem and think "Man, I have no idea how to do this for N=1". There should be sum(10!/k!), k=0..10 solutions for N=1. Well, that's with leading zeros (too lazy to figure out what the exact number is). So I was thinking about somehow generating them all and then go through the list for any N and look for the ones that N divides.
Ok, going through 9+ mil numbers every time looked kinda bad already, but storing them somehow... I had no idea how to do it. Especially because some of them needed more than 4 bytes.

I finally looked for a thread about it - and there it was - another easy problem masked as a hard one.

[EDIT: Just occured to me that the exact number is much smaller than 9 mil. Am I right if I say it is sum of even factorials up to 10? Which is less than 4mil. Now, that sounds doable, but still with some constraints (e.g. number of cases)]

aabiague · Post by **aabiague** » Mon Nov 20, 2006 4:31 am

Hello, who can tell me why my code is OLE ??? Please help me.

This is a part of my code.

Code: Select all

int main()
{
   char cadena[30];
   double num = 1.0 , num2 , i = 1.0 , aux = 9876543210.0;
   num = atof(gets(cadena));
   num2 = num * i ;
   if (num2 != 0 && num2 != 1 )
   {
     num2 = num * i ;
       while ( num2 < aux )
        {
         if (!DRepetido(i))
         {
              if (!DRepetido(num2))
                printf ("%.lf / %.lf = %.lf\n",num2,i,num);
              else
                Visitar(num2);
         }
          else
            Visitar(i);
        i++ ;
       num2 = num * i ;
      }
   }
    return 0;
}

Jan · Post by **Jan** » Mon Nov 20, 2006 6:07 pm

Dont open a new thread if there is one already. And you dont need 'double'. While using 'double' remember that you cant check like 'num2 != 0' or 'num2 != 1' due to precision error. You have to check like 'fabs(num2) > eps' or 'fabs(num2-1) > eps' where eps should be positive and small.

peterkwan · Post by **peterkwan** » Sun Nov 04, 2007 4:42 pm

i have tried the problem and got WA for several times, even I used the algorithm posted by Sedefcho. Here is my code:

Code: Select all

#include <iostream>
#include <string>
#include <sstream>
using namespace std;

#define S1_MAX 9876543210ULL

bool checkDigits(unsigned long long s1) {
	string n_str = "";
	ostringstream os;
	os << s1;
	n_str = os.str();

	int dn[10] = {0};

	for (int i = 0; i < n_str.length(); i++) {
		if (dn[n_str[i]-'0']>0) { return false; }
		dn[n_str[i]-'0']++;
	}

	return true;
}

main() {
	int c;
	unsigned long long s1, s2, n;

	cin >> c;
	for (int i = 0; i < c; i++) {
		cin >> n;
		for (s2 = 1; s2 <= S1_MAX/n; s2++) {
			if (checkDigits(s2)) {
				s1 = s2*n;
				if (s1 > S1_MAX) break;
				if (checkDigits(s1))
					cout << s1 << " / " << s2 << " = " << n << endl;
			}
		}

		cout << endl;
	}

	return 0;
}

Is there any case I don't pass?

Jehad Uddin · Post by **Jehad Uddin** » Sun Aug 02, 2009 12:31 pm

i m getting 20 WA in this problem,i m getting frustrated in this problem,pls help me.....

Code: Select all

#include<iostream>
#include<cmath>
 
using namespace std;
long long int check(long long int n)
{
 long long int a[10],k=1,i;
 for(i=0;i<10;i++) a[i]=0;
 do
 {
  if(a[n%10]==0)
  a[n%10]++;
  else k=0,a[n%10]++;
  n/=10;
 }
 while(n!=0);

 return k;
}
int main()
{
 long long int i,j,k,s1,s2,t,p;
 long long int max=1234567890;
 max=max*8;
 while(cin>>t)
 {
  cout<<endl;
  for(p=1;p<=t;p++)
  {
   
   
   cin>>s1;
   
   for(i=s1,j=1;i<=max;i+=s1,j++)
   {
    if(check(i)&&check(j))
    cout<<i<<" / "<<j<<" = "<<s1<<endl;
   
   }

  
  }
  
 }

 return 0;
}

whats about blank lines,i dont understand it,pls help me................

j.luis · Post by **j.luis** » Mon Oct 12, 2009 5:49 pm

#include <iostream>
#include <string>
#include <sstream>
using namespace std;

#define S1_MAX 9876543210ULL

bool checkDigits(unsigned long long s1) {
string n_str = "";
ostringstream os;
os << s1;
n_str = os.str();

int dn[10] = {0};

for (int i = 0; i < n_str.length(); i++) {
if (dn[n_str-'0']>0) { return false; }
dn[n_str-'0']++;
}

return true;
}

main() {
int c;
unsigned long long s1, s2, n;

cin >> c;
for (int i = 0; i < c; i++) {
cin >> n;
for (s2 = 1; s2 <= S1_MAX/n; s2++) {
if (checkDigits(s2)) {
s1 = s2*n;
if (s1 > S1_MAX) break;
if (checkDigits(s1))
cout << s1 << " / " << s2 << " = " << n << endl;
}
}

cout << endl;
}

return 0;
}

j.luis · Post by **j.luis** » Mon Oct 12, 2009 5:55 pm

const S1_MAX=9876543210;

function find_And_Print_Solutions_For_N(var N){

var S2_MIN := 1;
var S2_MAX := S1_MAX / N;
var s1 := 0;
var s2 := 0;

LOOP -> for s2 = S2_MIN to S2_MAX do the following
{
1) if ( has_Repeated_Digits(s2) ) continue;
2) s1 := s2 * N;
3) if (s1 > S1_MAX) break;
4) if ( has_Repeated_Digits(s1) ) continue;
5) PRINT (s1 + " / " + s2 + " = " + N);
}

}

mostafiz93 · Post by **mostafiz93** » Sun Apr 29, 2012 2:24 pm

Jehad Uddin wrote:i m getting 20 WA in this problem,i m getting frustrated in this problem,pls help me.....

Code: Select all

#include<iostream>
#include<cmath>
 
using namespace std;
long long int check(long long int n)
{
 long long int a[10],k=1,i;
 for(i=0;i<10;i++) a[i]=0;
 do
 {
  if(a[n%10]==0)
  a[n%10]++;
  else k=0,a[n%10]++;
  n/=10;
 }
 while(n!=0);

 return k;
}
int main()
{
 long long int i,j,k,s1,s2,t,p;
 long long int max=1234567890;
 max=max*8;
 while(cin>>t)
 {
  cout<<endl;
  for(p=1;p<=t;p++)
  {
   
   
   cin>>s1;
   
   for(i=s1,j=1;i<=max;i+=s1,j++)
   {
    if(check(i)&&check(j))
    cout<<i<<" / "<<j<<" = "<<s1<<endl;
   
   }

  
  }
  
 }

 return 0;
}

whats about blank lines,i dont understand it,pls help me................

the value of max should be 9876543210.(think pigeon hole principle!)

Farsan · Post by **Farsan** » Sun Jan 26, 2014 6:04 pm

What if the input is
1
1
I dont think there is any efficient way to compute all the outputs within 3 seconds.

brianfry713 · Post by **brianfry713** » Mon Jan 27, 2014 10:31 pm

N = 1 does not appear in the judge's input.

nafeeur · Post by **nafeeur** » Mon Jun 09, 2014 8:05 pm

Why giving WA!!!

Code: Select all

#include <bits/stdc++.h>

using namespace std;

//define part
#define pf printf
#define sf scanf
#define inp(x) scanf("%d",&x)
#define inp2(x,y) scanf("%d%d",&x,&y)
#define inpl(x) scanf("%lld",&x)
#define inpl2(x,y) scanf("%lld%lld",&x,&y)
#define IS(s) getline(cin,s)
#define ll long long int
#define tcn printf("Case %d:\n",++cas);
#define tc printf("Case %d: ",++cas);
#define For(i,n) for(__typeof(n) i=0; i<(n); i++)
#define ForR(a,b) for(__typeof(b) i=a; i<=b; i++)
#define For1(i,n) for(__typeof(n) i=1; i<=(n); i++)
#define READ(f) freopen(f, "r", stdin)
#define WRITE(f) freopen(f, "w", stdout)
#define PI 3.1415926535897932384626433832
#define INF (1<<30)
#define eps 1e-8
#define pb push_back
#define ppb pop_back
#define mem(x,a) memset(x,a,sizeof(x));
#define out(x) printf("%d\n",x);
#define Sort(s) sort(s.begin(),s.end());
#define Rev(s) reverse(s.begin(),s.end());
#define SQR(x) ((x)*(x))
#define PI 2*acos(0)
#define EPS 1e-7
#define ALL_BITS 0xFFFFFFFF
#define NEG_BITS(mask) (mask ^ ALL_BITS)
#define TEST_BIT(mask, i) (mask & (1 << i))
#define ON_BIT(mask, i) (mask | (1 << i))
#define OFF_BIT(mask, i) (mask & (~(1 << i)))
#define FLIP_BIT(mask, i) (mask ^ (1 << i))
#define OFF_SETED_LSB(x) ( x & (x-1) )
#define SET_UNION(A,B) (A|B)
#define SET_INTERSECTION(A,B) (A&B)
#define SET_DIFFERENCE(A,B) (A& (~B))
#define CTZ(x) __builtin_ctz(x)
#define CLZ(x) __builtin_clz(x)
#define COUNT_SET_BITS(x) __builtin_popcount(x)
#define IS_POWER_OF_TWO(x) (x&(x-1))
#define mx 10010
#define ArraySize 101
#define mem2D(A,v) memset(A, v, sizeof(int [ArraySize][ArraySize]))


string numtostring(ll num)
{
    string restult;

    ostringstream con;
    con<<num;
    restult=con.str();

    return restult;
}

int stringtoint(string str)
{
    int numb;
    istringstream(str)>>numb;
    return numb;
}
ll stringtoll(string S)
{
    stringstream buffer(S);
    ll var;
    buffer >> var;
    return var;
}

int main()
{
    int t;
    int count = 0;
    long long int n;
    bool blank = false;
    cin>>t;
    getchar();

    while(t--)
    {
        count++;
		if (count > 1)
			printf("\n");
        cin>>n;
        getchar();

        string str,sm,str1,st;
        vector<string>upstring,downstring;
        vector<int>v;

        int yes=0;
        for(int i=1; ; i++)
        {
            long long int res=i*n;

            if(i>n)
                break;
            else if(res>9876543210)
                break;


            string s=numtostring(res);

            sm=s;

            int c=0;

            if(sm.size()==1)
            {
                string catchi=numtostring(i);

                if(catchi.size()==1)
                {
                    downstring.pb(catchi);
                    upstring.pb(s);
                }

                else
                {
                    string fakei=catchi;
                    int d=0;
                    Sort(fakei);
                    //cout<<fakei<<endl;

                    for(int j=0; j<fakei.size()-1; j++)
                    {
                        if(fakei[j]==fakei[j+1])
                            break;
                        else
                            d++;
                    }

                    if(d==fakei.size()-1)
                    {
                        upstring.pb(s);
                        downstring.pb(catchi);
                    }
                }
            }

            else
            {
                Sort(sm);

                for(int j=0; j<sm.size()-1; j++)
                {
                    if(sm[j]==sm[j+1])
                        break;
                    else
                        c++;
                }

                if(c==s.size()-1)
                {
                    string catchi=numtostring(i);

                    if(catchi.size()==1)
                    {
                        downstring.pb(catchi);
                        upstring.pb(s);
                    }

                    else
                    {
                        string fakei=catchi;
                        int d=0;
                        Sort(fakei);

                        for(int j=0; j<fakei.size()-1; j++)
                        {
                            if(fakei[j]==fakei[j+1])
                                break;
                            else
                                d++;
                        }

                        if(d==fakei.size()-1)
                        {
                            upstring.pb(s);
                            downstring.pb(catchi);
                        }
                    }
                }
            }

        }

        for(int k=0; k<upstring.size(); k++)
        {
            cout<<upstring[k]<<" / "<<downstring[k]<<" = "<<n<<endl;
        }

        downstring.clear();
        upstring.clear();
        str.clear();
        sm.clear();
        str1.clear();
        st.clear();

    }
    return 0;
}

brianfry713 · Post by **brianfry713** » Wed Jun 11, 2014 10:22 pm

Try the I/O in this thread posted by dip » Tue Nov 30, 2004 7:24 am

uDebug · Post by **uDebug** » Sat Jun 14, 2014 7:26 am

dip's posts are useful but, unfortunately, they are wrong (on the format front). Posting dip's input again so someone doing a quick sanity check doesn't need to waste time examining the output for correctness because of the incorrect spacing (which does lead to a WA).

Test Case #1
Input:

Code: Select all

AC Output:

Code: Select all

1245698 / 1 = 1245698
12456980 / 10 = 1245698
73496182 / 59 = 1245698
429765810 / 345 = 1245698
734961820 / 590 = 1245698
9215673804 / 7398 = 1245698

52369874 / 1 = 52369874
261849370 / 5 = 52369874
523698740 / 10 = 52369874

741852963 / 1 = 741852963
1483705926 / 2 = 741852963
3709264815 / 5 = 741852963
7418529630 / 10 = 741852963

963852741 / 1 = 963852741
4819263705 / 5 = 963852741
9638527410 / 10 = 963852741

358947126 / 1 = 358947126
3589471260 / 10 = 358947126

Test Case #2
Input:

Code: Select all

1

52364

AC Output:

Code: Select all

52364 / 1 = 52364
104728 / 2 = 52364
157092 / 3 = 52364
209456 / 4 = 52364
523640 / 10 = 52364
680732 / 13 = 52364
785460 / 15 = 52364
1832740 / 35 = 52364
1937468 / 37 = 52364
3089476 / 59 = 52364
4398576 / 84 = 52364
5602948 / 107 = 52364
6912048 / 132 = 52364
9530248 / 182 = 52364
9687340 / 185 = 52364
12357904 / 236 = 52364
13824096 / 264 = 52364
18275036 / 349 = 52364
19374680 / 370 = 52364
21573968 / 412 = 52364
35974068 / 687 = 52364
38906452 / 743 = 52364
41629380 / 795 = 52364
43985760 / 840 = 52364
50374168 / 962 = 52364
51369084 / 981 = 52364
56134208 / 1072 = 52364
57024396 / 1089 = 52364
63150984 / 1206 = 52364
65873912 / 1258 = 52364
81059472 / 1548 = 52364
107398564 / 2051 = 52364
138974056 / 2654 = 52364
154369072 / 2948 = 52364
154630892 / 2953 = 52364
170392456 / 3254 = 52364
190657324 / 3641 = 52364
215739680 / 4120 = 52364
273916084 / 5231 = 52364
309261784 / 5906 = 52364
317954208 / 6072 = 52364
457923180 / 8745 = 52364
483529176 / 9234 = 52364
490231768 / 9362 = 52364
507983164 / 9701 = 52364
508349712 / 9708 = 52364
516937408 / 9872 = 52364
547360892 / 10453 = 52364
658739120 / 12580 = 52364
725189036 / 13849 = 52364
807924156 / 15429 = 52364
817035492 / 15603 = 52364
860759432 / 16438 = 52364
914537260 / 17465 = 52364
940876352 / 17968 = 52364
965173248 / 18432 = 52364
965382704 / 18436 = 52364
976431508 / 18647 = 52364
1659834072 / 31698 = 52364
2560913784 / 48906 = 52364
3028419576 / 57834 = 52364
4516237908 / 86247 = 52364
4835291760 / 92340 = 52364
5139264780 / 98145 = 52364
6915032748 / 132057 = 52364
9651732480 / 184320 = 52364

brianfry713 · Post by **brianfry713** » Wed Oct 22, 2014 12:03 am

In the judge's input all N values are >= 10000.

OJ Board

471 - Magic Numbers

471 OLE Help Please !!!!

Re: Hey Need Some I/O of 471 [Magic Numbers]

Re: 471 compile error

Re: 471 compile error

Re: Hey Need Some I/O of 471 [Magic Numbers]

Re: Hey Need Some I/O of 471 [Magic Numbers]

Re: Hey Need Some I/O of 471 [Magic Numbers]

Re: Hey Need Some I/O of 471 [Magic Numbers]

Re: Hey Need Some I/O of 471 [Magic Numbers]

Re: Hey Need Some I/O of 471 [Magic Numbers]

Re: 471 - Magic Numbers