[PYTHON] yukicoder contest 246 Participation record

yukicoder contest 246 Participation record

A 1040 Vertical University

Well, only 90 degrees or 270 degrees are vertical, so I just write it.

N = int(input())

t = N % 360
if t == 90 or t == 270:
    print('Yes')
else:
    print('No')

B 1041 Straight University

Since N ≤ 100, you only have to try all the combinations of the two points, so you don't have to worry about it. Of course, I forgot the equation of the straight line that passes through the two points, so I googled it. I used <0.0001 appropriately, but what should I do?

N = int(input())
XY = [list(map(int, input().split())) for _ in range(N)]

result = 0
for i in range(N):
    for j in range(i + 1, N):
        x1, y1 = XY[i]
        x2, y2 = XY[j]
        if x1 == x2:
            result = max(result, len([None for x, y in XY if x == x1]))
            continue
        t = 0
        for k in range(N):
            x, y = XY[k]
            if abs((y2 - y1) / (x2 - x1) * (x - x1) + y1 - y) < 0.0001:
                t += 1
        result = max(result, t)
print(result)

C 1042 Guchoku University

As you can see, it's a problem that can only be said to be Nibutan. For safety, if you change > 0.000001 to> 0.0000001, the accuracy will be insufficient and it will be an infinite loop or TLE. Is_ok 10 ** 35 is coming out in the middle, but it's okay that Python is easy.

from math import log2


def is_ok(N):
    return N * N <= Q * log2(N) * N + P


P, Q = map(int, input().split())

ok = 1
ng = 10 ** 18
while ng - ok > 0.000001:
    m = (ok + ng) / 2
    if is_ok(m):
        ok = m
    else:
        ng = m

print(ok)

D 1043 Series University

For dry batteries and miniature bulbs, find the number of all combinations of total voltage and total resistance by DP. Since the resistance range can be obtained from A and B for each voltage, the number of combinations of that voltage * the combination of resistors in that range The answer is the sum of the numbers of resistors. The number of combinations of resistors in that range can be obtained by * O * (1) if the cumulative sum is calculated. Below, PyPy is a code that ACs without becoming TLE.

N, M = map(int, input().split())
V = list(map(int, input().split()))
R = list(map(int, input().split()))
A, B = map(int, input().split())

vt = {}
vt[0] = 1
for v in V:
    nvt = vt.copy()
    for k in vt:
        nvt.setdefault(k + v, 0)
        nvt[k + v] += vt[k]
    vt = nvt
del vt[0]

rt = {}
rt[0] = 1
for r in R:
    nrt = rt.copy()
    for k in rt:
        nrt.setdefault(k + r, 0)
        nrt[k + r] += rt[k]
    rt = nrt
del rt[0]

ra = [0] * (100000 + 1)
for k in rt:
    ra[k] = rt[k]

for i in range(1, 100000 + 1):
    ra[i] += ra[i - 1]

result = 0
for k in vt:
    rlow = (k + B - 1) // B - 1
    rhigh = k // A
    if rlow == -1:
        result += ra[rhigh] * vt[k]
    else:
        result += (ra[rhigh] - ra[rlow]) * vt[k]
    result %= 1000000007
print(result)