ABC解説

【pythonでABC157を解説】C - Guess The Number

問題概要

C - Guess The Number
C - Guess The Number

続きを見る

問題文

以下の条件を満たす \(0\) 以上の整数が存在すれば、それらのうち最小のものを出力してください。そのような整数が存在しなければ、 -1と出力してください。

  • 十進表記で丁度 \(N\) 桁である。(\(0\) は \(1\) 桁の整数とする。その他の整数については、先頭に \(0\) をつけた表記は認めない。)
  • 左から数えて \(s_i\) 桁目は \(c_i\) である。\(\left(i = 1, 2, \cdots, M\right)\)

制約

  • 入力は全て整数
  • \(1 \leq N \leq 3\)
  • \(0 \leq M \leq 5\)
  • \(1 \leq s_i \leq N\)
  • \(0 \leq c_i \leq 9\)

問題の考察

制約が\(1 \leq N \leq 3\)であるため答えは最小で\(1\)桁、最大で\(3\)桁になるから\(0\)から\(999\)までの間に存在することが分かるので全検索しても十分に間に合う。

答えを求める手順

  • \(0\)から\(999\)まで全検索
  • この整数が\(N\) 桁か確認
  • この整数の\(s_i\) 桁目は \(c_i\)か確認
  • 条件を満たすならその整数を出力して終了
  • \(0\)から\(999\)までに一致する整数がなければ\(-1\)を出力

問題としてはそこまで難しくないが制約が多いので問題文をきちんと正しく読みましょう。

見逃してはいけない条件

  • 答えは\(N\) 桁
  • 最小のものを出力

また、整数型\(\Leftrightarrow\)文字列型の変換をきちんとできないと正しい答えを求められないので忘れている人は復習しておきましょう。

たびすけ
制約\(1 \leq N \leq 3\)が重要なので見逃さないようにしましょう！
条件一致の確認方法は基本的な構文が目白押しなので基礎力の確認には良い問題なので是非ACできるようにしましょう！

ACコード

import sys


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n, m = list(map(int, input().rstrip('\n').split()))
    sc = [list(map(int, input().rstrip('\n').split())) for _ in range(m)]
    for i in range(1000):
        st = str(i)
        if len(st) == n:
            is_ok = True
            for s, c in sc:
                if int(st[s - 1]) != c:
                    is_ok = False
                    break
            if is_ok:
                print(i)
                exit()
    print(-1)


if __name__ == '__main__':
    solve()

-ABC解説
-