Educational Codeforces Round 59 (Rated for Div. 2) A ~ D

codeforces.com/contest/1107

Dashboard - Educational Codeforces Round 59 (Rated for Div. 2) - Codeforces

 

풀은 문제: A, B, C

못 풀은 문제: D, E, F, G

풀이만 보고 풀은 문제:

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

 

 

난이도

A - 900

B - 1000

C - 1300

D - 1800

E - 2400

F - 2600

G - 2400

 

 

 

FAST IO

import os
import sys
from io import BytesIO, IOBase
from collections import defaultdict, deque, Counter, OrderedDict
import threading
from heapq import *

def main():
    return



BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

# endregion

if __name__ == "__main__":
    """sys.setrecursionlimit(400000)
    threading.stack_size(40960000)
    thread = threading.Thread(target=main)
    thread.start()"""
    main()

 

 

 

 

 

 

A. Digits Sequence Dividing

 

숫자를 두 개로 쪼개는데 뒤에 나온 숫자가 앞에 나온 숫자보다 더 클 수 있는지 확인하는 문제이다.

예외를 생각해보면 일의 자리와 십의 자리 밖에 없다.

일의 자리는 숫자 하나를 두 개로 쪼갤 수 없고, 십의 자리는 숫자가 ab(10*a + b) 일 때, 숫자가 a와 b로 나눌 수 있는데 a >= b인 경우 답이 안된다.

백의자리부터는 각 자리수의 숫자가 1이상 9이하이므로 맨 앞자리 수 하나랑 나머지 수를 출력하면 된다.

 

def main():
    for _ in range(int(input())):
        n = int(input())
        s = input()
        if n == 1 or (len(s) == 2 and int(s[0]) >= int(s[1])): print('NO');continue
        print('YES')
        print(2)
        print(s[0],s[1:]

 

 

 

B. Digital root

 

for문을 이용하여 숫자를 구해보면

루트가 1인 숫자: 1, 10, 19, 28, 37,...

루트가 2인 숫자: 2, 11, 20, 29, 38,...

....

루트가 9인 숫자: 9, 18, 27, 36, 45,....

 

보면 알다시피 전부 공차가 9인 등차수열로 이루어져 있다는 것을 알 수 있다.

 

그래서 루트가 x인 k번째 숫자는 (k-1)*9 + x라는 식을 구할 수 있다.

 

def main():
    for _ in range(int(input())):
        k,x= map(int,input().split())
        print((k-1)*9+x)

 

 

 

 

C. Brutality

 

연속되는 알파벳을 k번 이하로 눌러야 한다는 조건이 붙어져있다.

그래서 while문을 이용하여 연속인 문자들을 계속 리스트에 저장해오다가 다른 문자가 오면 그때 처리를 해주는 방식으로 O(n)으로 풀 수 있게 하였다.

점수를 최대로 먹으려면 연속된 문자의 index 번호의 리스트를 얻을 수 있는 점수를 기준으로 내림차순으로 정리해서 k개만큼 혹은 연속된 문자의 길이가 k개보다 작으면 전부 누르는 식으로 구현하였다.

 

def main():
    n, k = map(int, input().split())
    a = [*map(int, input().split())]
    s = input()
    ans = 0
    i = 1
    D = [0]
    while 1:
        if i >= n: break
        if s[D[0]] == s[i]:
            D.append(i)
        else:
            z = 0
            D.sort(key=lambda z: a[z], reverse=True)
            for j in range(len(D)):
                if z == k: break
                ans += a[D[j]]
                z += 1
            D = [i]
        i += 1
    z = 0
    D.sort(key=lambda z: a[z], reverse=True)
    for i in range(len(D)):
        if z == k: break
        ans += a[D[i]]
        z += 1
    print(ans)

 

 

 

 

 

 

D. Compression

 

n은 4의 배수이고, n by n 행렬을 압축시켜서 나타낼 수 있는지 물어보는 문제이다.

일단 행렬을 압축시키려면 같은 문자로 연속되는 행이 있어야하고, 열로 볼 때 같은 문자로 연속되는 열이 있어야한다.

 

그래서 연속되는 행의 개수와 열의 개수를 각각 리스트에 저장해둔다음 최대공약수를 구해주면 된다.

왜 최대공약수냐면 만약 아래 코드에서 ans1과 ans2의 값이 각각 4, 8일 때, col행렬의 8개의 연속되는 열을 4개, 4개로 나눠서 표현하면 되기 때문이다.

 

from math import gcd

def main():
    n = int(input())
    D = []
    for i in range(n):
        x = bin(int(input(),16))[2:]
        D.append('0'*(n-len(x))+x)

    row = []
    length = 1
    for i in range(1,n):
        if D[i-1] == D[i]: length += 1
        else:row.append(length);length = 1
    row.append(length)

    col = []
    length = 1
    for i in range(1,n):
        flag = True
        for j in range(n):
            if D[j][i-1] != D[j][i]:flag = False
        if flag: length += 1
        else: col.append(length);length = 1
    col.append(length)

    ans1 = row[0]
    for x in row:
        ans1 = gcd(ans1, x)
    ans2 = col[0]
    for y in col:
        ans2 = gcd(ans2, y)
    print(gcd(ans1,ans2))