読者です 読者をやめる 読者になる 読者になる

ゆらのふなびと

競プロ, Python, C++

ABC006 C - スフィンクスのなぞなぞ

競プロ

問題

C: スフィンクスのなぞなぞ - AtCoder Beginner Contest 006 | AtCoder

「この街には人間が N 人いる。人間は、大人、老人、赤ちゃんの 3 通りだ。 この街にいる人間の、足の数の合計は M 本で、大人の足は 2 本、老人の足は 3 本、赤ちゃんの足は 4 本と仮定した場合、存在する人間の組み合わせとしてあり得るものを 1 つ答えよ。」 (もし、そのような組み合わせが存在しない場合は-1 -1 -1と出力)

解法

AtCoder Beginner Contest #006 C問題 - スフィンクスのなぞなぞ - ゲームにっき(仮)別館(仮)

↑の記事を参考にした。

答えを大人a人、老人b人、赤ちゃんc人とすると、問題は以下の連立方程式で表される。

  • a + b + c = N
  • 2a + 3b + 4c = M
  • a, b, c >= 0

変数3つに対して式2つなので、どれか1つの変数を固定すれば解が定まる。ただしa,b,cは非負という制約があるので、これを満たすよう場合分けをする。

  1. M < 2*N のとき: 解なし(少なすぎる)
  2. 2N <= M <= 3N のとき: c = 0と固定できる
  3. 3N <= M <= 4N のとき: a = 0と固定できる
  4. M > 4*N のとき: 解なし(多すぎる)

2, 3のとき、固定した文字以外の2つの文字は連立方程式を解くことで得られる。

N, M = map(int, raw_input().split())
a, b, c = -1, -1, -1
if 2*N <= M <= 3*N:
    a = 3*N-M
    b = N - a
    c = 0
elif 3*N <= M <= 4*N:
    a = 0
    b = 4*N - M
    c = N - b
print a, b, c