[AtCoder explanation] Control ABC168 A, B, C problems with Python!

** AtCoder Beginners Contest 168 ** ** A, B, C problems ** will be explained as carefully as possible with ** Python 3 **.

I am aiming to explain a solution that satisfies the following three points, not just a method that can be solved.

--Simple: You don't have to think about anything extra --Easy to implement: I'm glad that mistakes and bugs are reduced --Long time: Increased performance and more time left for later problems

AtCoder Beginners Contest 168 Total number of submissions: 10866

Performance AC Score time Ranking Guideline
400 ABC--- 600 62 minutes 6607th Tea performance
600 ABC--- 600 36 minutes 5323th Tea rate at 8 times
800 ABC--- 600 16 minutes 4025th Green performance
1000 ABCD-- 1000 76 minutes 2861th 8 times green rate
1200 ABCD-- 1000 48 minutes 1950th Water performance

(Reference) Me: 1244th Performance 1418 ss_4.png I am a person who chose statistics and escaped because I do not want to do vectors with the number of centers IIB. (When is it?)

A problem (10686 people AC) "∴ (Therefore)"
If you know how to take out the 1st place, you can solve it. I use it a lot, so let's remember it in 3 seconds.
B problem (10466 AC) "... (Triple Dots)"
With Python, you just do it.
C problem (7598 people AC) ": (Colon)"
Do you remember the law of cosines? I googled.
D problem (3856 people AC) ".. (Double Dots)" [Not explained in this article] You can do breadth-first search (BFS) from
1. The answer is always YES.

Problem A "∴ (Therefore)"

** Problem page **: A-∴ (Therefore) ** Difficulty **: ★ ☆☆☆☆ ** Point **: Handling of character strings or handling of remainders

If you know the ones digit of the given number, you can solve it in different cases.

A I think it's a little troublesome for the problem. As a result, it is faster to move your hand before thinking about this.

How to solve

  1. Think about implementation

Step 1: Think about implementation

There are two patterns for finding the 1st place.

--Receive as a character string and set c = n [-1] (str type) --Receive as an integer and set c = n% 10 (int type)

After that, you can do something like ~~ if c in ["0", "1", "6", "8"]: ~~ ʻif c in "0168" `. (I changed it because it's easier to type strings than lists)

code

This is the pattern that is received as a character string. The " hon " pattern is troublesome because you have to type the most 5 characters, so it's a little easier to make it an else block.

bon, pon, hon are similar and confusing, so don't rush and check carefully before submitting so as not to generate unnecessary WA.

(However, if it is a character string, you can type " 24579 " in an instant, so it may be harder to make a mistake if you write it in the order of the problem statement) </ font>

n = input()
c = n[-1]

if c in "3":
    print("bon")
elif c in "0168":
    print("pon")
else:
    print("hon")

Here's a pattern that takes an integer and finds the ones place by the remainder after dividing by 10.

n = int(input())
c = n % 10

if c in [3]:
    print("bon")
elif c in [0, 1, 6, 8]:
    print("pon")
else:
    print("hon")

Problem B "... (Triple Dots)"

** Problem page **: B-... (Triple Dots) ** Difficulty **: ★ ☆☆☆☆ ** Point **: Handling of character strings

Python is super easy. Thanks to Python.

How to solve

  1. Think about implementation

Step 1: Think about implementation

For the time being, let's find the length of the character string. This is one shot with l = len (s).

If ʻif l <= k:, you can output it as it is, so it is print (s)`.

If not, cut out the leading $ K $ character and add '...' to the end to output. That is, print (s [: k] +'...'). s [: k] is the 0th to k-1th characters of s, so the total is k characters.

code

As a precaution, it is better to copy and paste the '...' from the question sentence.

I made a mistake and '. .. .. It cannot be said that there is a possibility of issuing WA by writing' or'...'.

    k = int(input())
    s = input()

    l = len(s)

    if l <= k:
        print(s)
    else:
        print(s[:k]+'...')

C problem ": (Colon)"

** Problem page **: C-: (Colon) ** Difficulty **: ★★★★ ☆ (There are individual differences) ** Points **: Knowledge of high school mathematics, radians and frequency methods

It's a high school math problem. Use the cosine theorem.

For these math problems, it may be useful to have a scientific calculator at hand.

Even if you don't have one, the calculator that comes with Windows has a scientific calculator mode. Or Google Search with Scientific Calculatoryou may.

Mathematical problems vary greatly from person to person. The Difficulty of AtCoder Problems was 107, but there are some people who couldn't solve it even with water or blue coder, so it's okay if you can't do it. is.

To give specific numbers, the AC / participants are water 702/742 and blue 333/350. It can be said that people in this rate band were quite special problems because almost all of them AC the usual C problem.

How to solve

  1. Think about the solution
  2. Find the angle between the needles
  3. Be careful about how to use Python's cos function (convert frequency to radians)
  4. Take the route properly

Step 1: Think about the solution

There are two ways to solve it.

--Calculate using the cosine theorem --Find the coordinates of the needle and use the three-square theorem

Most people do it with the cosine theorem, so I will explain it here. In fact, people who want to find out by coordinates should be good at mathematics, so there is no need to read this explanation.

The cosine theorem I did in high school is a formula for finding the length of the remaining one side from the two sides of a triangle and the angle between them.

c^{2} = a^{2} + b^{2} - 2abcos{θ}

Since $ a $ and $ b $ are given as the lengths of the hour and minute hands, respectively, they can be solved by knowing the angle $ θ $ between the hour and minute hands.

If you are motivated, I will draw a diagram, but since it is troublesome, [Google cosine theorem and search](https://www.google.com/search?q=%E4%BD%99%E5%BC%A6%] E5% AE% 9A% E7% 90% 86) You will get a lot of nice images.

Step 2: Find the angle between the needles

How can I find the angle between the needles?

Find the angles of the minute and hour hands, with the apex at 00:00 as 0 degrees. Then, pull the other angle from the one that is moving forward.

For example, if the hour hand is 15 degrees and the minute hand is 60 degrees, then 60-15 = 45 degrees. (Because it is an appropriate number, I don't think it will be such an angle with a real clock)

Minute hand angle

Since it is 360 degrees in 60 minutes, it advances 360 ÷ 60 = 6 degrees in 1 minute.

Hour hand angle

Since it is 360 degrees in 12 hours, it advances 360 ÷ 12 = 30 degrees in 1 hour. However, keep in mind that it advances in minutes, just as a real-life clock does.

It is easier to understand if you think that 60 minutes x 12 hours = 720 minutes is 360 degrees, and 1 minute is 360 ÷ 720 = 0.5 degrees. For example, at 9:45, 9 x 60 + 45 = 585 minutes and 585 x 0.5 = 292.5 degrees.

You don't have to fix it to an acute angle

For example, suppose the hour hand is 5 degrees and the minute hand is 350 degrees. (This angle is also appropriate)

At this time, 350-5 = 345 degrees, but I feel that there is an acute angle of 15 degrees between the needles.

However, it is okay to calculate with an obtuse angle of 345 degrees. This is because $ cos (θ) = cos (360 ° -θ) $. If you remember the unit circle, you can remember it. For details, please see the site that explains mathematics properly.

In addition, I forgot this and tried to convert, and I mistakenly issued 1WA in the conversion.

Step 3: Be careful about how to use Python's cos function (change frequency to radians)

The math module has its own function,math.cos ().

However, do not put the angle you just found into the math.cos () function. This is because the input of the math.cos () function is radians ($ \ pi = 180 ^ \ circ $).

You don't have to bother to calculate or remember the definition of radians. You can use the function math.radians () to convert frequencies to radians.

Step 4: Take the route properly

I will write it again, but the formula of the cosine theorem is

c^{2} = a^{2} + b^{2} - 2abcos{θ}

is.

You'll be asked for $ c ^ {2} $, so let's take the route and turn it into $ c $.

code

"Subtract the angle of the other needle from the angle of the one that is moving forward" is the same as taking the "absolute value of the difference", so I wrote that. (Actually, it's okay to get negative without doing this either)

import math

a, b, h, m = list(map(int, input().split()))
deg_a = (60 * h + m) * (360 / (60 * 12))
deg_b = m * (360 / 60)
deg = abs(deg_a - deg_b)
rad = math.radians(deg)

c2 = a ** 2 + b ** 2 - 2 * a * b * math.cos(rad)
print(c2 ** 0.5)

Digression: You can leave it negative

As I wrote earlier, as ʻabs (deg_a --deg_b) `, the value obtained by subtracting the angle of the non-advancing needle from the angle of the advancing needle is calculated, but it is okay to calculate with minus.

This is because of the nature of trigonometric functions. You can see it by google.

Recommended Posts

[AtCoder explanation] Control ABC180 A, B, C problems with Python!
[AtCoder explanation] Control ABC188 A, B, C problems with Python!
[AtCoder explanation] Control ABC158 A, B, C problems with Python!
[AtCoder explanation] Control ABC164 A, B, C problems with Python!
[AtCoder explanation] Control ABC168 A, B, C problems with Python!
[AtCoder explanation] Control the A, B, C problems of ABC186 with Python!
[AtCoder explanation] Control the A, B, C problems of ABC185 with Python!
[AtCoder explanation] Control the A, B, C problems of ABC187 with Python!
[AtCoder explanation] Control the A, B, C problems of ABC184 with Python!
[AtCoder explanation] Control the A, B, (C), D problems of ABC165 with Python!
[AtCoder explanation] Control the A, B, C, D problems of ABC183 with Python!
[AtCoder explanation] Control the A, B, C, D problems of ABC181 with Python!
ABC127 A, B, C Explanation (python)
ABC126 A, B, C Explanation (python)
Solve Atcoder ABC176 (A, B, C, E) in Python
Solve ABC168 A ~ C with Python
Solved AtCoder ABC 114 C-755 with Python3
Solve ABC162 A ~ C with Python
ABC128 A, B, C commentary (python)
Solve ABC158 A ~ C with Python
Solve ABC175 A, B, C in Python
[AtCoder] Solve ABC1 ~ 100 A problem with Python
Solve AtCoder ABC168 with python (A ~ D)
[AtCoder] Solve A problem of ABC101 ~ 169 with Python
AtCoder ABC 177 Python (A ~ E)
ABC163 C problem with python3
AtCoder ABC 178 Python (A ~ E)
ABC129 A, B, C commentary
AtCoder ABC 176 Python (A ~ E)
AtCoder ABC 182 Python (A ~ D)
ABC188 C problem with python3
Solve AtCoder ABC 186 with Python
ABC187 C problem with python
AtCoder Beginner Contest 174 B Problem "Distance" Explanation (C ++, Python, Java)
Solve ABC166 A ~ D with Python
ABC166 in Python A ~ C problem
Solve AtCoder Problems Recommendation with python (20200517-0523)
Solve ABC036 A ~ C in Python
Solving with Ruby and Python AtCoder ABC011 C Dynamic programming
Template AtCoder ABC 179 Python (A ~ E)
Solve ABC037 A ~ C in Python
AtCoder Beginner Contest 169 B Problem "Multiplication 2" Explanation (Python3, C ++, Java)
AtCoder Beginner Contest 170 A Problem "Five Variables" Explanation (C ++, Python, Java)
[AtCoder commentary] Win the ABC165 C problem "Many Requirements" with Python!
AtCoder Beginner Contest 169 A Explanation of Problem "Multiplication 1" (Python3, C ++, Java)
AtCoder Beginner Contest 176 A Explanation of problem "Takoyaki" (Python3, C ++, Java)
AtCoder Beginner Contest 175 B Problem "Making Triangle" Explanation (C ++, Python3, Java)
AtCoder Beginner Contest 175 A Problem "Rainy Season" Explanation (C ++, Python3, Java)
Solving with Ruby, Python and numpy AtCoder ABC054 B Matrix operation
Solving with Ruby, Perl, Java, and Python AtCoder ABC 065 C factorial
AtCoder Beginner Contest 176 B Problem "Multiple of 9" Explanation (Python3, C ++, Java)
AtCoder Beginner Contest 174 A Problem "Air Conditioner" Explanation (C ++, Python, Java)
[Python] [Explanation] AtCoder Typical DP Contest: A Contest
python> keyword arguments> hoge (** {'a': 1,'b': 2,'c': 3})
Solve ABC165 A, B, D in Python
AtCoder ABC 174 Python
AtCoder ABC187 Python
AtCoder ABC188 Python
AtCoder ABC 175 Python
Solving with Ruby and Python AtCoder ABC057 C Prime Factorization Bit Search
AtCoder Beginner Contest 173 B Problem "Judge Status Summary" Explanation (Python3, C ++, Java)