11371 - Number Theory for Newbies

All about problems in Volume 113. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Post by Observer » Sun Dec 30, 2007 12:18 pm

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

Post by hamedv » Sun Dec 30, 2007 1:21 pm

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

Post by jurajz » Sun Dec 30, 2007 1:39 pm

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.

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

Post by sohel » Sun Dec 30, 2007 1:52 pm

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:

Post by Eiger Yap » Sun Dec 30, 2007 3:11 pm

...
Last edited by Eiger Yap on Mon Dec 31, 2007 9:08 pm, edited 1 time in total.

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

Post by black.phoenix » Sun Dec 30, 2007 7:11 pm

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!

Post by black.phoenix » Sun Dec 30, 2007 7:31 pm

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:

Post by mf » Sun Dec 30, 2007 7:44 pm

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

Post by fpavetic » Sun Dec 30, 2007 8:29 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

Post by apurba » Mon Apr 21, 2008 7:43 am

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

Code: Select all

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

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

Code: Select all

keep dreaming...

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

Re: 11371 - Number Theory for Newbies

Post by andmej » Sun Apr 27, 2008 8:09 pm

apurba wrote: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.
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

Post by Mohamed Abd El-Monem » Mon Apr 28, 2008 4:52 pm

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

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

Re: 11371 - Number Theory for Newbies

Post by andmej » Sun May 04, 2008 6:35 am

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.
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

Post by amr saqr » Thu May 08, 2008 5:11 pm

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

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.

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

Re: 11371 - Number Theory for Newbies

Post by sohel » Fri May 09, 2008 7:32 am

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;

Post Reply

Return to “Volume 113 (11300-11399)”