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.

スクリーンショット (2).png

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))

Recommended Posts

Atcoder ABC115 Past Exercises
AtCoder ABC176
AtCoder ABC177
AtCoder ABC 174 Python
AtCoder ABC187 Python
AtCoder ABC188 Python
AtCoder ABC 175 Python
AtCoder Past Question Review (12 / 6,7)
AtCoder ABC 177 Python (A ~ E)
AtCoder ABC 178 Python (A ~ E)
Atcoder ABC164 A-C in Python
AtCoder ABC 176 Python (A ~ E)
Atcoder ABC167 A-D in Python
Atcoder ABC165 A-D in Python
Atcoder ABC166 A-E in Python
AtCoder ABC 182 Python (A ~ D)
I participated in AtCoder (ABC158)
Solve AtCoder ABC 186 with Python
Atcoder ABC169 A-E in Python
AtCoder ABC177 A-D in python
AtCoder Beginners Contest Past Question Challenge 6
AtCoder Beginners Contest Past Question Challenge 4
ABC168
ABC164
AtCoder Grand Contest Past Question Challenge 2
AtCoder Beginners Contest Past Question Challenge 9
Solve Atcoder ABC169 A-D in Python
Atcoder ABC125 C --GCD on Blackboard
ABC174
AtCoder Beginners Contest Past Question Challenge 7
AtCoder Grand Contest Past Question Challenge 1
AtCoder Beginners Contest Past Question Challenge 10
Solved AtCoder ABC 114 C-755 with Python3
Template AtCoder ABC 179 Python (A ~ E)
ABC175
AtCoder Beginner Contest 066 Review past questions
ABC170
AtCoder Beginners Contest Past Question Challenge 5
I participated in AtCoder (ABC169 edition)
ABC182
ABC153
AtCoder Beginner Contest 102 Review of past questions
AtCoder Beginner Contest 072 Review of past questions
AtCoder Beginner Contest 062 Review of past questions
AtCoder Beginner Contest 113 Review of past questions
Atcoder ABC60 D --Simple Knapsack Separate Solution
AtCoder Beginner Contest 074 Review of past questions
AtCoder Beginner Contest 051 Review of past questions
AtCoder Beginner Contest 127 Review of past questions
AtCoder Beginner Contest 119 Review of past questions
AtCoder Beginner Contest 054 Review of past questions
AtCoder Beginner Contest 117 Review of past questions
AtCoder Beginner Contest 105 Review of past questions
AtCoder Beginner Contest 112 Review of past questions
AtCoder Beginner Contest 076 Review of past questions
AtCoder Beginner Contest 089 Review of past questions
Atcoder ABC099 C --Strange Bank Separate Solution
AtCoder Beginner Contest 069 Review of past questions
AtCoder Beginner Contest 079 Review of past questions
AtCoder Beginner Contest 056 Review of past questions
AtCoder Beginner Contest 087 Review of past questions