Bにしては難しかったので、書いておこうかなと。
問題概要
以下の料理が提供される店がある。(「調理時間」は料理を注文してから客に届くまでの時間)
- ABC 丼： 調理時間 $A$ 分
- ARC カレー： 調理時間 $B$ 分
- AGC パスタ： 調理時間 $C$ 分
- APC ラーメン： 調理時間 $D$ 分
- ATC ハンバーグ： 調理時間 $E$ 分
またこの店には以下のような注文のルールがある。
- 注文は、$10$ の倍数の時刻 (時刻 $0,10,20,30,...$) にしかできない。
- 一回の注文につき一つの料理しか注文できない。
- ある料理を注文したら、それが届くまで別の注文ができない。ただし、料理が届いたちょうどの時刻には注文ができる。
5つの料理全てを注文する時、最後の料理が届く最速の時間を求めよ。
考えたこと
入力例で実験してみればわかるが、この問題は実は1~4番目の順番は何でもよく、最後の値によって答えが決まる。時刻の和を取っていく時に、注文は $10$ の倍数の時刻に行われるので、10で割った剰余が0でなければ1の位が繰り上げられるが、最後の値だけは次の注文がないため繰り上げられずに和を取ることになるからだ。
以下の入力例1で実験する。
- ABC 丼： 調理時間 $29$ 分
- ARC カレー： 調理時間 $20$ 分
- AGC パスタ： 調理時間 $7$ 分
- APC ラーメン： 調理時間 $35$ 分
- ATC ハンバーグ： 調理時間 $120$ 分
この時答えは $ABC$ 丼 → $ARC$ カレー → $AGC$ パスタ → $ATC$ ハンバーグ → $APC$ ラーメン の順で注文して $215$ 分であるが、例えば$ABC$ 丼と$ARC$ カレーの順番が逆でも問題はない。
一方、例えば、 $ATC$ ハンバーグ と $APC$ ラーメンの順番を入れ替えると答えは$220$となる。
よって、それぞれの料理が最後になった場合を全通り出して最小値をとればよい。
計算量は $O(1)$ である。
解答
b.cs
using System;
using System.Linq;
class Program
{
static void Main(string[] args) {
int[] l = new int[5];
for (int i = 0; i < 5; i ++) {
l[i] = int.Parse(Console.ReadLine());
}
int[] t = new int[5];
for(int i = 0; i < 5; i ++) {
t[i] = l[i];
for (int j = 0; j < 5; j ++) {
if (j != i) {
if (l[j]%10 == 0) t[i] += l[j];
else t[i] += l[j] + 10 - l[j]%10;
}
}
}
Console.WriteLine(t.Min());
}
}