11371 - Number Theory for Newbies

[Observer]

I think you can assume that double gives at least 12 digits of precision for this problem, which is more than enough (we only have to handle 10-digit numbers).

Judge solution uses int64 (PASCAL).

[hamedv]

I solved this problem by next_permutation() and prev_permutation().
is there any other way to solve this problem?

[jurajz]

I used int64 in Pascal, it is enough, because 9 223 372 036 854 775 807 is much greater than 9 999 999 991. And my method was arrange suitable the digits from input number n, for maximum number and minimum number. But remember, all digits must be used, including zeroes.

[sohel]

I solved this problem by next_permutation() and prev_permutation().
is there any other way to solve this problem?

There is a greedy approach!

The largest number can be found by sorting the input number in descending order.

The smallest one can be found by sorting in ascending order.. but there could be a case of leading 0. By swapping the smallest non zero digit with the first zero, this can be handled.

Example :
Input --> 12300

Largest number - 32100
Smallest number - 00123 --> 10023

[Eiger Yap]

...

[black.phoenix]

There is a greedy approach!

The largest number can be found by sorting the input number in descending order.

The smallest one can be found by sorting in ascending order.. but there could be a case of leading 0. By swapping the smallest non zero digit with the first zero, this can be handled.

Example :
Input --> 12300

Largest number - 32100
Smallest number - 00123 --> 10023

I think this is the easy way to solve this problem but in order to sort the input you should treat it as a string.

To avoid this and make things faster I declared an int array with 10 positions to store how many 0-9 the input number has. Then store in a long long the biggest number N (initializing with 0 first) possible from some permutation using a for loop from 9 to 0 and while there's a digit multiply n by 10 and sum the digit. This number would be "a".

After, we can find "b" making the "inverse", that is, getting from last digit of "a" to first (getting remainders of 10) in order to find the smallest number. The leading zeroes case can be treated saving in a variable how many zeros stored in array were found, count the number of digits of "b" (which can be done while finding "b") then calculate 10^(number of zeros + number of digits of "b" - 1), multiply it by ("b" divided by 10^(number of digits of "b" - 1)) and sum the remainder of ("b" divided by 10^(number of digits of "b" - 1)).

I wasn't getting Accepted due to a formatting problem. The problem I was having is that I was using Dev-C++ in Windows and "%lld" does not work as a format to printf, so I thought my program was wrong. Instead, you must use "%I64d" which is a Windows thing even though Dev-C++ use the gcc compiler. But for submitting I changed to "%lld" because I think the grader is running under Linux and it got accepted.

If my explanation is not clear I can post part of the code.

[black.phoenix]

Type Bits

int 16
long 32
long long 64

I think int is either 16 or 32, it depends on your system. Declaring short guarantees 16, long 32 and long long 64.

Can unsigned long long (in theory up to 18,xxx,xxx,xxx,xxx,xxx,xxx) solve the problem?, does unsigned long long really exists? (I know is an stupid question, but here in my computer I tried to make calculations with 10-digit numbers with unsigned long long and it make wrong answers, but clearly, it could be my compiler, and UVa can accept that)

If uva can accept and your computer gives wrong answer maybe it's the same problem I was facing. I was using Dev-C++ in Windows and Windows uses "%I64d" for long long while in Linux it's "%lld". For unsigned long long it's "%I64u" in Windows and "%llu" in Linux.

[mf]

For unsigned long long it's "%I64u" in Windows

That depends on your compiler. I use cygwin and it's %llu for me
Visual Studio 2005 also supports %llu.

[fpavetic]

For unsigned long long it's "%I64u" in Windows

That depends on your compiler. I use cygwin and it's %llu for me
Visual Studio 2005 also supports %llu.

if i am not mistaken Dev-C++ uses MinGW compiler, and there long long is printed differently than "%lld"

[apurba]

what should be output for these input????????

Code: Select all

100
500
10000
0005

some one get acc help pls........

thanks in advance.........

[andmej]

what should be output for these input????????

Code: Select all

100
500
10000
0005

some one get acc help pls........

thanks in advance.........

The output for the first three cases is

Code: Select all

100 - 100 = 0 = 9 * 0
500 - 500 = 0 = 9 * 0
10000 - 10000 = 0 = 9 * 0

The last input is wrong: There are no inputs with leading zeros in the judge's input.

Be careful with overflows.

[Mohamed Abd El-Monem]

i tried all test cases and get correct answer
but i get WA from the judje
please any help
this is my code

Code: Select all

# include <iostream>
# include <algorithm>
# include <stdlib.h>
# include <string>
using namespace std;


long long int GetIntVal(string strConvert)
{ 
  long long int intReturn; 

  intReturn = atoi(strConvert.c_str()); 

  return(intReturn); 
}



int main()
{
	char num[11];
	while(gets(num))
	{
		int size = strlen(num);
		long long int ReversedNumber,Number,diff,divisor;
		Number = GetIntVal(num);
		sort(num,num+size);
		reverse(num,num+size);
		ReversedNumber = GetIntVal(num);
		diff = ReversedNumber - Number;
		divisor = diff / 9;
		cout<<ReversedNumber<<" - "<<Number<<" = "<<diff<<" = 9 * "<<divisor<<endl;

	}
	return 0;
}

thanx in advance

[andmej]

Input:

Code: Select all

123450

Your code outputs

Code: Select all

543210 - 123450 = 419760 = 9 * 46640

The correct answer is

Code: Select all

543210 - 102345 = 440865 = 9 * 48985

Good luck.

[amr saqr]

I don't know why am i getting Wrong Answer !!
here is my code, please help

Code: Select all

#include <iostream>
#include <string>
#include <sstream>
#include <algorithm>
using namespace std;
int main()
{
	string number;
	long long no;
	long long a;
	long long b;
	while (cin>>no)
	{
		ostringstream oss;
		oss<<no;
		number=oss.str();
		sort(number.begin(),number.end());
		if (number.length()>1)
		{
			if (number[0]-48==0)
			{
				int index=0;
				while (number[index]-48==0)
					index++;
				char temp=number[index];
				number[index]=number[0];
				number[0]=temp;
			}
		}
		string::reverse_iterator it;
		int pos=1;
		b=0;
		for (it=number.rbegin();it<number.rend();it++)
		{
			b+=((*it)-48)*pos;
			pos*=10;
		}
		sort(number.begin(),number.end());
		reverse(number.begin(),number.end());
		pos=1;
		a=0;
		for (it=number.rbegin();it<number.rend();it++)
		{
			a+=((*it)-48)*pos;
			pos*=10;
		}
		long long diff=a-b;
		long long div=diff/9;
		printf("%I64d - %I64d = %I64d = 9 * %I64d\n",a,b,diff,div);
		
	}
	return 0;
}

[sohel]

Code: Select all

for (it=number.rbegin();it<number.rend();it++)
      {
         a+=((*it)-48)*pos;
         pos*=10;
      }

even though a is declared as long long, but the RHS of the expression returns an integer and causes overflow.

Typecasting with (long long) should solve the problem.

a+=(long long)((*it)-48)*pos;