Review of AtCoder Beginner Contest 165, up to question E (Python)

This is a review article for beginners of competition professionals.

The solution I write here is written while looking at the commentary and other people's submissions. It may not be what you actually submitted.

A - We Love Golf

It is a question to answer whether K is included in the range of A or more and B or less.

From the constraint of $ 1 \ leq A \ leq B \ leq 1000 $, $ 1 \ leq K \ leq 1000 $, there is no problem if you simply search for a value that satisfies the condition in the range from $ A $ to $ B $. ..

N = int(input())
A, B = map(int, input().split())
for i in range(A, B+1):
  if i % N == 0:
    print('OK')
    break
else:
  print('NG')

B - 1%

When the deposited 100 yen has an annual interest rate of 1%, it is a question of how many years later it will exceed the given amount of X yen.

Amounts after the decimal point will be truncated. Answered the number of times while was turned until the specified amount was exceeded.

X = int(input())
n = 100
count = 0
while n < X:
  count += 1
  n = int(n * 1.01)
print(count)

C - Many Requirements

Get $ d $ points when $ A_b --A_a = c $ for inputs $ a, b, c, d $. When you are free to create the sequence $ \ boldsymbol {A} $, the question is to answer what the maximum total score will be.

It looks like a confusing problem ... but the sequence length $ N $, maximum $ M $ is $ 1 \ leq N \ leq 10, 1 \ leq M \ leq 10 $, given $ a, b The number of, c, d $ $ Q $ is also specified as $ 1 \ leq Q \ leq 50 $. I thought that this would be a brute force attack.

I used ʻitertools.combinations_with_replacement ()` for brute force. Note that the sequence $ A $ has a fixed sorted value, but duplicate values are possible.

import itertools

N, M, Q = map(int, input().split())
abcd = [tuple(map(int, input().split())) for _ in range(Q)]

Max = 0
for C in itertools.combinations_with_replacement(range(1, M + 1), N):
  score = sum([d for a, b, c, d in abcd if C[b-1] - C[a-1] == c])
  Max = max(Max, score)
print(Max)

Postscript

Is this really a number that can be pushed? $ O (M ^ N Q) $, right? I was worried and tried to calculate.

import itertools

print(len(list(itertools.combinations_with_replacement(range(1, 11), 10))))
# 92378

It seems that you can go. Looking at the commentary, this full search was tough on my own. Long live Python. Long live the library.

D - Floor Function

floor (Ax/B)-A\times floor (x/B)

Is the problem of finding $ x $ which is the maximum value.

Aside from the mathematical proof, I wondered if I should find the maximum value of $ x $ such that $ floor (x / B) = 0 $. The condition is met by the largest $ B-1 $ below $ N $, that is, the smaller of $ B-1 $ or $ N $.

That's why I wrote the following.

A, B, N = map(int, input().split())

x = min(B-1, N)
print(A*x // B - A * (x//B))

Mathematical explanation

I didn't understand the mathematical explanation, so I will read the explanation.

f(x) = floor (Ax/B)-A\times floor (x/B)

And put it. When the value of $ x $ is increased by $ B $ in this formula, the first term on the right side is always increased by $ A $. The second term is always reduced by $ A $. This cancels out and the total does not change. In other words, the following formula holds.

f(x) = f(x+B)

So you don't have to think about the range of $ B \ leq x $. Find the maximum value in the range of $ 0 \ leq x <B $, $ 0 \ leq x \ leq N $.

In this range, the value of the second term, which is originally negative, is always 0, so the value of the first term, which is a monotonous increase, should be maximized within the range. That is, maximize $ x $ within the range.

I don't use the second term, so you can write it as follows.

A, B, N = map(int, input().split())
print(A * min(B-1, N) // B)

E - Rotation Matching

It is a problem to think about how to take a combination in which opponents do not overlap when $ N $ participants play 1vs1 rock-paper-scissors at the same time for $ M $ games and $ N $ times.

The problem statement is extremely complicated. What are you asking?

Let's say $ N = 9 $ people participated in this tournament. There will be 9 sets of matches. From here, let's set $ M = 3 $ and make three pairs.

Choose a pair of 1 or 2 as you like.

Even if you rotate 9 times in this state, there will be no duplication of opponents.

Next, let's take 3, 5 pairs.

This will not cause duplication.

Next, let's take a pair of 6 and 7.

This will cause duplication. A pair of 1 and 2 shifts and a pair of 6 and 7 shifts take the same thing on the way.

How to fix this? It has been shifted by one or two, so let's shift it by three this time.

This time there is no duplication. The problem is to make such a pair.

In other words, this problem can be rephrased as follows.

"Output $ M $ pairs of ($ A_i, B_i $) such that $ B_i --A_i = 1, 2, 3, ..., M $, without duplication of values."

No decent search has been done to solve this. (TLE has come out.) From the beginning, the shape is decided and placed.

So I implemented it as follows.

N, M = map(int, input().split())

halfPos = -(-N//2)
qPos = halfPos // 2
q3Pos = qPos + halfPos

for m in range(1, M+1):
  if m % 2:
    print(qPos-m//2, qPos+m//2+1)
  else:
    print(q3Pos-m//2, q3Pos+m//2)

This article ends here. This is the first time I have solved it in production with ABCDE.