(出題: evima)

タラバガニ（脚 \(8\) 本）が \(a\) 匹、ズワイガニ（脚 \(10\) 本）が \(b\) 匹、エビ（脚 \(26\) 本）が \(c\) 匹いるとします。すると、\(8a + 10b + 26c = N\) が成り立ちます。問題は、\(a + b\) の最小値を尋ねています。

部分点

\(N \leq 100\) のとき、\(8a \leq 8a + 10b + 26c = N \leq 100\) より \(a \leq 12\) です。同様に、\(b \leq 10, c \leq 3\) も成り立ちます。以上を満たす非負整数の組 \(a, b, c\) は \(13 \times 11 \times 4 = 572\) 通りしかなく、これらを全て試す時間は十分にあります。

満点

\(N\) が最大で \(10^{15}\) になりうる場合、上記の方針を取ると実行制限時間にとても間に合いません。しかし、タラバガニが \(26\) 匹以上いる場合、タラバガニ \(26\) 匹をエビ \(8\) 匹と交換しても脚の合計本数は変わらず、一方でカニの数は少なくなるため、タラバガニは \(25\) 匹以下であると考えても問題の答えは変わりません。同様に、ズワイガニも \(25\) 匹以下であると考えることができます。

\(a \leq 25, b \leq 25\) を満たすような非負整数の組 \(a, b\) は \(26 \times 26 = 576\) 通りしかなく、これらを全て試す時間は十分にあります。\(a, b\) を定めると \(c = (N - 8a - 10b) / 26\) と定まり、これが非負整数であればタラバガニの数が \(a\) 匹、ズワイガニの数が \(b\) 匹である可能性があります。

今回その必要はありませんが、より速く答えを求めることもできます。