まず最初にわかったのは、各和の総和を求める関数fnがあったとき、
- f(x)=N かつ f(2x)=M を満たす正整数 x が存在するような，最大の正整数 M．
- そのような M に対して，f(x)=N かつ f(2x)=M を満たす最小の正整数 x．
ということから、
2 * fn(x) = fn(2i)
が成り立つ最初のxを見つけられればOKということ。
なのだけど、これを全て探そうとすると、例3の入力値100が与えられた時でさえTLEで追いつかない。
なので考え方を変えて、
f(x)=N
を満たす、xの中から fn(2x) = M になるものを探す作戦を次に思いついた。
f(x)=Nを満たすものは、
N=3のとき、
3, 12, 21, 102, 111, 120, 201, 210, ...
N=6のとき、
6, 15, 24, 33, 42, 51, 105, 114, 123, 132, 141, 150, ...
という塩梅。
これに2番目の条件、 f(x)=N かつ f(2x)=M に当てはめると、
N=3のとき、
x : 3, 12, 21, 102, 111, 120, 201, 210, ...
2x: 6, 24, 42, 204, 222, 240, 402, 420, ...
M : 6, 6, 6, 6, 6, 6, 6, 6, ...
N=6のとき、
x : 6, 15, 24, 33, 42, 51, 105, 114, 123, 132, 141, 150, ...
2x:12, 30, 48, 66, 84,102, 210, 228, 246, 264, 282, 300, ...
M : 3, 3, 12, 12, 12, 3, 3, 12, 12, 12, 12, 3, ...
と、xの全ての桁の数字が4以下の場合、 2N = Mが成り立ち。
5以上の数字が1つでもあると、2N > Mが成り立つことがわかり、
Mは最大のMを求めるので、2Nが最大値である。（→1行目に出力する。）
また最大のMのときのxなので、Mは4以下の数字で構成されているということがわかるので、
4413 3324 4441 のような数字になるのがわかる。
- 大きい位に大きい数字が入るより、1の位から大きい数字が入っているものの方が数字が小さくなる。
-
N%4が1~3の時、3444と4344なら、3444の方が小さいxとなる。 - 桁は少ない方がいい。
-
-
N%4が0の時は、先頭には0がつけられない。
から、xの最小値は一番下の桁から4埋めして先頭に N%4 をつければよい。
以上により、下記でACになる。
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
int m = 2 * n;
cout << m << endl;
int f = n%4;
int c = n/4;
if (f != 0) {
cout << f ;
}
for (int i=0; i<c; i++) {
cout << "4" ;
}
cout << endl;
}