11371 - Number Theory for Newbies
Moderator: Board moderators
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).
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
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org
There is a greedy approach!hamedv wrote:I solved this problem by next_permutation() and prev_permutation().
is there any other way to solve this problem?
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
-
- New poster
- Posts: 8
- Joined: Sun Aug 06, 2006 3:07 am
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.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
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.
-
- New poster
- Posts: 8
- Joined: Sun Aug 06, 2006 3:07 am
Re: long long... double... HELP!
I think int is either 16 or 32, it depends on your system. Declaring short guarantees 16, long 32 and long long 64.ligregni wrote: Type Bits
int 16
long 32
long long 64
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.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)
You do not know whether the path is easy or hard unless you walk through it.
Re: 11371 - Number Theory for Newbies
what should be output for these input????????
some one get acc help pls........
thanks in advance.........
Code: Select all
100
500
10000
0005
thanks in advance.........
Code: Select all
keep dreaming...
Re: 11371 - Number Theory for Newbies
The output for the first three cases isapurba wrote:what should be output for these input????????
some one get acc help pls........Code: Select all
100 500 10000 0005
thanks in advance.........
Code: Select all
100 - 100 = 0 = 9 * 0
500 - 500 = 0 = 9 * 0
10000 - 10000 = 0 = 9 * 0
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
Are you dreaming right now?
http://www.dreamviews.com
-
- 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
please any help
this is my code
thanx in advance
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;
}
Re: 11371 - Number Theory for Newbies
Input:
Your code outputs
The correct answer is
Good luck.
Code: Select all
123450
Code: Select all
543210 - 123450 = 419760 = 9 * 46640
Code: Select all
543210 - 102345 = 440865 = 9 * 48985
Runtime errors in Pascal are reported as Wrong Answers by the online judge. Be careful.
Are you dreaming right now?
http://www.dreamviews.com
Are you dreaming right now?
http://www.dreamviews.com
Re: 11371 - Number Theory for Newbies
I don't know why am i getting Wrong Answer !!
here is my code, please help
here is my code, please help
![:oops:](./images/smilies/icon_redface.gif)
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;
}
C++ Is The Best.
Re: 11371 - Number Theory for Newbies
Code: Select all
for (it=number.rbegin();it<number.rend();it++)
{
a+=((*it)-48)*pos;
pos*=10;
}
Typecasting with (long long) should solve the problem.
a+=(long long)((*it)-48)*pos;