Codeforces Round #184 (Div. 2) A. Strange Addition

,

問題文の読解の難易度がかなり高い問題。

A. Strange Addition

問題

非負整数の集合が与えられる。重複はない。 この集合の部分集合で、以下の条件を満たすもので、要素数が最大のものをひとつ答えよ。

  • 任意の自然数$i$に関して、その部分集合の要素の整数で、10進表記した際に$i$桁目が非零になるものが高々ひとつしかない。

解法

$d_i \le 100$という制約がある。やるだけ。

実装

まずpopcountが0,1のものだけ処理し、次に2のものを処理。

#!/usr/bin/env python3
k = int(input())
ds = list(map(int,input().split()))
es = []
bs = [False, False, False]
for d in ds:
    assert 0 <= d <= 100
    if d == 0:
        es.append(d)
    elif 1 <= d <= 9:
        if not bs[0]:
            bs[0] = True
            es.append(d)
    elif 10 <= d <= 99 and d % 10 == 0:
        if not bs[1]:
            bs[1] = True
            es.append(d)
    elif d == 100:
        if not bs[2]:
            bs[2] = True
            es.append(d)
for d in ds:
    if not bs[0] and not bs[1]:
        if 10 <= d <= 99 and d % 10 != 0:
            bs[0] = True
            bs[1] = True
            es.append(d)
print(len(es))
print(*es)