A. Omkar and Bad Story #724 Div.2

5900 단어 2021.07.042021.07.04

https://codeforces.com/contest/1536/problem/A
시간 2초, 메모리 256MB

input :

  • t (1≤t≤50)
  • n (2≤n≤100)
  • a1,a2,⋯,an (−100≤ai≤100)

output :

  • For each test case, output one line containing YES if Omkar can create a nice array b by adding elements to a and NO otherwise.

  • 각 테스트 케이스에서 Omkar가 좋은 배열 ba를 추가 해서 만들 수 있다면 YES를 그렇지 않다면 NO를 출력하시오.

  • If the first line is YES, output a second line containing a single integer k (n≤k≤300).

  • 만약 YES를 출력한다면 한 자리의 정수 k를 출력하시오.

  • Then output one line containing k distinct integers b1,b2,⋯,bk (−10^9 ≤ bi ≤ 10^9), the elements of the nice array b. b1,b2,⋯,bk can be in any order.

  • 그 다음 줄에는 k개의 동일하지 않은 정수를 출력하시오.(b 배열의 원소들)

조건 :

  • An array b=[b1,b2,…,bk] is called nice if for any two distinct elements bi,bj of b, |bi−bj| appears in b at least once

  • 좋은 배열이려면 배열의 원소들의 차의 절대값이 배열의 원소이어야 한다.

  • In addition, all elements in b must be distinct.

  • 추가로, b를 구성하는 원소들은 모두 구별이 가능해야 한다.(동일한 원소 포함 X)


처음 문제를 봤을 땐 무슨 말인가 싶었다.
문제가 원하는 것은 배열을 이루는 원소들의 차의 절댓값을 원소로 가져야 하는 것이다.

예를 들어
3
2 5 10
이란 입력이 있다고 하자.

|2 - 5|, |2 - 10|, |5 - 10|의 값들이 추가로 필요하다.
2 3 5 8 10
|2 - 3|, |2 - 8|, |3 - 10|의 값들이 추가로 필요하다.
1 2 3 5 6 7 8 10
|1 - 5|, |1 - 10|의 값들이 추가로 필요하다.
1 2 3 4 5 6 7 8 9 10

결국에 얻는 값은 1 ~ (입력된 마지막 값) 이다. 그렇기 때문에 그냥 마지막 값까지 전체를 출력해버리면 된다.

추가적으로 문제의 조건에서 배열을 이루는 원소들은 동일하지 않고 배열의 값은 -100 ~ 100 까지이다.

음수

만약 음수가 존재한다면?
이 배열은 좋은 배열이 될 수 없다.
추가되는 값들과 원래 존재하던 음수 와의 차를 구한다면 계속해서 더 큰 양수가 필요하다. 음수와 음수의 절대값을 구해도 양수가 추가 되어야 하고 이 양수와 음수의 차를 구하면 또 더 큰 양수가 필요하다. 이의 반복이기에 입력 받은 배열에 음수가 존재한다면 'NO'를 출력하면 된다.

0

입력된 배열에 0이 존재한다면?
음수가 없다면 좋은배열이 될 가능성이 있다.
그래서 정답을 출력할 때 0 ~ 100 까지를 출력해 주어야 한다.

물론 0 ~ 100 까지를 출력하지 않아도 되는 경우가 있다. 예제와 같은 경우인데 결국 저 예제도 0 ~ 100 에 포함이 된다.

# from r-tron18's solution
import sys

t = int(sys.stdin.readline())
for i in range(t):
    n = int(sys.stdin.readline())
    data = list(map(int, sys.stdin.readline().split()))
    data.sort()

    if data[0] < 0:
        print("no")
        continue

    print("yes")
    print("101")
    for j in range(0, 101):
        print(j, end=" ")
    print()

좋은 웹페이지 즐겨찾기