読者です 読者をやめる 読者になる 読者になる

UVa11371 Number Theory for Newbies

問題
http://uva.onlinejudge.org/external/113/11371.html

概要
入力の数字 N を並び替えた数字 a, b がある。a - b が 9 の倍数になり、かつ a - b が最大になるような a, b を求めよ。ただし、a, b はleading 0 となるような数字であってはならない。

解法
a は数字列の降順ソート、b は昇順ソートしたものとする。

(i) b がleading 0 でないとき、a-b がそのまま 9 の倍数となる。

(ii) b が leading 0 のとき、0 でない最小の値を先頭の 0 とswap() する。
9 の倍数の最大が swap() 後の reverse() を a とする場合と一致しないことがあるため、後ろから next_permutation() して最大値を見つける必要があると思う。ただ、next_permutation() しなくても、swap() の後にもう一度ソートしてから逆順にするとジャッジを通せる。理由は分からない。

#include <bits/stdc++.h>
using namespace std;

#define ALL(x) (x).begin(), (x).end()
typedef long long ll;
inline ll toLL(string s) { return atoll(s.c_str()); }

int main() {
  string s;
  while(cin >> s) {
    
    sort(ALL(s));
    
    if(s[0] == '0') {
      for(int i=1; i<s.size(); i++)
        if(s[i] != '0') { swap(s[0], s[i]); break; }
    }
    
    ll b = toLL(s);
    sort(ALL(s)); reverse(ALL(s)); // <-> do {...} while(next_permutation(...));
    ll a = toLL(s);
    cout << a << " - " << b <<  " = " << a-b <<  " = 9 * " << (a-b)/9 << endl;
  }
  
  return 0;
}