Codeforces 1216 #Codeforces

1216C.py

class Rect:

    def __init__(self, a, b, c, d):
        self.x1, self.y1 = a, b
        self.x2, self.y2 = c, d

    def get_intersect(self, tar_rect):
        nw_rect = Rect(0, 0, 0, 0)
        nw_rect.x1 = max(self.x1, tar_rect.x1)
        nw_rect.y1 = max(self.y1, tar_rect.y1)
        nw_rect.x2 = min(self.x2, tar_rect.x2)
        nw_rect.y2 = min(self.y2, tar_rect.y2)
        if nw_rect.x1 > nw_rect.x2 or nw_rect.y1 > nw_rect.y2:
            nw_rect = Rect(0, 0, 0, 0)
        return nw_rect

    def get_area(self):
        r, c = self.y2 - self.y1, self.x2 - self.x1
        return r * c

rects = []
for i in range(3):
    rc = Rect(*list(map(int, input().split())))
    rects.append(rc)

r1 = rects[0].get_intersect(rects[1])
r2 = rects[0].get_intersect(rects[2])
r3 = r1.get_intersect(r2)
tar_a = rects[0].get_area()

if r1.get_area() + r2.get_area() - r3.get_area() < tar_a:
    print('YES')
else:
    print('NO')
'''
50 100 100000 99000
13 4654 999999 1000000
0 0 1000000 45654
'''

1216E2.py

def calc(k):
    num, ret, pre = len(str(k)), 0, 0
    for i in range(1, num):
        cnt = pow(10, i - 1) * 9
        ret += pre * cnt + i * (1 + cnt) * cnt // 2
        pre += i * cnt
    extra = k - pow(10, num - 1) + 1
    ret += pre * extra
    ret += num * (1 + extra) * extra // 2
    return int(ret)


def ds(k):
    num, _sum = 1, 0
    while _sum + num * pow(10, num - 1) * 9 < k:
        _sum += num * pow(10, num - 1) * 9
        num += 1
    k -= _sum
    val = pow(10, num - 1) + k // num
    if k % num is 0:
        return (val - 1) % 10
    k = num - (k % num)
    for i in range(k):
        val = val // 10
    return val % 10


def solve(k):
    l, r, ans = 0, 1e9 + 7, 0
    while l <= r:
        mid = int((l + r) // 2)
        if calc(mid) >= k:
            ans, r = mid, mid - 1
        else:
            l = mid + 1
    # print('[log] ans = %d len = %d' % (ans, calc(ans)))
    k = k - calc(ans - 1)
    return ds(k)

q = int(input())

for i in range(q):
    k = int(input())
    print(solve(k))

1216F.py

n, k = map(int, input().split())
mask = list(map(int, input()))

dp = [0] * (n + 2)
nxt = [1 << 31] * (n + 2)

for i in range(n, 0, -1):
    nxt[i] = i if mask[i - 1] is 1 else nxt[i + 1]

for i in range(1, n + 1):
    dp[i] = dp[i - 1] + i
    idx = nxt[max(1, i - k)]
    if idx <= i + k:
        dp[i] = min(dp[i], dp[max(0, idx - k - 1)] + idx)

print(dp[n])