https://codeforces.com/contest/1521/problem/B
시간 2초, 메모리 256MB
input :
- t (1 ≤ t ≤ 10000)
- n (1 ≤ n ≤ 105)
- a1, a2, …, an (1 ≤ ai ≤ 109)
output :
- For each of t test cases print a single integer k (0≤k≤n) — the number of operations. You don't need to minimize this number.
In each of the next k lines print 4 integers i, j, x, y (1≤i≠j≤n, 1≤x,y≤2⋅109) so that min(ai,aj)=min(x,y) — in this manner you replace ai with x and aj with y.
각 테스트 케이스에서 행동을 수행해야 하는 횟수 k를 출력하시오. 이 때, k는 최소화 되지 않아도 됩니다.
그리고 k개의 줄에 i, j, x, y를 출력하시오.
조건 :
-
She calls such an array a good that for all i (2 ≤ i ≤n) takes place gcd(ai−1, ai)=1
good인 배열의 경우 i번째에 위치한 원소의 값의 gcd를 구했을 때 1이 나오는 것을 말한다. -
You can perform the operation: select two different indices i,j (1≤i,j≤n, i≠j) and two integers x,y (1≤x,y≤2⋅109) so that min(ai,aj)=min(x,y). Then change ai to x and aj to y.
아래의 행동을 수행할 수 있다.
두 개의 인덱스 i, j를 고르고 두 수 x, y를 골라서 두 수의 최솟값이 같을 때 각 원소의 값을 x, y로 교체할 수 있다.
이 문제를 보면서 가장 삽질 했던 부분은 또 그거다. 최소화를 안 해도 되는데 최소화를 하려 한것...
최소화를 안 해도 할 수는 있다. gcd계산 한 것이 1이 안되는 것들 기리 묶어서 그냥 소수를 찾아서 넣어줘도 된다.
근데 여기서 문제는 소수를 몇 번째꺼를 쓸거냐에서 이건 아닌 것 같아 버렸다.
그러면 어떻게 해야 하나
gcd가 1이 나온다는 의미는 둘이 가진 최대 공약수가 1이라는 것이다. 최대 공약수가 되려면 소수와 다른 수를 가지고 와도 되지만 1큰 수를 가지고 와도 된다.
그러니까 그냥 가장 작은 수를 기준으로 인덱스 거리를 구해서 그 수만큼 더해 주면 되는 것이다. 그렇게 해서 내림차순, 숫자, 오름차순의 순서로 배열을 구성하자.
두 개의 gcd가 1이 되는 경우
-> 소수일 때, 1 차이 날 때.
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()))
val = min(data)
idx = data.index(val)
print(len(data) - 1)
for j in range(len(data)):
if j == idx:
continue
print(f"{idx + 1} {j + 1} {val} {val + abs(idx - j)}")
나머지 c, d는 읽어 보려 했는데 c에서 문제를 푸는 방식 자체가 이해가 안 되서 나중을 기약한다..
