結果
| 問題 |
No.281 門松と魔法(1)
|
| コンテスト | |
| ユーザー |
 gew1fw
|
| 提出日時 | 2025-06-12 16:46:48 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 6,659 bytes |
| コンパイル時間 | 173 ms |
| コンパイル使用メモリ | 82,320 KB |
| 実行使用メモリ | 54,892 KB |
| 最終ジャッジ日時 | 2025-06-12 16:47:51 |
| 合計ジャッジ時間 | 3,568 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 46 WA * 11 |
ソースコード
def main():
import sys
input = sys.stdin.read().split()
d = int(input[0])
H = list(map(int, input[1:4]))
H1, H2, H3 = H
if d == 0:
# Check if already valid
valid = False
if H1 != H2 and H2 != H3 and H1 != H3:
if (H2 > H1 and H2 > H3) or (H2 < H1 and H2 < H3):
valid = True
print(0 if valid else -1)
return
INF = float('inf')
def compute_pattern1():
min_total = INF
# Try k2 from 0 to 100
for k2 in range(0, 101):
X = H2 - k2 * d
if X < 0:
continue
# Y and Z must be < X, and Y != Z
# Compute k1 and k3
if X == 0:
continue # Y and Z must be <0, impossible
# For H1
numerator = H1 - (X - 1)
if numerator <= 0:
k1_min = 0
else:
k1_min = (numerator + d - 1) // d
k1_max = H1 // d
if k1_min > k1_max:
continue
# For H3
numerator3 = H3 - (X - 1)
if numerator3 <= 0:
k3_min = 0
else:
k3_min = (numerator3 + d - 1) // d
k3_max = H3 // d
if k3_min > k3_max:
continue
# Now find the minimal k1 + k3 where Y != Z
best = INF
# Check possible k1 and k3 within their ranges
# Try minimal k1 and k3 first
k1_start = k1_min
k3_start = k3_min
Y = H1 - k1_start * d
Z = H3 - k3_start * d
if Y != Z:
best = k1_start + k3_start
else:
# Need to find next possible
# Try incrementing k1 or k3
if k1_start + 1 <= k1_max:
new_Y = H1 - (k1_start + 1) * d
if new_Y != Z:
best = min(best, (k1_start + 1) + k3_start)
if k3_start + 1 <= k3_max:
new_Z = H3 - (k3_start + 1) * d
if new_Z != Y:
best = min(best, k1_start + (k3_start + 1))
if k1_start + 1 <= k1_max and k3_start + 1 <= k3_max:
new_Y = H1 - (k1_start + 1) * d
new_Z = H3 - (k3_start + 1) * d
if new_Y != new_Z:
best = min(best, (k1_start + 1) + (k3_start + 1))
# Check further increments if necessary (up to a limit)
# Limit the search to avoid infinite loops
max_add = 5
for add in range(1, max_add + 1):
found = False
for delta_k1 in range(0, add + 1):
delta_k3 = add - delta_k1
new_k1 = k1_start + delta_k1
new_k3 = k3_start + delta_k3
if new_k1 > k1_max or new_k3 > k3_max:
continue
new_Y = H1 - new_k1 * d
new_Z = H3 - new_k3 * d
if new_Y != new_Z:
best = min(best, new_k1 + new_k3)
found = True
break
if found:
break
if best != INF:
total = best + k2
if total < min_total:
min_total = total
return min_total if min_total != INF else -1
def compute_pattern2():
min_total = INF
# Try k2 from 0 to 100
for k2 in range(0, 101):
X = H2 - k2 * d
if X < 0:
continue
# Y and Z must be > X, and Y != Z
# Compute k1 and k3
# For H1: H1 -k1*d > X → k1 < (H1 - X)/d → k1_max = floor( (H1 - X -1)/d )
# Also, H1 -k1*d >=0 → k1 <= H1//d
if H1 <= X:
continue # No way to make Y > X
k1_max = (H1 - X - 1) // d
k1_max = min(k1_max, H1 // d)
if k1_max < 0:
continue
# For H3
if H3 <= X:
continue
k3_max = (H3 - X - 1) // d
k3_max = min(k3_max, H3 // d)
if k3_max < 0:
continue
# k1 can be from 0 to k1_max, k3 from 0 to k3_max
# Find minimal k1 +k3 where Y != Z
best = INF
# Check k1=0 and k3=0 first
Y = H1 - 0 * d
Z = H3 - 0 * d
if Y != Z:
best = 0
else:
# Try incrementing one of them
if 0 <= 1 <= k3_max:
new_Z = H3 - 1 * d
if new_Z > X and new_Z != Y:
best = min(best, 1)
if 0 <= 1 <= k1_max:
new_Y = H1 - 1 * d
if new_Y > X and new_Y != Z:
best = min(best, 1)
if 0 <= 1 <= k1_max and 0 <= 1 <= k3_max:
new_Y = H1 - 1 * d
new_Z = H3 - 1 * d
if new_Y > X and new_Z > X and new_Y != new_Z:
best = min(best, 2)
# Check further increments if needed
max_add = 5
for add in range(1, max_add + 1):
found = False
for delta_k1 in range(0, add + 1):
delta_k3 = add - delta_k1
new_k1 = delta_k1
new_k3 = delta_k3
if new_k1 > k1_max or new_k3 > k3_max:
continue
new_Y_val = H1 - new_k1 * d
new_Z_val = H3 - new_k3 * d
if new_Y_val > X and new_Z_val > X and new_Y_val != new_Z_val:
best = min(best, new_k1 + new_k3)
found = True
break
if found:
break
if best != INF:
total = best + k2
if total < min_total:
min_total = total
return min_total if min_total != INF else -1
res1 = compute_pattern1()
res2 = compute_pattern2()
final_res = INF
if res1 != -1:
final_res = res1
if res2 != -1 and res2 < final_res:
final_res = res2
if final_res != INF:
print(final_res)
else:
print(-1)
if __name__ == '__main__':
main()