AtCoder Beginner Contest 161 C

2020年4月8日

AtCoder Beginner Contest 161 C

AtCoder Beginner Contest 161 C 問題をPython で解説していきます。
まずは問題文から。
https://atcoder.jp/contests/abc161/tasks/abc161_c

C – Replacing Integer 


実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 300 点

問題文

青木君は任意の整数 x に対し、以下の操作を行うことができます。

操作: x を x と K の差の絶対値で置き換える。

整数 N の初期値が与えられます。この整数に上記の操作を 0 回以上好きな回数行った時にとりうる N の最小値を求めてください。

制約

  • 0≤N≤10^18
  • 1≤K≤10^18
  • 入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。

N K

出力

操作を 0 回以上好きな回数行った時にとりうる N の最小値を出力せよ。

解説

x と K の差の正負によって絶対値の値は変化するので,正味の操作は以下の2通りになります。

  • x – K > 0 の時:x -> x – K
  • x – K < 0 の時:x -> -(x – K)

なので,x – K > 0 であるときは常にx から K を引き続けていき,x – K < 0 になるまでその操作が続きます。
この操作を行う回数は, N を K で割った時の商になります。よって,その操作を行う回数を l とすると,
N – l * K > 0
となるような最大の n を求めてあげると,l + 1 回目の操作では,
(N – l * K) – K < 0
になるので,この値の絶対値を取ることになります。
よって,この2つの数の大小を比較すればいいことになります。
すなわち,出力すべきは

min(N - l * K, abs((N - l * K) - K) 

になります。

解答

n, k = map(int, input().split())

l = n // k

print(min(n - l * k, abs((n - l * k) - k)))

他の問題も解説しているので,ぜひ見ていってください!
ABC 161 A
ABC 161 B
ABC 161 D
ABC 161 E
ABC 161 F