Edit

【pythonでABC182を解説】C - To 3

問題概要

問題ページ

C - To 3
C - To 3

問題ページへ移動する

問題文

各桁に \(0\) が出現しないような正の整数 \(N\) が与えられます。
\(N\) の桁数を \(k\) とします。\(N\) の桁を \(0\) 個以上 \(k\) 個未満消して、残った桁をそのままの順序で結合することで \(3\) の倍数を作りたいです。
\(3\) の倍数を作ることができるか判定し、作ることができるなら作るのに必要な最少の消す桁数を求めてください。

制約

  • \(1 \le N \lt 10^{18}\)
  • \(N\) は各桁に \(0\) が出現しない整数

問題の考察

ACコード

import sys
import itertools


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n = str(input().rstrip('\n'))
    mn = 10 ** 20
    for it_v in itertools.product([True, False], repeat=len(n)):
        t = 0
        for i in range(len(n)):
            if it_v[i]:
                t += int(n[i])
        if t % 3 == 0:
            c = it_v.count(False)
            if c < len(n):
                mn = min(mn, it_v.count(False))
    print(mn if mn != 10 ** 20 else -1)


if __name__ == '__main__':
    solve()

-Edit
-