問題概要
$3$ つの整数 $A,B,C$が与えられる。
以下の $2$ 種類の操作を好きな順で繰り返して $A,B,C$をすべて等しくするために必要な操作の最小回数を求めよ。
- $A,B,C$ のうち $2$ つを選んで、その両方を $1$ 増やす
- $A,B,C$ のうち $1$ つを選んで、その整数を $2$ 増やす
制約条件
- $0≤A,B,C≤50$
- 入力はすべて整数である
考えたこと
操作はどちらも足し算で$+1$または$+2$なので、$3$つの整数を小さい順に$A,B,C$とすると、最終的に全ての数が$C$または$C+1$となるように操作を繰り返すことになる。
足し算が何回必要かは $(C-A)/2$の商と剰余によってわかる。最小回数を求めるには$+2$の操作を優先するべきなので、まず$2$で割った商が$+2$の操作回数となり、剰余が$+1$の操作回数となる。
例えば$A=3, C=6$の時、$(C-A)/2$の商は$1$、剰余は$1$となり$+2$を1回、$+1$を1回すればよい。
これを$(C-A)/2$と$(C-B)/2$の剰余の結果ごとに場合分けして書けばよい。(剰余だと考えうる場合の数は4通りなので。)
計算量は値の大小に左右されず、$O(1)$となる。
解答
c.cs
using System;
using System.Linq;
class Program
{
static void Main(string[] args) {
int[] s = Console.ReadLine().Split().Select(int.Parse).ToArray();
Array.Sort(s);
Console.WriteLine(solve(s[0], s[1], s[2]));
}
static int solve(int a, int b, int c) { //a < b < c
int count = 0;
if ((c-b)%2 == 0 && (c-a)%2 == 0) {
count += (c-b)/2+(c-a)/2;
}
else if (((c-b)%2 == 0 && (c-a)%2 == 1) || ((c-b)%2 == 1 && (c-a)%2 == 0)) {
count += (c-b)/2 + (c-a)/2 + 2;
}
else {
count += (c-b)/2 + (c-a)/2 + 1;
}
return count;
}
}