Dual (Hard Version)

发表于 分类于 ，

    有 $t$（$1\le t\le 500$）组数据，对于每组数据给出一个长度为 $n$（$1\le n\le 20$）的序列 $a$（$-20\le a_i\le 20$）。

    可以进行 $k$（$0\le k\le 31$）次操作，每次操作任选一组 $i,j$（$1\le i,j\le n$），把 $a_i\leftarrow a_i+a_j$，最后使得整个序列单调不减。

    对于每组数据，第一行输出 $k$，之后 $k$ 行输出执行操作的 $i,j$。

Dual (Hard Version)

Created by LXC on Fri Apr 12 09:48:37 2024

https://codeforces.com/problemset/problem/1854/A2

ranting: 1900

tag: constructive algorithms, math

problem

有 $t$（$1\le t\le 500$）组数据，对于每组数据给出一个长度为 $n$（$1\le n\le 20$）的序列 $a$（$-20\le a_i\le 20$）。

可以进行 $k$（$0\le k\le 31$）次操作，每次操作任选一组 $i,j$（$1\le i,j\le n$），把 $a_i\leftarrow a_i+a_j$，最后使得整个序列单调不减。

对于每组数据，第一行输出 $k$，之后 $k$ 行输出执行操作的 $i,j$。

solution

对于全是正数或负数的情况，只需要n-1次操作，可以使得非降序。

存在正数或负数，我们尝试转化为全正数或负数。

找到最大值mx和最小值mn

如果$|mx| > |mn|$，我们现在考虑最糟糕的情况，有20个数，然后最后需要19次操作变为非降序。现在还剩下31-20=12次操作。也就是说，负数最多只能有12个。我们就可以每一次操作用最大的正整数加到负数上使得一个负数变非负数。如果负数超过12个，那么正数个数就不超过7个，对于任意负数其必小于等于-1，而-1只需5次倍增可以达到-32，($-1,-2,-4,-8,-16,-32$)，$|-32|>mx$。于是剩余的至少7次操作可以将至多7个正数变为非正数。

对于$|mx| \le |mn|$同理。

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126

#include <bits/stdc++.h>
// #define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define N 500005
#define MOD 998244353
using namespace std;

random_device seed;
ranlux48 engine(seed());
int random(int l, int r) {
    uniform_int_distribution<> distrib(l, r);
    return distrib(engine);
}
template<class t,class u> ostream& operator<<(ostream& os,const pair<t,u>& p) {
    return os<<'['<<p.first<<", "<<p.second<<']';
}
template<class t> ostream& operator<<(ostream& os,const vector<t>& v) {
    os<<'['; int s = 1;
    for(auto e:v) { if (s) s = 0; else os << ", "; os << e; }
    return os<<']';
}
template<class t,class u> ostream& operator<<(ostream& os,const map<t,u>& mp){
    os<<'{'; int s = 1;
    for(auto [x,y]:mp) { if (s) s = 0; else os << ", "; os<<x<<": "<<y; }
    return os<<'}';
}

void sol() {
    int n;
    cin >> n;
    vector<int> a(n);
    int neg = 0, pos = 0, mx = 0, mn = 0;
    for (auto& i:a) {
        cin >> i;
        if (i<0) neg++;
        if (i>0) pos++;
    }
    for (int i=0; i<n; i++) {
        if (a[mx] < a[i]) mx = i;
        if (a[mn] > a[i]) mn = i;
    }
    // cout << a << endl;
    // cout << a[mx] << " " << a[mn] << endl;
    vector<pair<int,int>> ans;
    if (pos == 0) {
        for (int i=n-2; i>=0; i--) {
            ans.emplace_back(i, i+1);
        }
    } else if (neg == 0) {
        for (int i=1; i<n; i++) {
            ans.emplace_back(i, i-1);
        }
    } else if (a[mx] + a[mn] < 0) { // a[mx] < |a[mn]|
        if (pos <= 12) { // opt: 12+19 = 31 
            for (int i=0; i<n; i++) {
                if (a[i] > 0) {
                    ans.emplace_back(i, mn);
                }
            }
            for (int i=n-2; i>=0; i--) {
                ans.emplace_back(i, i+1);
            }
        } else { // a[mx] = 1, 2, 4, 8, 16, 32. opt: 5 + 7 + 19 = 31
            for (int i=0; i<5; i++) {
                ans.emplace_back(mx, mx);
            }
            for (int i=0; i<n; i++) { // most opt 7
                if (a[i] < 0) { 
                    ans.emplace_back(i, mx);
                }
            }
            for (int i=1; i<n; i++) {
                ans.emplace_back(i, i-1);
            }      
        }
    } else { // a[mx] > |a[mn]|
        if (neg <= 12) { // opt: 12+19 = 31 
            for (int i=0; i<n; i++) {
                if (a[i] < 0) {
                    ans.emplace_back(i, mx);
                }
            }
            for (int i=1; i<n; i++) {
                ans.emplace_back(i, i-1);
            }   
        } else { // a[mn] = -1, -2, -4, -8, -16, -32. opt: 5 + 7 + 19 = 31
            for (int i=0; i<5; i++) {
                ans.emplace_back(mn, mn);
            }
            for (int i=0; i<n; i++) {
                if (a[i] > 0) {
                    ans.emplace_back(i, mn);
                }
            }
            for (int i=n-2; i>=0; i--) {
                ans.emplace_back(i, i+1);
            }   
        }
    }
    cout << ans.size() << "\n";
    for (auto [x,y]:ans) {
        cout << x+1 << " " << y+1 << "\n";
        a[x] += a[y];
    }
    // cout << a << endl;
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}