結果
| 問題 |
No.653 E869120 and Lucky Numbers
|
| コンテスト | |
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 12:57:38 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 70 ms / 2,000 ms |
| コード長 | 6,631 bytes |
| コンパイル時間 | 140 ms |
| コンパイル使用メモリ | 82,732 KB |
| 実行使用メモリ | 80,700 KB |
| 最終ジャッジ日時 | 2025-05-14 12:59:13 |
| 合計ジャッジ時間 | 2,491 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 31 |
ソースコード
import sys
# Set a higher recursion depth limit if needed, although this solution is iterative.
# sys.setrecursionlimit(21000)
def solve():
# Read the input number p as a string
p_str = sys.stdin.readline().strip()
N = len(p_str)
# Handle edge case: If p is an empty string (based on constraints p >= 1, N should be >= 1)
# If N=0, p is empty string or 0. If p=0, it cannot be represented as sum of two positive lucky numbers.
if N == 0:
print("No")
return
# Convert the string p into a list of digits. Reverse it to process from right to left (units digit first).
# p_digits[i] will be the i-th digit from the right (0-indexed).
p_digits = [int(d) for d in p_str]
p_digits.reverse()
# Initialize DP table using a list of sets.
# dp[i] will store the set of reachable states after processing column i-1 (before processing column i).
# Each state is a tuple: (carry_in, a_ended, b_ended, a_non_zero, b_non_zero)
# carry_in: The carry coming into column i from column i-1. Can be 0 or 1.
# a_ended: Boolean flag, True if number 'a' has already terminated (all subsequent digits must be 0).
# b_ended: Boolean flag, True if number 'b' has already terminated.
# a_non_zero: Boolean flag, True if 'a' has had at least one non-zero digit (6 or 7) assigned so far.
# b_non_zero: Boolean flag, True if 'b' has had at least one non-zero digit (6 or 7) assigned so far.
# The maximum number of states per column is 2*2*2*2*2 = 32. Storing states in a set automatically handles duplicates.
dp = [set() for _ in range(N + 1)]
# Base case: Before processing any digits (at column 0), the carry is 0.
# Both numbers 'a' and 'b' are considered active (not ended, so za=False, zb=False).
# Initially, neither 'a' nor 'b' has been assigned a non-zero digit (so nza=False, nzb=False).
dp[0].add((0, False, False, False, False))
# Iterate through the columns, corresponding to the digits of p from right to left (0 to N-1).
for i in range(N):
# Optimization: If dp[i] is empty, it means no valid assignment of digits
# could produce the prefix of p processed so far. Thus, no solution is possible.
if not dp[i]:
break
# Get the current digit of p we need to match.
current_p_digit = p_digits[i]
# Explore transitions from each reachable state at column i.
for state in dp[i]:
# Unpack the current state tuple
c, za, zb, nza, nzb = state
# Determine the possible digits (da) for number 'a' at the current column i.
# If 'a' has already ended (za is True), the only possible digit is 0.
# If 'a' is still active (za is False), the possible digits are 6, 7, or 0.
# Choosing 0 when za is False signifies that 'a' terminates at this point (ends just before this column).
possible_da = [0] if za else [6, 7, 0]
# Determine the possible digits (db) for number 'b' similarly.
possible_db = [0] if zb else [6, 7, 0]
# Iterate through all valid combinations of digits (da, db) for the current column i.
for da in possible_da:
# The check `if za and da != 0: continue` is implicitly handled by how possible_da is generated.
# If za is True, possible_da is only [0]. So da is always 0.
for db in possible_db:
# Similarly, `if zb and db != 0: continue` is implicitly handled.
# Calculate the sum for the current column: digit_a + digit_b + carry_in
current_sum = da + db + c
# Check if the unit digit of the sum matches the required digit of p for this column.
if current_sum % 10 == current_p_digit:
# Calculate the carry for the next column (i+1).
next_c = current_sum // 10
# The carry can only be 0 or 1 because max sum is 7+7+1 = 15.
# If next_c > 1, it implies an impossible situation or error. We can skip.
if next_c > 1: continue
# Determine the state flags for the next column (i+1):
# next_za: 'a' ends if it was already ended (za=True) OR if the chosen digit da is 0.
next_za = za or (da == 0)
# next_zb: 'b' ends if it was already ended (zb=True) OR if the chosen digit db is 0.
next_zb = zb or (db == 0)
# next_nza: 'a' is considered non-zero if it was already non-zero (nza=True) OR if the chosen digit da is non-zero (6 or 7).
next_nza = nza or (da != 0)
# next_nzb: 'b' is considered non-zero if it was already non-zero (nzb=True) OR if the chosen digit db is non-zero (6 or 7).
next_nzb = nzb or (db != 0)
# Add the computed next state to the set of reachable states for column i+1.
dp[i+1].add((next_c, next_za, next_zb, next_nza, next_nzb))
# After iterating through all N columns (0 to N-1):
# The final states are stored in dp[N]. These states represent the status after processing the most significant digit p_{N-1}.
# A valid solution requires finding a state in dp[N] that meets the problem criteria.
found_solution = False
for state in dp[N]:
c, za, zb, nza, nzb = state
# Check for the conditions of a valid solution:
# 1. The final carry (carry out of the last processed column N-1, which is carry *into* column N) must be 0.
# This ensures the sum matches p exactly and doesn't require an extra digit.
# 2. Both constructed numbers 'a' and 'b' must be non-zero (positive). This is tracked by nza and nzb flags.
# A lucky number must be positive by definition ("0 is not a lucky number").
if c == 0 and nza and nzb:
found_solution = True
break # Found a valid solution, no need to check further states.
# Output the final result based on whether a valid solution was found.
if found_solution:
print("Yes")
else:
print("No")
# Call the solve function to run the logic.
solve()