はじめに
前回
Boot campの問題を5問解きます
#44
考えたこと
iまでの非負整数の和は$\frac{1}{2}n(n+1)$となり}}ます。この和が$X$になるのは$\frac{1}{2}n(n+1)=X$のときで、$n$について解くと、$n=\frac{-1\pm{\sqrt{8X+1}}}{2}$となります。この式の解にceil記号を付けると$\lceil \frac{-1\pm{\sqrt{8X+1}}}{2} \rceil$となります。これが答えになります。
import math
x = int(input())
f = (-1+math.sqrt(8*x+1)) / 2
print(math.ceil(f))
考えたこと
操作のたびにreverseしてると死ぬので、反転しているかをboolで管理します。データの左右にしかアクセスしないのでdequeを使います。あとは、操作を実装するだけ
from collections import deque
n = int(input())
a = list(input().split())
b = deque([])
r = False
for i in range(n):
if r:
b.appendleft(a[i])
else:
b.append(a[i])
r = not r
if r:
b = reversed(b)
ans = ' '.join(b)
print(ans)
考えたこと
まずはcをsに合成せずにいくつのsccを作成できるかを考えます。cをsに合成せずに作れるsccは$min(N,M//2)$となります。
次は合成した場合を考えます。合成すると2個のcが1個のsになるので、cからsを作ろうとすると4個のcが必要になります。あとは実装するだけです。
n, m = map(int,input().split())
if m - 2 * n >= 0: #合成せずにsccが作れるかどうか
ans = n + (m-2*n)//4
print(ans)
else:
print(m//2)
考えたこと
分割する点が中心にあるなら分割方法は無数に存在します。また、分割したときの大きくない方の面積は全体の半分です。
w, h, x, y = map(int,input().split())
s = w * h / 2
if 2*x == w and 2*y == h:
print(s,1)
else:
print(s,0)
考えたこと
$A_i$の要素についてcountするとおそらくTLEするので、別の方法でカウントしていきます。sortして値の区切りでカウントしていく方法で実装します。一番長い辺が4本以上あればそれ辺で作れる正方形が最大になります。そうでなければ、二本ある一番目の辺と二本ある二番目の辺の長方形になります。
n = int(input())
a = list(map(int,input().split()))
a.sort(reverse=True)
c = 0
v = []
for i in range(n-1):
if a[i] != a[i+1]:
c += 1
if c >= 2: #辺が二本以上のときのみappend
v.append([a[i],c])
c = 0
else:
c += 1
if a.count(a[-1]) >=2:
v.append([a[-1],a.count(a[-1])])
if len(v) == 0: #vが空なら四角形は作れない
print(0)
elif v[0][1] >= 4: #正方形になる
print(v[0][0]**2)
elif len(v) >= 2: # 長方形
print(v[0][0]*v[1][0])
まとめ
これくらいなら解ける。ではまた、