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

We will explain how to solve A, B, C problems of ** AtCoder Beginners Contest 158 ** with ** Python 3 ** as carefully as possible for beginners.

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 ――It doesn't take long: The performance goes up and the time left for the D problem increases.

ABC158 data

Date: 2020-03-07 (Sat) 21:00 ~ 2020-03-07 (Sat) 22:40 (100 minutes) A Number of people submitting questions: 7053

Performance AC time Ranking Guideline
400 ABC- 63 minutes 4580th Tea performance
600 ABC- 23 minutes 3766th Brown rate at 8 times
800 ABCD 90 minutes 2911th place Green performance

(Reference) I: Performance 1144 ABCD-- 44:24 (1WA) 1644th </ font>

A problem (6954 people AC)
Reading comprehension will be tested.
B problem (5837 AC)
It's difficult. It is easy to understand if you write it on paper.
C problem (5456 people AC)
It's easy if you realize that you can search (brute force) one yen at a time from the smallest.
D problem (3533 people AC) [Not explained in this article] Simulating the
operation is too late.

ABC158A 『Station and Bus』

** Problem page **: A --Station and Bus ** Difficulty **: ★ ☆☆☆☆ ** Point **: String operation

Even if I read only the problem statement, I don't know what to do. In such a case, it is good to see a concrete example with a sample for the time being.

Problem statement

Problem statement (folding, image)
![158a.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/595910/16dcf824-5797-3686-5c66-9ed2ac66194a.png)

To put it simply

There is a three-character string $ S $ with only " A " or " B ". This is a string that represents the operating companies of the three stations in the city of AtCoder. For example, in the case of " ABA ", station 1 and station 3 are operated by company A, and station 2 is operated by company B.

The stations of different operating companies have different routes, so transportation is inconvenient. Therefore, I decided to operate a bus between the stations of company A and company B.

However, there is not always a combination of stations where buses actually operate. Specifically, if all three stations in the city are stations of the same company, there will be no set of stations operated by buses.

Determine if the bus actually runs.

How to solve

  1. Decipher the problem statement

Step 1: Decrypt the problem statement

You don't have to use your imagination to the above levels during the contest, but imagining and writing specific situations can help you understand.

If there are two types of $ S $, such as " ABA " " ABB ", " A " and " B ", then " Yes ". If $ S $ has only one character, that is, " AAA " or " BBB ", then "No".

code

Since the number of characters is fixed at 3, it is easy to type " AAA " and " BBB " directly.

Be careful not to mistake " No " and " Yes " and reverse them. If you make sure that the sample passes each time before submitting it, you will inadvertently lose the WA.

s = input()

if s == "AAA" or s == "BBB":
    print("No")
else:
    print("Yes")

If the number of characters is not fixed, for example, 1 million characters and you can not type directly, it is good to make a character string with the following code.

s = input()
n = len(s) #s length n

a_only = "A" * n #A string followed by n characters
b_only = "B" * n #A string in which B continues for n characters

if s == a_only or s == b_only:
    print("No")
else:
    print("Yes")

Or you can use len (set (s)). I won't explain it this time, but it's useful to remember.

s = input()

num = len(set(s))  #If you convert to set type, the duplication disappears, so you can see the number of types with len

if num == 1:
    print("No")
else:
    print("Yes")

ABC158B『Count Balls』

** Problem page **: B --Count Balls ** Difficulty **: ★★★★★ ** Point **: Integer (division quotient and remainder), computational complexity

It is the highest level of difficulty as a B problem.

The operation of 10 to the 100th power of the problem sentence, the maximum of the constraint is 10 to the 18th power, and an unimaginably huge number comes out. Humans cannot specifically imagine such a huge number. If you try, it will be confusing, so treat it mechanically and abstractly.

If you read the problem statement and think for a moment, you can see that the written 10 to the 100th power means "substantially infinite" and "large enough", and the number itself has no meaning.

Problem statement

Problem statement (folding, image)
![158b.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/595910/3e45f6ea-a4eb-2fe3-7c16-c1eb109dfce3.png)

To put it simply

  • $ A $ and $ B $ are difficult to understand, so change them to $ Blue $ and $ Red $.

Create an infinitely long row of balls by alternating $ Blue $ blue balls and $ Red $ red balls.

Specify $ N $ in the range of> 1 or more and 100 kyo (= 10,000 times 100 trillion) or less. How many blue balls out of $ N $ from the beginning of the row of balls?

How to solve

  1. Notice that the loop is constrained and not in time
  2. Think about how to calculate by formula

Step 1: Notice that the loop is constrained and not in time

Of course, you can get the answer by simulating the operation with a while loop. However, the problem is that $ N $ can be up to 100K. Even if you use a PC, the calculation will take years to decades without exaggeration, so you need to find it by another method.

What to do is to use "integer division" (division with the remainder that was done in the middle grade of elementary school) to calculate in one shot.

Step 2: Think about how to calculate by formula

If you think of "the operation of adding $ Blue $ blue balls and $ Red $ red balls" as one set, you can calculate by division. Let's rephrase the operation a little.

Consider the operation of adding "a cylinder containing $ Blue $ blue balls and $ Red $ red balls" to a row one by one.

However, if the number of balls in the row exceeds $ N $ if you add them in the cylinder, we will remove the balls one by one from the cylinder and add them to the row. At this time, the blue ball comes out of the cylinder first.

Forget about the color of the balls, and find the $ Q $ number of cylinders containing $ (Blue + Red) $ balls and the $ R $ number of rose balls. Once you know this, you can easily calculate the number of blue balls.

abc158bfig1.png

"Number of cylinders $ Q $" and "Number of rose balls $ R $" means "total number of balls $ N $" and "number of balls per cylinder $ (Blue + Red) $" It is calculated by dividing by.

{N} \div {(Blue + Red)} =Q too R

The "total number of blue balls" you want to find is "total number of blue balls in the cylinder" + "number of blue balls of roses", so you can calculate and add each of them.

Total number of blue balls in the tube

There are $ Blue $ blue balls in one cylinder. Therefore, there are $ Blue \ times Q $ blue balls in a $ Q $ book tube.

Number of blue balls of roses

Only one tube can be opened, so of the $ R $ rose balls, the maximum number of blue balls is $ Blue $. In other words, it is basically $ R $, but if $ R $ exceeds $ Blue $ as shown in the image below, it should be $ Blue $.

abc158bfig2.png

In other words, the smaller of $ R $ and $ Blue $, $ min (Blue, R) $.

Total number

From the above, the number of balls required is $ {N} \ div {(Blue + Red)} = Q If you say R $ too much

Blue \times Q + min(Blue, R)

Will be. Let's write this in the code.

code

n, blue, red = list(map(int, input().split()))

# n / (blue + red) = quot ... rem
quot = n // (blue + red)  #Quotient
rem = n % (blue + red)  #Remainder

ans = blue * quot + min(blue, rem)

print(ans)

For simple problems, you can name the variable a single letter "a", "b", or "x", but for complex problems it's better to have a name that tells you what the variable is.

I searched and wrote that the English word for quotient is "quotient". It's a waste of time to look up during the contest, so you can use romaji for "sho" or "amari".

ABC158C『Tax Increase』 ** Problem page **: C --Tax Increase ** Difficulty **: ★★ ☆☆☆ ** Point **: How to search all (brute force), handle loops, and truncate

It is a matter of consumption tax. I think it is easier than the B problem because it is easy to imagine concretely and it is not difficult to implement.

Problem statement

Problem statement (folding, image)
![158c.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/595910/67e2e6e7-acdb-0d4e-e17c-e0461019f687.png)

things to do

  1. Think about how to ask

Step 1: Think about how to ask

Since the upper limit of consumption tax is as small as 100 yen, it seems good to check it by full search (brute force). The specific range is that the consumption tax is 100 yen. The tax-excluded price is 1250 to 1262 yen for 8%, and 1000 to 1009 yen for 10%, so you can check 1 yen from 0 yen to 1009 yen. is.

You don't have to ask for this upper limit of 1009 yen. It is troublesome to ask for it and it causes mistakes, so it is easy and safe to check up to about 10,000 yen.

code

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

ans = -1 #If you can't find the answer-Set 1 to the initial value

#Check by increasing by 1 yen from 0 yen to 9999 yen
for price in range(10000):
    #8 consumption tax%And 10%Calculate each
    tax_a = int(price * 0.08)
    tax_b = int(price * 0.1)

    #When the condition is met, assign it to the answer and exit the loop
    if tax_a == a and tax_b == b:
        ans = price
        break

#If the answer is found, the value at that time, if not found, the initial value-1 is displayed
print(ans)

I only need to find the minimum value, so I increase it by 1 yen and when I find it, I try to get out of the loop.

This time, I used int function of built-in function for truncation processing, but from math import floor You can also write and use the math module floor function. The two behave differently for negative numbers, but they are not relevant for this issue.

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 ABC182 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!
ABC126 A, B, C Explanation (python)
Challenge AtCoder (ABC) 164 with Python! A ~ C problem
Solve Atcoder ABC176 (A, B, C, E) in Python
Solve ABC163 A ~ C with Python
Solve ABC168 A ~ C with Python
Solved AtCoder ABC 114 C-755 with Python3
Solve ABC162 A ~ C with Python
Solve ABC167 A ~ C with Python
ABC128 A, B, C commentary (python)
Solve ABC158 A ~ C with Python
[AtCoder] Solve ABC1 ~ 100 A problem with Python
Solve AtCoder ABC168 with python (A ~ D)
AtCoder ABC 177 Python (A ~ E)
Solve AtCoder ABC166 with python
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 166 A Explanation of Problem "A? C" (Python3, C ++, Java)
AtCoder Beginner Contest 174 B Problem "Distance" Explanation (C ++, Python, Java)
AtCoder Beginner Contest 177 B Problem "Substring" Explanation (Python3, C ++, Java)
Solve ABC166 A ~ D with Python
AtCoder Beginner Contest 167 A Problem "Registration" Explanation (Python3, C ++, Java)
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 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