Codeforces Round #701 (Div. 2) A ~ B

codeforces.com/contest/1485

Dashboard - Codeforces Round #701 (Div. 2) - Codeforces

 

풀은 문제: 없음 ( + A, B )

못 풀은 문제: A, B, C, D, E

풀이만 보고 풀은 문제:

코드와 풀이를 보고 풀은 문제:

 

 

 

점수 수직하강할 예정

A번에서 막혔을 때 제출을 안하고 아예 참가하지 말았어야 했다

 

 

 

A. Add and Divide

a = 10**9이므로 대충 b = 10**5이상부터는 답이 1 아니면 2가 나오게 된다.

답이 1이 나오는 조건은 b > a일 때이고, 답이 2가 나오는 조건은 b**2 > a인데, 이 내용이 윗 줄을 포함하고 있으므로 그다음부터는 for문을 이용하여 구현해주면 된다.

 

주의할 점은 b = 1일 때 무조건 b = b + 1을 해주고 시작해야한다.

def main():
    for _ in range(int(input())):
        a,b = map(int,input().split())
        if a < b: print(1);continue
        if b**2 > a: print(2);continue
        ans = float('inf')
        for i in range(b,10**5):
            if i==1:continue
            z = a
            c = i-b
            while z:
                c += 1
                z //= i
            ans = min(ans,c)
            if i**2 > a:print(ans);break

 

 

 

 

 

 

B. Replace and Keep Sorted

 

이 문제의 아이디어는 a[i]는 a[i]를 제외한 a[i-1]과 a[i+1]사이의 수로 변경할 수 있다는 점이다.

그래야 조건을 만족하면서 숫자를 변경할 수 있다.

a[l]의 경우에는 1과 a[l] 사이의 숫자의 개수, a[r]의 경우에는 a[r]과 k사이의 숫자의 개수를 구하면 된다.

 

그래서 정리하면

1과 a[l] 사이의 숫자의 개수

a[l], a[l+1], a[l+2], ... , a[r] 사이의 숫자의 개수 * 2 (prefix sum 이용)

a[r]과 k 사이의 숫자의 개수

이 세가지를 더하면 답이 나온다.

 

def main():
    n,q,k = map(int,input().split())
    a = [*map(int,input().split())]
    num = [0]*n
    for i in range(1,n):
        num[i] = a[i]-a[i-1]-1
        num[i] += num[i-1]
    for i in range(q):
        l,r = map(int,input().split());l-=1;r-=1
        ans = 0
        ans += a[l]-1
        ans += (num[r]-num[l])*2
        ans += k - a[r]
        print(ans)