[AtCoder explanation] Control the A, B, (C), D problems of ABC165 with Python!

A problem (11225 AC)

I think it was a little difficult.

B problem (9994 AC)

Don't forget to truncate. If you have a habit of checking with a sample, you do not have to issue WA.

C problem (2514 people AC)

It was very difficult. Speaking of just brute force, that's right ...

D problem (5554 AC) The difficulty is the opposite of the

C question. It is a problem that you can understand if you try it.

C problem is a difficult D problem level difficulty. If you just say "brute force and check all the answers", you will often see the C problem.

However, it is difficult to notice that this problem can brute force possible sequences. On top of that, you can't solve it without knowing how to make all possible sequences.

On the other hand, the D problem was the usual C problem level difficulty. In the case of such a problem set, it is necessary to have the courage to calm down and confirm the D problem, then discard the C problem and do the D problem.

ABC165A 『We Love Golf』

** Problem page **: A --We Love Golf ** Difficulty **: ★★ ☆☆☆ ** Point **: Mathematics, while handling

If you know how to make all multiples of k less than or equal to b, you can solve it.

How to solve

1. Think about what to do

Step 1: Read the question

An easy way to come up with is to enumerate all multiples of k less than or equal to b and make " OK " if there is at least one that is greater than or equal to a. Now you can start writing code.

However, it is easier to find the maximum multiple of k below b and if it is greater than or equal to a, the method of " OK " "written in the official commentary PDF, so if you can think of it, write it here. Is good. I couldn't think of it.

code

I will write two methods.

k = int(input())
a, b = list(map(int, input().split()))

x = 0

#I feel like I can write it a little more beautifully, but for the time being, an infinite loop+at break
while True:
    x += k
    if a <= x <= b:
        print("OK")
        break

    if x > b:
        print("NG")
        break

k = int(input())
a, b = list(map(int, input().split()))

#Find "a multiple of the maximum k less than or equal to b"
largest = (b // k) * k

if a <= largest:
    print("OK")
else:
    print("NG")

ABC165B『1%』

** Problem page **: B-1% ** Difficulty **: ★★ ☆☆☆ ** Point **: Handling while, reading the problem statement accurately

Just do as it is written, but the important thing is written in parentheses, ** "Truncate the money after the decimal point every year" **.

In the case of C ++ etc., you need to be careful about overflow, but in Python you do not have to worry about it. It's Python, isn't it?

How to solve

1. Think about what to do

Step 1: Think about what to do

I have 100 yen at first, and it increases by compound interest by 1% a year. If you follow this street, you can solve it.

If you read the question sentence carefully, you will find that it is very important in parentheses (compound interest, ** truncated after the decimal point **).

Therefore, let's truncate after the decimal point.

code

Once you have read the question, all you have to do is write it.

Even if you miss the decimal point truncation, if you check it with a sample, the answer will be different, so you will notice something is wrong. I noticed.

Specifically, the answer for sample 2 is 3760 and the output is 3703, and sample 3 is 1706 and 1649.

Sample 2 is the largest constraint of $ 10 ^ {18} $, so I'm confident that if this passes, you won't have to worry about errors.

x = int(input())

year = 0 #answer
money = 100 #Initial value of 100 yen

#Turn the loop until it is over x yen
while money < x:
    money *= 1.01
    money = int(money)
    year += 1

print(year)

ABC165C『Many Requirements』

** Problem page **: C --Many Requirements ** Difficulty **: ★★★★★★★★★★ (Difficult D problem level!) ** Type **: Brute force idea, depth-first search (other methods available), past exercises

First of all, it is difficult to read the problem statement and understand the meaning. Even if you understand the meaning, you need to think of making all the sequences and checking them. And even if you know that you are brute force, you can't solve it without knowing how to make a sequence.

To be honest, it's the difficulty of the difficult D problem.

things to do

1. (Because it seems to be dangerous, check if the D problem is easy)
2. Decipher the problem statement
3. Think about the solution
4. Think about implementation

Step 1 (Because it seems to be dangerous, check if the D problem is easy)

What? You might think, but this is important. AtAtCoder, it's quite common for the difficulty of the problem to be reversed. If the problem at the back seems to be solvable, it is better to do it in terms of points.

This time, there were 2500 AC people in C and 5000 AC people in D, which was more than double the difference. It's rare that there is such a difference in difficulty, but it is often the case that there is a slight difference in difficulty.

If you concentrate on the problem, you will not come up with the idea of solving the problem behind it, so it is important to calm down and move away from the problem.

After the contest was over, I often felt frustrated, "I could have solved this problem!", So if I don't understand a little, I try to check the problem behind.

This time, I thought about C for 5 minutes and felt like it was too bad, so I solved D in 10 minutes, then returned to C and solved it in 15 minutes.

Step 2-Separate article

Since it became long, I divided it into another article. I will explain in three ways.

--Use itertools.combinations_with_replacement (easiest) --Create with queue recursion (highly versatile method) --Depth-first search (commentary PDF method)

[AtCoder commentary] Win the ABC165 C problem "Many Requirements" with Python!

Similar

Here are some similar issues. The last two are a little more difficult D question level difficulty, but still easier than this question.

Tea level: ABC029 C --Brute-force Attack Green level: ABC161 D --Lunlun Number Green Level: Panasonic Programming Contest 2020 D --String Equivalence

ABC165D『Floor Function』 ** Problem page **: D --Floor Function ** Difficulty **: ★★★ ☆☆ ** Type **: Mathematics

If you are good at math, you can intuitively understand the answer. For those of us who are not good at math, we can find out by trying various things.

things to do

1. Try it for the time being

Step 1: Try it for the time being

For such problems, it is a good idea to substitute numbers for the time being.

I'm happy that $ floor (Ax / B) $ is big, and $ A \ times {floor (x / B)} $ is small.

You can see that the latter grows when $ x $ is exactly a multiple of $ B $. So, after trying various things, you can see that $ f (x + B) = f (x) $.

Therefore, $ x $ only needs to be considered in the range of $ 0 to (B-1) $. At this time, the subtraction $ A \ times {floor (x / B)} = 0 $, so you can forget about the existence.

Now, $ floor (Ax / B) $ gets bigger as $ x $ gets bigger, so $ x $ should be $ B-1 $. However, there is a condition that $ x $ is less than $ N $, so the smaller of $ N $ and $ B-1 $ is the answer.

code

If you understand it, it's just a matter of writing.

    a, b, n = list(map(int, input().split()))
    x = min(b - 1, n) # b-1 is good, but sometimes the upper limit n does not allow it.
    ans = int(a * x / b) #Calculate. The latter term is 0, so you don't have to write it.
    print(ans)