AtCoder I don't know diary_4 ABC081B, 087B, 083B (from ABS)

Introduction

[What to do next after registering with AtCoder-If you solve this much, you can fight enough! Past questions 10 questions ~](https://qiita.com/drken/items/fd4e5e3630d0f5859067#5-%E9%81%8E%E5%8E%BB%E5%95%8F%E7%B2%BE%E9 % 81% B8-10-% E5% 95% 8F) Since there was no contest for a while during the New Year holidays, I tried the problem of AtCoder Beginners Selection described in this article. I was licking the problem B, but it was very difficult. Well, I felt that I could fight if I solved this much. Also, I was writing an article thinking that something was wrong, but I fixed it because I was making typographical errors with great momentum. I won't say anything because it's so embarrassing, but if anyone has noticed it, I'm a beginner so please look at it with warm eyes. I'm sorry.

ABC081B - Shift only N positive integers A 1 </ sub>, ..., A N </ sub> are written on the blackboard. Sunuke can do the following when all the integers written on the blackboard are even numbers.

--Replace all the integers written on the blackboard with the ones divided by two.

Please ask how many times you can perform the operation at the maximum.

Thoughts

(1) I wonder if there is no choice but to divide everything ... I wonder if it will be TLE ... ② Anyway, let's arrange in ascending order to reduce the amount of calculation ③ Let's divide the list by the power of 2 without modifying it. Depending on the problem, it can be divided into commas and punctuation.

I wrote it

n = input()
a = list(map(int, input().split()))
a.sort()
i = 0
#Loop for the time being
while i <= a[0]:
  for j in a:
    #If it doesn't break, exit the inner loop
    if j % (2**(i+1)) != 0:
      print(i)
      break
  #If everything in the list is broken, next
  else:
    i += 1
    #Ignore the break of ↓!
    continue
  #Exit the outer loop after the inner loop
  break

It's just this code, but it took me a few hours to get here. It was very difficult to realize the operation of breaking both loops when the number that could not be broken came. The execution time was unexpectedly short. I didn't know that I could shift the indentation of else ... I didn't say no, so it's good. At i <= a [0], I decided to break it sometime like last time and set it to a [0], but I think there is a better way ...

Answer of a strong man (Tsuyobito)

――I don't understand the meaning at all

I'm sorry for not studying, but I didn't know the answer for the group with the shortest code at all. There are still many functions I don't know. The main point of this diary is that I want to write code that I couldn't reach at the current level, so I skipped here and searched for an answer with a structure similar to myself. I might look it up someday.

--Combine all () and for statement --Use list comprehension notation

There was such a way. I see……. I haven't used the all function so much, so I couldn't think of it at all. Besides, I knew the list comprehension, but I'm not good at it. I will review it properly. It was a very, very learning problem. There is only choice for ABS .... I also read the Linear Search Article provided by the original article.

ABC087B - Coins You have A 500-yen coins, B 100-yen coins, and C 50-yen coins. How many ways are there to choose some of these coins and make the total amount just X Yen? You cannot distinguish between coins of the same type. The two ways of choosing coins are distinguished when the number of coins selected is different for a certain type of coin.

Thoughts

① Is it too complicated to disassemble the target amount? ② Then it seems better to brute force with the coins you have

I wrote it

a = int(input())
b = int(input())
c = int(input())
x = int(input())
ans = 0
#Combination brute force
for i in range(a+1):
  for j in range(b+1): 
    for k in range(c+1):
      total = (i * 500)+(j * 100)+(k * 50)
      if total == x:
        ans += 1
        break
print(ans)


It took about an hour to write this too. Looking back, it's so easy to explain ... It's a multiple loop, but it has a simple structure. This is because I was just stupid, but I'll do my best not to be stupid from now on, so it's okay. Answer of a strong man (Tsuyobito)

It was about the same. Yay! Well, it's a simple problem.

ABC083B - Some Sums Find the sum of integers 1 to N that have a decimal sum of A to B or less. Constraint

Thoughts

① If it is up to almost 4 digits, it is not so big, so it seems that you can brute force ② I wonder if I can loop at each digit as before ③ Do not loop with unnecessary digits so as not to increase the amount of calculation I just did it! I thought that I was in good shape. I'm a little lonely later.

I wrote it

n, a, b = map(int, input().split())
ans = 0
#Do not loop in the tens to thousands depending on the value of n
ir = 1 if n < 1000 else 10
jr = 1 if n < 100 else 10
kr = 1 if n < 10 else 10
#Combination brute force
for i in range(ir):
  for j in range(jr):
    for k in range(kr):
      for l in range(10):
        #Total of digits
        s = i + j + k + l
        if s >= a and s <= b:
          #Total price
          t = 1000 * i + 100 * j + 10 * k + l 
          if t <= n:
            ans += t
print(ans)

WA. Since there were only two cases, I thought that there was an exception overlooked and confirmed it properly, but I forgot about the time of n = 10 4 </ sup>. Of course, I made a lot of other mistakes in the process, and I was wondering whether to make such a small mistake, but I will keep this as a commandment. Don't forget the exceptions you made.

I wrote _2

n, a, b = map(int, input().split())
ans = 0
ir = 1 if n < 1000 else 10
jr = 1 if n < 100 else 10
kr = 1 if n < 10 else 10
for i in range(ir):
  for j in range(jr):
    for k in range(kr):
      for l in range(10):
        s = i + j + k + l
        if s >= a and s <= b:
          t = 1000 * i + 100 * j + 10 * k + l 
          if t <= n:
            ans += t
#I'll pick up the exception
if n == 10000 and a ==1:
            ans += n            
print(ans)

When you make an exception, you may want to write the code from the exception so that you don't forget it. Answer of a strong man (Tsuyobito)

Character string i Each is made a numerical value by int and sum is taken. I see, i see……? !! I couldn't think of it at all. I used to use the map function only for input ... It's amazing that everyone has come up with it. However, there are some standards, and I wonder if everyone has learned this way. I will do my best too. When I read the explanation, it seems to be a fairly common problem. I can think of a way to add too much that I kept dividing by 10, I see, I see. You have to make these other people's ideas your own and come up with more difficult ones yourself ... I want to get used to these joseki as soon as possible. Also, it seems that a <= s <= b was good. I thought I could do it, but I didn't believe it. Believe.

I was surprised that it took an overwhelming amount of time than the B problem that I had solved several times. [^ 1] Besides, all three learned a lot. It feels like it's the problem of choice. We will also challenge the remaining ABS problems. I want to add it after reviewing it properly ....

[^ 1]: Isn't it simply because it was solved at a useless dawn? The theory emerged

Recommended Posts

AtCoder I don't know diary_4 ABC081B, 087B, 083B (from ABS)
AtCoder I don't know diary_2 ABC148E
AtCoder I don't know diary_1 ABC148D
AtCoder I don't know diary_3 ABC149C, D
I don't know the value error
[Python] Start diary from today Atcorder ABC058-B