【ABC157 C】「Guess The Number」を解く【Python3】

コンテスト一覧へ

 

条件を満たす0以上の整数がある場合、最小のものを出力する問題です。

「0は1桁の整数。その他の整数については、先頭に0をつけた表記は認めない」と言う条件に注意が必要です。

提出
n, m = map(int, input().split())

li = [0] * n

for i in range(m):
    si, ci = map(int, input().split())
    if li[si-1] != 0 and li[si-1] != ci:
        print(-1)
        exit(0)
    if si == 1 and ci == 0:
        if n > 1:
            print(-1)
            exit(0)
    li[si-1] = ci

if n > 1 and li[0] == 0:
    li[0] = 1

for i in range(n):
    print(li[i], end="")

最初に0で埋めたリストを作成します。

このリストに si,ci の条件を用いて入力をしていき、矛盾しない整数を作ります。

リストのインデックスは0始まりなので、リスト内の「si-1」にciを入力することを考えます。

このとき、「li[si-1]」の値が、0でもciでもない場合は、「-1」を出力してプログラムを終了させます。

0でもciでもないということは、すでに指定の数を入力しており、これから入力するciとも異なるということで、矛盾してしまうためです。

同じように、si(左から数えた桁数)が1で、ciが0の場合も同様に矛盾します。

ただ、nが1の場合のみ、1桁で0ということがあり得るので、「n>1」を条件に加えています。

 

そのほか、すべての整数のパターンを調べる方法もあります。

Nが3以下、条件のMも5以下であるので、時間的にも間に合います。

提出
n, m = map(int, input().split())
sc_li = [list(map(int,input().split())) for _ in range(m)]
sc = []
ans = ""

for i in range(1000):
    flag = True
    ans = str(i)
    if len(ans) != n:
        continue
    for j in range(m):
        si, ci = sc_li[j]
        if int(ans[si-1]) != ci:
            flag = False
    if flag:
        print(ans)
        exit(0)

print(-1)

試す整数は0〜999です。

flagを「True」にしておきます。

整数を文字列に変換し、長さがn以下の場合は、「continue」で次の整数を試します。

すべての siを判定して、ciと異なるものが出てきたら、flagが「False」になります。

最後まで「True」だった最初の数(ansは文字列のまま出力してOK)が答えになり、999まで試して、条件に合うものがない場合は「-1」を出力します。

【ABC157】解説記事リスト

コンテスト一覧に戻る

コメントを残す

メールアドレスが公開されることはありません。