1521-B, *1300

Problem - 1521B - Codeforces

문제

• 크기가 $n(1\leq n \leq 10^{5})$인 수열 $a_{1}a_{2}...a_{n-1}a_{n}$이 주어진다
• 인접한 항이 서로소가 되게 수열의 값을 변경시켜라
  (단, $\mathrm{min(a_{i},\ a_{j})=min(x,\ y)}\ \text{and}\ i\neq j,\  a_{i},\ a_{j}\rightarrow x,\ y$)

 

$O(n)$

$(a,\ a+1)=1$임을 이용한다

준 수열의 최소값이 $m$이라고 하면 준 수열을 다음과 같이 바꾼다
$$...,m+2,\ m+1,\ m,\ m+1,\ m+2,\ ...$$

#include <bits/stdc++.h>
#define endl "\n"
#define loop(i, n) for(int i = 1; i <= n; i++)
using namespace std;
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
 
    int t;
    cin >> t;
    while(t--){
        int n;
        cin >> n;
        int tmp;
        int minval = 1e9+1;
        int min_ind = -1;
        loop(i, n){
            cin >> tmp;
            if(tmp < minval){
                minval = tmp;
                min_ind = i;
            }
        }
 
        cout << n-1 << endl;
        loop(i, n) {
            if(i == min_ind) continue;
            cout << min_ind << ' ' << i << ' ' << minval << ' ' << minval + abs(min_ind-i) << endl;
        }
 
    }
    
    return 0;
}cs