B. I Hate 1111 #723 Div.2

LONGNEW·2021년 7월 5일
0

CP

목록 보기
14/155

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

input :

  • t (1≤t≤10000)
  • x (1≤x≤109)

output :

  • For each testcase, you should output a single string. If you can make x, output "YES" (without quotes). Otherwise, output "NO".
  • 각 테스트 케이스에서 문자열을 출력하면 된다. x를 만들 수 있다면 "YES"를 그렇지 않은 경우에는 "NO"를 출력하시오.

조건 :

  • You are given an integer x. Can you make x by summing up some number of 11,111,1111,11111,…? (You can use any number among them any number of times).
    x를 입력받았을 때 11, 111, 1111, 11111,...으로 이 숫자를 만들 수 있는지 답하시오.

문제가 어메이징 하다.
그냥 무지성으로 11, 111, 1111, ... , 111111111 까지 나머지를 구해서 확인하려고 했다.
그런데 이 수는 배수가 아니므로 이게 성립하지 않는다.

문제의 힌트로 문제를 다시 읽으라는 말이 있었다.
1111은 11 101의 값이다.
그렇다면 추가되는 값들은? 111
101 뭐 이렇게 볼 수 있기 때문에 집중해야 하는 부분은 11, 111 밖에 없는 것이다.

그러면 입력 받은 x가 A 11 + B 111이면 "YES"를 출력하면 되는 것인데.
이 범위를 제한 하지 못한다면 시간 초과가 발생할 것이다. A의 값을 찢든지, B의 값을 찢든지 해야 한다.

A = C 111 + D라고 한다면 0 ~ 무한 까지를 나타낼 수 있어야 한다. D의 범위는 0 ~ 110 까지로 for문을 반복해서 D 11값을 뺀 후에 이 값이 111로 나누어 떨어지는지 확인하면 된다.
B = C 11 + D라고 한다면 위와 동일한 조건을 만족해야 한다. D의 범위는 0 ~ 10까지로 for문을 통해 D 111값을 뺸 후에 이 값이 11로 나누어 떨어지는지 확인하면 된다.

숫자들의 연관성을 통해서 한 식으로 만든 후에 범위를 제한해야 하는 문제였다....

2021.07.30
숫자의 연관성을 생각해야 한다 결국 x를 만들 때는 1로만 이루어진 숫자(1을 제외한)들로 만들어야 하는데
111을 11을 통해서 만들려 하면 100 + 11 즉 10이 포함되어야 한다. 이렇게 된다면 추가적인 조건이 발생한다. 그렇기 때문에 11, 111의 경우 작은 놈들이니 건드릴 수 없지만
1111의 경우 11 100 + 11 11 만으로 만들 수 있고
11111의 경우 111
100 + 11 작은 두 놈을 통해 만들 수 있다. 그렇기 떄문에
작은 두 수를 이용해 나타내는 것이다. 그리고 이 식을 그냥 둔다면 우리는 모든 경우를 따져야 한다. 그게 싫기 때문에 동일한 수를 가진 것끼리 묶는 것이다.

# solution from meteorexx
import sys

t = int(sys.stdin.readline())
for i in range(t):
    x = int(sys.stdin.readline())
    data = [111 * j for j in range(11)]
    flag = 0

    for item in data:
        if item > x:
            break

        if x - item % 11 == 0:
            flag = 1
            print("YES")
            break

    if flag:
        continue

    print("NO")

0개의 댓글