bootcampのeasy100をやった記録　21-30

[AtCoderProblemsのTrainingをPython3でやる Easy編](https://qiita.com/hortensia/items/364f33a7909c169cdd45)
↑これの21-30のやつです。

#21.[ABC149-C Next Prime](https://atcoder.jp/contests/abc149/tasks/abc149_c)
全てのi(2<=i<=$\sqrt{x}$)に対してx%iが0になったらx=x+1して、ならなかったらwhileループから抜けてxを出せば良いですね。

```python
x=int(input())
while True:
    for i in range(2,int(x**0.5)+1):
        if x%i==0:
            break
    else:
        break
    x+=1
print(x)
```

#22.[AGC027-A Candy Distribution Again]()
sum(a)==xのときはnが答えなのは自明です。
それ以外のときはaをソートして$\sum_{i=1}^ka_i≦x$を満たすkの最大値が答えです。

```python
n,x=map(int,input().split())
a=sorted([int(i)for i in input().split()])
res=0
if sum(a)==x:
    res=n
else:
    for i in range(n):
        if sum(a[:i])<=x:res=i
print(res)
```
#23.[ABC092-B Chocolate](https://atcoder.jp/contests/abc092/tasks/abc092_b)

1<=j<=D+1の範囲で$(j-1)\%A_i=0$となるjがいくつあるかを各iに対して探せば良いです。
$(i,j)$はせいぜい$(100,100)$にしかならないので二重ループでいけますね。

```python
n=int(input())
d,x=map(int,input().split())
a=[int(input())for i in range(n)]
res=x
for i in range(n):
    for j in range(d):
        if j%a[i]==0:
            res+=1
print(res)
```
と、ここまで書いてて気づいたのですが[^1]、各iに対するjの個数って(d-1)/a[i]+1じゃないですかーやだー。
解説もこっちしか書いてませんね。全探索とは……宇宙とは……。

```python
n=int(input())
d,x=map(int,input().split())
a=[int(input())for i in range(n)]
res=x+n
for i in range(n):
    res+=(d-1)//a[i]
print(res)
```

#24.[日立製作所 社会システム事業部 プログラミングコンテスト2020-B Nice Shopping](https://atcoder.jp/contests/hitachi2020/tasks/hitachi2020_b)
入力例3を見るまで割引券を使わないパターンを考えてなかったので優しいなあと思いました。
答えの初期値をmin(a)+min(b)でやった後、$a_{x_i}+b_{y_i}-C_i$と現在保持している答えを比べて、小さいほうを答えに代入していけばよいですね。

```python
A,B,M=map(int,input().split())
a=[int(i)for i in input().split()]
b=[int(i)for i in input().split()]
xyc=[[int(i)for i in input().split()]for j in range(M)]
res=min(a)+min(b)
for x,y,c in xyc:
    tmp=a[x-1]+b[y-1]-c
    res=min(res,tmp)
print(res)
```

#25.[ABC150-C Count Order](https://atcoder.jp/contests/abc150/tasks/abc150_c)
Pより小さい順列の個数を$a$、Qより小さい順列の個数を$b$としても$|a-b|$
は変わらないことに気づければ、あとは順列を生成するだけです。

```python
from itertools import permutations
n=int(input())
p=tuple(int(i)for i in input().split())
q=tuple(int(i)for i in input().split())
permutation_n=list(permutations(range(1,n+1)))
a=b=0
for i in permutation_n:
    if i<p:a+=1
    if i<q:b+=1
print(abs(a-b))
```

#26.[ABC153-D Caracal vs Monster](https://atcoder.jp/contests/abc153/tasks/abc153_d)
雑に再帰したら例3が再帰深すぎてエラーを吐いた。それはそう。

```python
def attack():
    global res
    if h[0]!=1:
        tmp=h.pop(0)
        h.append(tmp//2)
        h.append(tmp//2)
        res+=1
        return attack()
    else:
        return None
h=[int(input())]
res=0
attack()
res+=len(h)
print(res)
```

ところで、体力H(H>1)のモンスターを倒すのに必要な攻撃回数は2*(H/2のモンスターを倒すのに必要な攻撃回数)+1回です。
こっちで再帰したらいけました。

```python
def attack(x):
    if x==1:
        return 1
    else:
        return 2*attack(x//2)+1
h=int(input())
res=attack(h)
print(res)
```

#27.[ABC158-B Count Balls](https://atcoder.jp/contests/abc158/tasks/abc158_b)
「どう見ても合ってるなのになんで通らないんだ？？？？？」と思ったら掛け算の順番の問題でした。
`res=a*n//(a+b)`だとダメなんですね。言われてみればその通り。

```python
n,a,b=map(int,input().split())
res=n//(a+b)*a
if n%(a+b)>=a:
    res+=a
else:
    res+=n%(a+b)
print(res)
```

#28.[ABC081-B Shift only](https://atcoder.jp/contests/abc081/tasks/abc081_b)
リスト内に奇数が出るまで要素を割り続けるゲームですな。

```python
def notExistOdd(lst):
    for i in lst:
        if i%2==1:
            return False
    return True

n=int(input())
a=[int(i)for i in input().split()]
res=0
div=lambda x:x/2
while notExistOdd(a):
    res+=1
    a=list(map(div,a))
print(res)
```

#29.[ABC114-B 754](https://atcoder.jp/contests/abc114/tasks/abc114_b)
スライスを使うと連続部分を切り出しやすいのでオススメです。

```python
s=input()
res=[]
for i in range(len(s)-2):
    tmp=s[i:i+3]
    if len(tmp)<3:
        continue
    res.append(abs(753-int(tmp)))
print(min(res))
```

#30.[ABC108-B Ruined Square](https://atcoder.jp/contests/abc108/tasks/abc108_b)
平面図形はゲロを吐くほど苦手なので例を使ってガチャガチャやったり画面とにらめっこしてたら$x_2-x_1$と$y_2-y_1$っぽい数字が出てきたのでなんとかなった。
~~やめろ、数学の問題を出すんじゃない！~~

```python
x1,y1,x2,y2=map(int,input().split())
a=x2-x1
b=y2-y1
print(x2-b,y2+a,x1-b,y1+a)
```

#おわりに
数学の問題が出てくるとオアアーッアーッてなるのでやめて欲しいのですが、プログラミングが計算機科学である以上は無理ですね。

[^1]: 実は1問ずつ解いた直後に書いてます。