Atcoder ABC115 Past Exercises

Introduction

This is a study memo of the past question ABC115. The language used is Python.

A - Christmas Eve Eve Eve Difficulty : 0 I think that writing a branch with an if statement is the easiest and most stable.

d = int(input())
if d == 22:
    print('Christmas Eve Eve Eve')
if d == 23:
    print('Christmas Eve Eve')
if d == 24:
    print('Christmas Eve')
if d == 25:
    print('Christmas')

B - Christmas Eve Eve Difficulty : 24 First, find the total price without discount. From there, subtract half the price of the most expensive item to get the payment amount.

n = int(input())
p = list(int(input()) for i in range(n))
print(sum(p) - (max(p)//2))

C - Christmas Eve Difficulty : 243 In Example 1, the first, third, and fifth trees are selected as the correct answer, but it is difficult to select 1, 3, and 5 as they are. For example, if you think that these trees are arranged in ascending order such as "10, 11, 12, 14, 15", the answer trees will be serial numbers with the first, second, and third trees, making it easier to give an answer. .. So, sort $ h $ in advance. Then, use for to calculate $ h_ {max} --h_ {min} $ in order from the front to find the minimum difference.

n,k = map(int,input().split())
h = list(int(input()) for i in range(n))
h.sort()
ans = 10**16
for i in range(n-k+1):
    ans = min(ans,h[i+k-1]-h[i])
print(ans)

D - Christmas Difficulty : 1084 The multidimensional burger for this problem looks like this:

Level 0 P
Level 1 BPPPB
Level 2 BBPPPBPBPPPBB
Level 3 BBBPPPBPBPPPBBPBBPPPBPBPPPBBB
︙

This problem has a maximum level of 50, which is slightly over $ 10 ^ {15} $ from Example 3, and simply making and counting burgers will not meet the execution time limit. Therefore, it is necessary to devise and find the number of patties. First, find the thickness $ a $ per level and the total number of patties $ p $ per level. Level 0 is known as 1 from the beginning, but level 1 and above must be calculated. $ a_i $ consists of "van, $ a_ {i-1} $, patty, $ a_ {i-1} $, van", so $ a_i = a_ {i-1} \ times 2 + 3 $ Will be. $ p_i $ needs to subtract a van from the above configuration, so $ p_i = p_ {i-1} \ times 2 + 1 $.

a[i] = 2 × a[i-1] + 3 
p[i] = 2 × p[i-1] + 1

Then, let $ f (N, X) $ be the number of patties contained in the X layer from the bottom of level N. Furthermore, for level 0, we take advantage of the simple finding and assume that "for level N-1, we know $ f (N-1, Y) $ no matter what integer Y is specified." You can also ask for Level N burgers as follows:

1. X =When 1
   N =If 1 then f(N,X) = 0
   N =If 0, f(N,X) = 1
Except for level 0, the bottom of every level is a van, so there are 0 patties.

2. 1 < X ≦ 1 + a[N-1]When f(N,X) = f(N-1,X-1)
X is level N-1 thickness+If it fits in 1.
The reason for adding 1 is level N-The amount of the lower van added when constructing level N from 1.
Level N-Since we need to find the number of patties in the X layer of 1, f(N-1,X-1)call.
The reason for subtracting 1 is the same as when adding.

3. X = 2 + a[N-1]When f(N,X) = p[N-1] + 1
X is level N-If the thickness of 1 is the same as the thickness including the lower van and the middle patty that were added when configuring level N.
Level N in this case-It is the number of 1 patties plus the 1 middle patty added when configuring level N.

4. 2 + a[N-1] < X ≦ 2 + 2a[N-1]When f(N,X) = p[N-1] + 1 + f(N-1,X-2-a[N-1])
It looks like a mixture of conditions 2 and 3.
Calculate the number of sheets up to the middle patty in the same way as 3.
In addition, I want to find the number of patties from the middle to the top, so f(N-1,X-2-a[N-1])call.
The X part is just X minus the length of 3.

5. X = 3 + 2a[N-1]When f(N,X) = 2p[N-1] + 1
If X is the current level N thickness as is.
In this case, as we calculated at the beginning, 2 x p[N-1] +It can be obtained by 1.

The flow up to this point is shown in the figure. Look at the yellow B as a van and the brown P as a patty.

Write this condition as a recursive function and call $ f (N, X) $ to get the answer.

n,x = map(int,input().split())
a,p = [1],[1]
for i in range(n):
    a.append(a[i] * 2 + 3)
    p.append(p[i] * 2 + 1)

def pate(n,x):
    if x == 1:
        if n == 0:
            return 1
        else:
            return 0
    elif x <= 1 + a[n-1]:
        return pate(n-1,x-1)
    elif x == 2 + a[n-1]:
        return p[n-1] + 1
    elif x <= 2 + 2 * a[n-1]:
        return p[n-1] + 1 + pate(n-1,x-2-a[n-1])
    else:
        return 2 * p[n-1] + 1

print(pate(n,x))