AtCoder Regular Contest #039 A問題 - A - B problem

Source

AtCoder Regular Contest #039
問題文

問題概要

三桁の正整数 $A,B$ が与えられる．
$A$ か $B$ かどちらの桁を $1$ 桁だけ変えることができる（変えなくても良い）．
ただし，最初の桁を $0$ にしてはいけない．
そのような変更した後の $A-B$ の最大値を求める問題．

解法

どの桁をどの数字に変えるかを全探索すれば良い．
$A$ を変更するか，$B$ を変更するかの $2$ パターンに分類すれば，できるだけ上の桁をできるだけ増加／減少させるのが良いので貪欲にも解ける．

C++によるスパゲッティなソースコード

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

#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define mygc(c) (c)=getchar_unlocked()
#define mypc(c) putchar_unlocked(c)

int reader(char c[]){int i,s=0;for(;;){mygc(i);if(i!=' '&&i!='\n'&&i!='\r'&&i!='\t'&&i!=EOF) break;}c[s++]=i;for(;;){mygc(i);if(i==' '||i=='\n'||i=='\r'||i=='\t'||i==EOF) break;c[s++]=i;}c[s]='\0';return s;}
template <class T, class S> void reader(T *x, S *y){reader(x);reader(y);}

void writer(int x, char c){int s=0,m=0;char f[10];if(x<0)m=1,x=-x;while(x)f[s++]=x%10,x/=10;if(!s)f[s++]=0;if(m)mypc('-');while(s--)mypc(f[s]+'0');mypc(c);}
template<class T> void writerLn(T x){writer(x,'\n');}

char A[10], B[10];

int main(){
  int i, j, m;
  int res = -9999, tmp;

  reader(A,B);

  rep(i,3) REP(j,'0','9'+1){
    if(i==0 && j=='0') continue;
    m = A[i];
    A[i] = j;
    tmp = atoi(A) - atoi(B);
    res = max(res, tmp);
    A[i] = m;
  }
  rep(i,3) REP(j,'0','9'+1){
    if(i==0 && j=='0') continue;
    m = B[i];
    B[i] = j;
    tmp = atoi(A) - atoi(B);
    res = max(res, tmp);
    B[i] = m;
  }

  writerLn(res);

  return 0;
}

Current time: 2024年04月25日07時05分10秒
Last modified: 2015年07月01日06時50分19秒 (by laycrs)
Tags: Competitive_Programming AtCoder AtCoder_Regular_Contest ARC039 ARC_A
トップページに戻る

Logged in as: unknown user (not login)

ログイン：