Official

A - Shampoo Editorial by en_translator


If you are new to learning programming and do not know where to start, please try Problem A “Welcome to AtCoder” from practice contest. There you can find a sample code for each language.
Also, if you are not familiar to problems in programming contests, we recommend you to try some problems in “AtCoder Beginners Selection” (https://atcoder.jp/contests/abs).
「競プロ典型 90 問」(Typical 90 Problems of Competitive Programming) (https://atcoder.jp/contests/typical90) is a collection of typical 90 competitive programming problems; unfortunately, currently the problem statements are all Japanese.
「C++入門 AtCoder Programming Guide for beginners (APG4b)」(https://atcoder.jp/contests/APG4b) is a C++ tutorial for competitive programmers. Sadly, this is only in Japanese too.


Solution 1

Let’s actually simulate the process. The following infinite-loop implementation is simple.

Sample code (Python)

V,A,B,C=map(int,input().split())
while True:
  if V<A:
    print("F")
    exit()
  V-=A
  if V<B:
    print("M")
    exit()
  V-=B
  if V<C:
    print("T")
    exit()
  V-=C

The computational complexity of this solution is \(O(V)\).

Solution 2

First, let’s consider the case where \(V<A+B+C\). In such case, we can find the answer by the following simple conditional branches:

if V<A:
  print("F")
elif V<A+B:
  print("M")
else:
  print("T")

While \(V\geq A+B+C\), shampoo is consumed \((A+B+C)\) a day. Thus, when the remaining amount of shampoo falls below \(A+B+C\), the amount is \(V\%(A+B+C)\). (\(x\%y\) denotes the remainder when \(x\) is divided by \(y\))
Therefore, it can be solved by the following code:

Sample code (Python)

V,A,B,C=map(int,input().split())
V%=A+B+C
if V<A:
  print("F")
elif V<A+B:
  print("M")
else:
  print("T")

The computational complexity of this algorithm is \(O(1)\) under certain assumption.

posted:
last update: