結果
| 問題 |
No.281 門松と魔法(1)
|
| ユーザー |
 lam6er
|
| 提出日時 | 2025-04-16 00:08:24 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 7,279 bytes |
| コンパイル時間 | 226 ms |
| コンパイル使用メモリ | 81,940 KB |
| 実行使用メモリ | 68,260 KB |
| 最終ジャッジ日時 | 2025-04-16 00:09:34 |
| 合計ジャッジ時間 | 3,661 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 44 WA * 3 RE * 10 |
ソースコード
import sys
def compute_case1(d, H1, H2, H3):
min_steps = float('inf')
max_k2 = 100
for k2 in range(0, max_k2 + 1):
h2 = H2 - k2 * d
if h2 < 0:
break
# Compute k1 for H1 < h2
if H1 >= h2:
required_h1 = h2 - 1
if required_h1 < 0:
# H1 can't be reduced to <0 and >=0, but required_h1 is -1, so H1' must be 0, which is <h2 only if h2>0
if h2 == 0:
continue # H1' is 0, which is not <0
else:
# H1 needs to be reduced to 0
k1 = (H1 + d - 1) // d # ceil division to reach <=0
h1 = 0
if h1 >= h2:
continue
else:
k1 = (H1 - required_h1 + d - 1) // d
h1 = H1 - k1 * d
if h1 < 0:
h1 = 0
if h1 >= h2:
continue
else:
k1 = 0
h1 = H1
# Compute k3 for H3 < h2
if H3 >= h2:
required_h3 = h2 - 1
if required_h3 < 0:
if h2 == 0:
continue
else:
k3 = (H3 + d - 1) // d
h3 = 0
if h3 >= h2:
continue
else:
k3 = (H3 - required_h3 + d - 1) // d
h3 = H3 - k3 * d
if h3 < 0:
h3 = 0
if h3 >= h2:
continue
else:
k3 = 0
h3 = H3
# Check conditions
if h1 < h2 and h3 < h2:
if h1 != h3:
total = k1 + k2 + k3
if total < min_steps:
min_steps = total
else:
# Try adding one step to k1
new_k1 = k1 + 1
new_h1 = max(0, H1 - new_k1 * d)
if new_h1 < h2 and new_h1 != h3:
total = new_k1 + k2 + k3
if total < min_steps:
min_steps = total
else:
# Try adding one step to k3
new_k3 = k3 + 1
new_h3 = max(0, H3 - new_k3 * d)
if new_h3 < h2 and new_h3 != h1:
total = k1 + k2 + new_k3
if total < min_steps:
min_steps = total
# Check k2_max for h2=0
k2_max = H2 // d
for k2 in [k2_max, k2_max + 1]:
h2 = H2 - k2 * d
if h2 < 0:
continue
# Compute k1 for H1 < h2
if H1 >= h2:
required_h1 = h2 - 1
if required_h1 < 0:
if h2 == 0:
continue
else:
k1 = (H1 + d - 1) // d
h1 = 0
if h1 >= h2:
continue
else:
k1 = (H1 - required_h1 + d - 1) // d
h1 = H1 - k1 * d
if h1 < 0:
h1 = 0
if h1 >= h2:
continue
else:
k1 = 0
h1 = H1
# Compute k3 for H3 < h2
if H3 >= h2:
required_h3 = h2 - 1
if required_h3 < 0:
if h2 == 0:
continue
else:
k3 = (H3 + d - 1) // d
h3 = 0
if h3 >= h2:
continue
else:
k3 = (H3 - required_h3 + d - 1) // d
h3 = H3 - k3 * d
if h3 < 0:
h3 = 0
if h3 >= h2:
continue
else:
k3 = 0
h3 = H3
# Check conditions
if h1 < h2 and h3 < h2:
if h1 != h3:
total = k1 + k2 + k3
if total < min_steps:
min_steps = total
else:
# Try adding one step to k1
new_k1 = k1 + 1
new_h1 = max(0, H1 - new_k1 * d)
if new_h1 < h2 and new_h1 != h3:
total = new_k1 + k2 + k3
if total < min_steps:
min_steps = total
else:
# Try adding one step to k3
new_k3 = k3 + 1
new_h3 = max(0, H3 - new_k3 * d)
if new_h3 < h2 and new_h3 != h1:
total = k1 + k2 + new_k3
if total < min_steps:
min_steps = total
return min_steps
def compute_case2(d, H1, H2, H3):
min_steps = float('inf')
max_k2 = 100
for k2 in range(0, max_k2 + 1):
h2 = H2 - k2 * d
if h2 < 0:
break
# H1' and H3' must be > h2
# Compute max steps allowed for H1 and H3 to be > h2
# For H1: H1 -k1*d > h2 → k1 < (H1 - h2)/d → k1_max = floor( (H1 - h2 -1)/d )
# since k1 >=0
if H1 <= h2:
continue
# k1 can be 0, as we want minimal steps
k1 = 0
h1 = H1
if H3 <= h2:
continue
k3 = 0
h3 = H3
if h1 > h2 and h3 > h2:
if h1 != h3:
total = k2
if total < min_steps:
min_steps = total
else:
# Need to apply one step to either H1 or H3
# Try H1
new_h1 = max(0, h1 - d)
if new_h1 > h2 and new_h1 != h3:
total = k2 + 1
if total < min_steps:
min_steps = total
else:
# Try H3
new_h3 = max(0, h3 - d)
if new_h3 > h2 and new_h3 != h1:
total = k2 + 1
if total < min_steps:
min_steps = total
# Check k2_max for h2=0
k2_max = H2 // d
for k2 in [k2_max, k2_max + 1]:
h2 = H2 - k2 * d
if h2 < 0:
continue
if H1 <= h2 or H3 <= h2:
continue
k1 = 0
h1 = H1
k3 = 0
h3 = H3
if h1 != h3:
total = k2
if total < min_steps:
min_steps = total
else:
new_h1 = max(0, h1 - d)
if new_h1 > h2 and new_h1 != h3:
total = k2 + 1
if total < min_steps:
min_steps = total
else:
new_h3 = max(0, h3 - d)
if new_h3 > h2 and new_h3 != h1:
total = k2 + 1
if total < min_steps:
min_steps = total
return min_steps
def main():
d = int(sys.stdin.readline())
H = [int(sys.stdin.readline()) for _ in range(3)]
H1, H2, H3 = H[0], H[1], H[2]
case1 = compute_case1(d, H1, H2, H3)
case2 = compute_case2(d, H1, H2, H3)
min_total = min(case1, case2)
if min_total == float('inf'):
print(-1)
else:
print(min_total)
if __name__ == '__main__':
main()