B. Scenes From a Memory | Round #741 Div.2

LONGNEW·2021년 8월 27일
0

CP

목록 보기
94/155

https://codeforces.com/contest/1562/problem/B
시간 1초, 메모리 256MB

input :

  • t (1 ≤ t ≤ 103)
  • k (1 ≤ k ≤ 50)
  • n

output :

  • For every test case, print two numbers in two lines. In the first line print the number of digits, that you have left in the number. In the second line print the digits left after all delitions.
    각 테스트 케이스에서 두 줄의 정답을 출력하시오. 첫째 줄에는 숫자의 길이를 둘때 줄에는 제거를 모두 끝마친 후 얻을 수 있는 수를 출력하시오.

조건 :

  • n에는 0이 포함되어 있지 않다.

  • n에서 수들을 최대한 많이 제거한 후에 얻은 수가 소수가 아닐 수 있는가

  • 소수가 아니라는 의미는 합성수 또는 1을 나타낸다.


가장 처음 들었던 생각은 4, 6, 8, 9, 1이 있으면 그냥 얘네를 출력하면 되겠다 였다.

일단 1이 포함된다는 것 자체를 너무 늦게 안 것도 좀 문제가 있었다.

이 5가지 조건을 만족시키는 if를 만들려고 했으니 아주 문제가 있었다.
지금와서 보니 리스트에 이 값들을 넣은 다음에 존재하는지를 확인하는 것이 매우 편하다.

1의 길이는 해결이 가능하고 그럼 2의 길이로 넘어가자.

사실 문제를 푸는 당시에는 모든 길이를 다 따져야 하나? 하는 생각에 문제를 놓고 싶었다.
지금 와서 천천히 다시 보니 따져야 하는 숫자는 매우 적다. 2, 3, 5, 7이 4개의 숫자를 이용해서 만든 수들인데 얘네가 소수이려면 자기자신이 또 나오는 일은 없어야 한다.

22, 33, 과 같은 수는 합성수이기 때문이다.

2의 길이까지는 소수가 발생할 수 있는데 3의 길이에서는 발생할 수 없다.

235, 237, 257, 325, 327, 357, 523, 527, 537, 723, 725, 735 처럼 죄다 1개를 빼버리면 합성수가 될 수 있기 때문이다.
어차피 2의 길이에서도 만들 수 없다면 3의 길이에서 새로운 2의 길이짜리 정답을 얻을 수 있다.

물론 문제를 푸는 당시에는 그냥 짜증나서 4의 길이까지 조합을 통해 문제를 해결하도록 하였다. 그리고 헛웃음이 나와서 그냥 롤이나 하고 잤다.

그러기에 그냥 2개의 숫자를 가지고 정답을 얻을 수 있다고 봐야하는 것이다.
3짜리를 만들어도 2개로 만든 정답을 얻으니까

import sys, math

def check():
    visit = set()

    for i in range(len(num)):
        now = int(num[i])

        if now in visit:
            continue

        visit.add(now)
        for j in range(2, int(math.sqrt(now)) + 1):
            if now % j == 0:
                return now

    for i in range(len(num)):
        for j in range(i + 1, len(num)):
            now = int(num[i] + num[j])

            if now in visit:
                continue

            visit.add(now)
            for k in range(2, int(math.sqrt(now)) + 1):
                if now % k == 0:
                    return now

for _ in range(int(sys.stdin.readline())):
    k = int(sys.stdin.readline())
    n = sys.stdin.readline().rstrip()
    num = []

    for item in n:
        num.append(item)

    if '1' in num:
        print(1)
        print(1)
        continue

    ans = check()
    print(len(str(ans)))
    print(ans)

0개의 댓글