A. Omkar and Bad Story #724 Div.2
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 anice
arrayb
by adding elements toa
andNO
otherwise. -
각 테스트 케이스에서 Omkar가
좋은
배열b
를a
를 추가 해서 만들 수 있다면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()
Author And Source
이 문제에 관하여(A. Omkar and Bad Story #724 Div.2), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@jsin2475/A.-Omkar-and-Bad-Story-724-Div.2저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)