Codeforces Round #104 (Div. 1) B : Lucky Number 2
問題概要
4がa1個、7がa2個、47がa3個、74がa4個部分文字列として含まれる辞書順最小の部分文字列を求める問題。できないときは指摘。
解法
場合分けでといたが、それはあまりよくない。辞書順最小の定石どおり、判定問題に落として解くべきだった。
acceptされたコード
#include <cstdio> #include <algorithm> using namespace std; const int MAX_L = 1e6; int A, B, C, D; char buf[MAX_L*2 + 1]; void init(){ scanf("%d%d%d%d", &A, &B, &C, &D); } void solve(){ int p = 0; if(A < C || A < D || B < C || B < D){ puts("-1"); return ; } if( C == D ){ if(A == C && B == D){ puts("-1"); return ; } if(A > C){ for(int i=0; i<A-C-1; i++){ buf[p++] = '4'; } for(int i=0; i<C; i++){ buf[p++] = '4'; buf[p++] = '7'; } for(int i=0; i<B-C; i++){ buf[p++] = '7'; } buf[p++] = '4'; } else if(B > C){ buf[p++] = '7'; for(int i=0; i<C; i++){ buf[p++] = '4'; buf[p++] = '7'; } for(int i=0; i<B-C-1; i++){ buf[p++] = '7'; } } } else if( C == D + 1 ){ for(int i=0; i<A-C; i++){ buf[p++] = '4'; } for(int i=0; i<C; i++){ buf[p++] = '4'; buf[p++] = '7'; } for(int i=0; i<B-C; i++){ buf[p++] = '7'; } } else if( D == C + 1 ){ buf[p++] = '7'; buf[p++] = '4'; for(int i=0; i<A-D; i++){ buf[p++] = '4'; } for(int i=0; i<D-2; i++){ buf[p++] = '7'; buf[p++] = '4'; } for(int i=0; i<B-D; i++){ buf[p++] = '7'; } buf[p++] = '7'; buf[p++] = '4'; } else{ puts("-1"); return ; } puts(buf); } int main(){ init(); solve(); return 0; }