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

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

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.

"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 $.

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

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.