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: