## 11371 - Number Theory for Newbies

Moderator: Board moderators

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong
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).
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

hamedv
Learning poster
Posts: 98
Joined: Mon May 07, 2007 8:30 am
I solved this problem by next_permutation() and prev_permutation().
is there any other way to solve this problem?

jurajz
Learning poster
Posts: 69
Joined: Sat Sep 02, 2006 7:30 pm
Location: Slovakia
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
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York
hamedv wrote: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
New poster
Posts: 4
Joined: Sun Nov 18, 2007 2:30 pm
Location: Medan-Indonesia
Contact:
...
Last edited by Eiger Yap on Mon Dec 31, 2007 9:08 pm, edited 1 time in total. Visit my blog at http://eigeryap88.blogspot.com/

black.phoenix
New poster
Posts: 8
Joined: Sun Aug 06, 2006 3:07 am
sohel wrote: 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.
You do not know whether the path is easy or hard unless you walk through it.

black.phoenix
New poster
Posts: 8
Joined: Sun Aug 06, 2006 3:07 am

### Re: long long... double... HELP!

ligregni wrote: 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.
You do not know whether the path is easy or hard unless you walk through it.

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
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
Learning poster
Posts: 51
Joined: Sat Mar 04, 2006 8:00 pm
mf wrote:
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
New poster
Posts: 42
Joined: Sun Oct 07, 2007 10:29 pm

### Re: 11371 - Number Theory for Newbies

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

Code: Select all

``````100
500
10000
0005
``````
some one get acc help pls........

Code: Select all

``keep dreaming...``

andmej
Experienced poster
Posts: 158
Joined: Sun Feb 04, 2007 7:45 pm
Location: Medellin, Colombia

### Re: 11371 - Number Theory for Newbies

apurba wrote:what should be output for these input????????

Code: Select all

``````100
500
10000
0005
``````
some one get acc help pls........

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.
Runtime errors in Pascal are reported as Wrong Answers by the online judge. Be careful.

Are you dreaming right now?
http://www.dreamviews.com

Mohamed Abd El-Monem
New poster
Posts: 15
Joined: Mon Mar 31, 2008 1:20 am
Location: Egypt
Contact:

### Re: 11371 - Number Theory for Newbies

i tried all test cases and get correct answer
but i get WA from the judje
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;
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;
}``````

andmej
Experienced poster
Posts: 158
Joined: Sun Feb 04, 2007 7:45 pm
Location: Medellin, Colombia

### Re: 11371 - Number Theory for Newbies

Input:

Code: Select all

``123450``

Code: Select all

``````543210 - 123450 = 419760 = 9 * 46640
``````

Code: Select all

``````543210 - 102345 = 440865 = 9 * 48985
``````
Good luck.
Runtime errors in Pascal are reported as Wrong Answers by the online judge. Be careful.

Are you dreaming right now?
http://www.dreamviews.com

amr saqr
New poster
Posts: 29
Joined: Tue Mar 11, 2008 6:35 pm

### Re: 11371 - Number Theory for Newbies

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-48==0)
{
int index=0;
while (number[index]-48==0)
index++;
char temp=number[index];
number[index]=number;
number=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;
}``````
C++ Is The Best.

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

### Re: 11371 - Number Theory for Newbies

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;