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

Obaida
A great helper
Posts: 380
Joined: Wed Jan 16, 2008 6:51 am
Location: (BUBT) Dhaka,Bagladesh.

Re: 11371 - Number Theory for Newbies

Post by Obaida » Wed Jan 07, 2009 8:02 am

I don't know when this kidding WA leave me.
I can't get Accepted in this problem. Someone please help me. :oops:

Code: Select all

removed
Last edited by Obaida on Sat Jan 10, 2009 8:20 am, edited 1 time in total.
try_try_try_try_&&&_try@try.com
This may be the address of success.

shiplu_1320
New poster
Posts: 32
Joined: Sat Dec 29, 2007 9:08 pm
Location: CSEDU , Dhaka
Contact:

Re: 11371 - Number Theory for Newbies

Post by shiplu_1320 » Wed Jan 07, 2009 11:20 am

use long long :)
A learner......

Obaida
A great helper
Posts: 380
Joined: Wed Jan 16, 2008 6:51 am
Location: (BUBT) Dhaka,Bagladesh.

Re: 11371 - Number Theory for Newbies

Post by Obaida » Sat Jan 10, 2009 8:19 am

Thanks bt still WA!!!

Code: Select all

removed
Last edited by Obaida on Sat Jan 10, 2009 11:39 am, edited 1 time in total.
try_try_try_try_&&&_try@try.com
This may be the address of success.

newkid
Learning poster
Posts: 73
Joined: Fri Dec 12, 2008 3:06 am

Re: 11371 - Number Theory for Newbies

Post by newkid » Sat Jan 10, 2009 11:27 am

I think its printing problem. try the following.. notice the LL suffix after 9.

Code: Select all

    if(y>x)
      printf("%lld - %lld = %lld = %lld * %lld\n",y,x,y-x,9LL,(y-x)/9);
    else
      printf("%lld - %lld = %lld = %lld * %lld\n",x,y,x-y,9LL,(x-y)/9);
hmm..

Obaida
A great helper
Posts: 380
Joined: Wed Jan 16, 2008 6:51 am
Location: (BUBT) Dhaka,Bagladesh.

Re: 11371 - Number Theory for Newbies

Post by Obaida » Sat Jan 10, 2009 12:32 pm

Thank you for help.
I got Accepted. :D
try_try_try_try_&&&_try@try.com
This may be the address of success.

reazul
New poster
Posts: 1
Joined: Sun Jan 24, 2010 9:34 am

Re: 11371 - Number Theory for Newbies

Post by reazul » Sun Jan 24, 2010 9:38 am

i'm getting WA can anybody help please...thnx in advance.
the code:

Code: Select all

#include<iostream>
#include<math.h>
using namespace std;

int main(){
	char a[15];
	int b[15],f[15];
	int c,d,e,t,q=10;
	long double r=0,s=0,ans;
 
#ifndef ONLINE JUDGE
	freopen("11371.txt","r",stdin);
#endif

	while(gets(a)){
		for(c=0;a[c];c++){
			b[c]=a[c]-49+1;
			f[c]=b[c];
			
		}
		for(d=1;d<c;++d){
			for(e=c-1;e>=d;--e){
				if(b[e-1]>b[e]){
				t=b[e-1];
				b[e-1]=b[e];
				b[e]=t;
				}
			}
		}
		for(d=1;d<c;++d){
			for(e=c-1;e>=d;--e){
				if(f[e-1]<f[e]){
				t=f[e-1];
				f[e-1]=f[e];
				f[e]=t;
				}
			}
		}
		if(b[0]==0){
			for(d=0;d<c;d++){
				if(b[d]>0){
					t=b[d];
					b[d]=0;
					b[0]=t;
					break;
				}
			}
		}
		r=0;
		for(d=0;d<c;d++){
			r=r+ pow(static_cast<long double>(q),static_cast<long double>(c-d-1.00))*(static_cast<long double>(b[d]));
		
		}
		s=0;
		for(d=0;d<c;d++){
			s=s+ pow(static_cast<long double>(q),static_cast<long double>(c-d-1.00))*(static_cast<long double>(f[d]));
		
		}
		ans=s-r;
		printf("%.0Lf - %.0Lf = %.0Lf = 9 * %.0Lf\n",s,r,ans,(ans)/(9));
		
		
	}

	return 0;
}

User avatar
plamplam
Experienced poster
Posts: 150
Joined: Fri May 06, 2011 11:37 am

Re: 11371 - Number Theory for Newbies

Post by plamplam » Tue Jun 14, 2011 7:35 am

100
100 - 100 = 0 = 9 * 0
100102
211000 - 100012 = 110988 = 9 * 12332
910291
992110 - 101299 = 890811 = 9 * 98979
1
1 - 1 = 0 = 9 * 0
2
2 - 2 = 0 = 9 * 0
10
10 - 10 = 0 = 9 * 0
11
11 - 11 = 0 = 9 * 0
12
21 - 12 = 9 = 9 * 1
99909
99990 - 90999 = 8991 = 9 * 999
1234560789
9876543210 - 1023456789 = 8853086421 = 9 * 983676269
You tried your best and you failed miserably. The lesson is 'never try'. -Homer Simpson

Mahabub Khan
New poster
Posts: 5
Joined: Sun Apr 08, 2012 5:36 pm

Re: 11371 - Number Theory for Newbies

Post by Mahabub Khan » Sun Oct 28, 2012 9:58 pm

To Mr. Sohel Hafiz

You said,
"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."

my Question is why we are using this logic?
is there any kind of rule for this?

please describe broadly or give me a
site where i will find the logic...

Thanks in advance :)

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 » Mon Oct 29, 2012 10:45 am

Well, it's kind of straight forward.

The first digit should obviously be the smallest to make the the number minimum. Since we aren't allowing leading zeros, so we must place the smallest non-zero digit. Then simply sort the remaining digits in ascending order.

shondhi
New poster
Posts: 25
Joined: Tue Oct 02, 2012 5:24 pm
Location: Chittagong
Contact:

Got WA at UVa 11371 - Number Theory for Newbies

Post by shondhi » Sat Nov 03, 2012 5:03 pm

Can anyone help to fix what's wrong in my code. Here is it:

Code: Select all

#include <iostream>
#include <cstdio>
#include <cmath>
long long Reverse(long long a)
{
    long long rev = 0, temp, digit;
    while(a > 0)
    {
        digit = a % 10;
        rev = rev * 10 + digit;
        a /= 10;
    }
    return rev;
}
using namespace std;
int main()
{
    long long a, b, c, d;
    while(scanf("%lld", &a) == 1)
    {
        b = Reverse(a);
        if(a > b)
        {
            c = (a - b);
            d = c/9;
            printf("%lld - %lld = %lld = 9 * %lld\n", a, b, c, d);
        }
        else
        {
            c = (b - a);
            d = c/9;
            printf("%lld - %lld = %lld = 9 * %lld\n", b, a, c, d);
        }
    }
    return 0;
}

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: Got WA at UVa 11371 - Number Theory for Newbies

Post by brianfry713 » Tue Nov 06, 2012 3:46 am

Input 191, correct output:911 - 119 = 792 = 9 * 88
Check input and AC output for thousands of problems on uDebug!

Mahabub Khan
New poster
Posts: 5
Joined: Sun Apr 08, 2012 5:36 pm

Re: 11371 - Number Theory for Newbies

Post by Mahabub Khan » Tue Nov 06, 2012 4:28 pm

Thank You Bro :)

User avatar
shipu_a
New poster
Posts: 23
Joined: Tue Oct 23, 2012 8:04 pm
Location: Dhaka,Bangladesh
Contact:

Re: 11371 - Number Theory for Newbies

Post by shipu_a » Mon Nov 19, 2012 7:46 pm

TLE !!! Anyone help me................. :cry:

Code: Select all

Accepted...................  :) 
Nothing is imposible in the world.....And
Never Judge a Book by Its Cover.............
BUBT_Psycho
http://uhunt.felix-halim.net/id/168573
http://shipuahamed.blogspot.com

alimbubt
New poster
Posts: 39
Joined: Tue Aug 07, 2012 10:40 pm
Location: BUBT,Dhaka, Bangladesh
Contact:

Re: 11371 - Number Theory for Newbies

Post by alimbubt » Sun Jan 06, 2013 10:00 am

Input:

Code: Select all

100102
1
3
12300
100
147020
1990
199
5501
1293
400
Output:

Code: Select all

211000 - 100012 = 110988 = 9 * 12332
1 - 1 = 0 = 9 * 0
3 - 3 = 0 = 9 * 0
32100 - 10023 = 22077 = 9 * 2453
100 - 100 = 0 = 9 * 0
742100 - 100247 = 641853 = 9 * 71317
9910 - 1099 = 8811 = 9 * 979
991 - 199 = 792 = 9 * 88
5510 - 1055 = 4455 = 9 * 495
9321 - 1239 = 8082 = 9 * 898
400 - 400 = 0 = 9 * 0
Give me six hours to chop down a tree and I will spend the first four sharpening the axe...(BUBT ILLUSION)
http://uhunt.felix-halim.net/id/155497
http://onlyprogramming.wordpress.com/

raj
Learning poster
Posts: 78
Joined: Fri Feb 15, 2013 5:39 pm

Re: Got WA at UVa 11371 - Number Theory for Newbies

Post by raj » Wed Sep 25, 2013 7:39 am

Input 191, correct output:911 - 119 = 792 = 9 * 88
Is the correct answer can also be "911 - 191 = 720 = 9 * 80" ?? because the question says about permutation...
I dont know why i am getting "Wrong Answer"... Need help please :( :(

Heres is my code..

Code: Select all

import java.io.*;
import java.util.*;
public class Main{
  
  public static String printPermutations( char [] c ) {
    String ans = "";
    char [] cc = new char[c.length];
    cc = c;
    if(( c = nextPermutation( c ) ) != null) {
      for(Character d : c){
        ans = ans + d;
      }
      return ans;
    }
    else{
      for(Character d : cc){
        ans = ans + d;
      }
      StringBuffer r = new StringBuffer(ans);
      r = r.reverse();
      ans = r+"";
      char [] n = ans.toCharArray();
      n = nextPermutation( n );
      ans = "";
      for(Character d : n){
        ans = ans + d;
      }
      return ans;   
    }
  }
  
  public static char[] nextPermutation( char[] c ) {
    // 1. finds the largest k, that c[k] < c[k+1]
    int first = getFirst( c );
    if ( first == -1 ) return null; // no greater permutation
    // 2. find last index toSwap, that c[k] < c[toSwap]
    int toSwap = c.length - 1;
    while ( c[ first ]>=( c[ toSwap ] ))
      --toSwap;
    // 3. swap elements with indexes first and last
    swap( c, first++, toSwap );
    // 4. reverse sequence from k+1 to n (inclusive) 
    toSwap = c.length - 1;
    while ( first < toSwap )
      swap( c, first++, toSwap-- );
    return c;
  }
  
  public static int getFirst( char [] c ) {
    for ( int i = c.length - 2; i >= 0; --i )
      if ( c[ i ]<( c[ i + 1 ] ))
      return i;
    return -1;
  }
  
  // swaps two elements (with indexes i and j) in array 
  public static void swap( char [] c, int i, int j ) {
    char tmp = c[ i ];
    c[ i ] = c[ j ];
    c[ j ] = tmp;
  }
  
  
  public static void main(String[] args)throws IOException {
    BufferedReader k = new BufferedReader(new InputStreamReader(System.in));
    //BufferedReader k = new BufferedReader(new FileReader("E:/Uva-input.txt.txt"));
    PrintWriter z = new PrintWriter(System.out);
    String line;
    while((line = k.readLine())!=null){
      String line2 = "";
      if(line.length()!=1){
        char [] j = line.toCharArray();
        line2 = printPermutations(j);
      }
      else{
        line2 = line;
      }
      long n = Long.valueOf(line);
      long m = Long.valueOf(line2);
      long max = 0,min = 0;
      if(n>m){
        max = n;min = m;
      }
      else{
        max = m;min = n;
      }
      long ans = max - min;
      z.println(max+" - "+min+" = "+(ans)+" = 9 * "+(ans/9));
    }
    z.flush();
  }
}

Post Reply

Return to “Volume 113 (11300-11399)”