Codeforces Global Round 6

A. Competitive Programmer standard input/output1 s, 256 MB x5632

　　　　模拟一下，需要能整除60 字符串中需要能整除2 3 10，所以需要字符串各位数之和能整除3 并且有一个偶数和一个0 或者两个0也行，特殊情况全为0 也行，

B. Dice Tower standard input/output 1 s, 256 MB

　　　　一开始想错了，打算是 n 可以由多少个21-k个数构成， WA了两发，纸上多画了几个发现应该是由 x 个骰子构成 n = x*14+y (y>=1 && y<=6) 因为骰子叠起来一定会有上下两个面被挡住而骰子是标准的 1-6 2-5 3-4 所以两个上下的骰子的点数之和为7 相当于每个骰子的贡献只有四个侧面， n 等于 x个骰子的侧面加一个最上面的面 so cout << (n%14<=6&&n%14>=1 ? "YES ":"NO ")

C. Diverse Matrix standard input/output1 s, 256 MB

　　　　开始没有头绪没有看懂题面，直接手推了几组数据找到了规律相当于输入r c，你需要输出 r 行 c列的矩阵而矩阵的每行每列的最大公约数构成一个新的数组，数组的每个元素需要是唯一的且需要minimizing the magnitude 就是说数组的最大值最小，那么最小的情况就是 1 2 3 4 5 ………… c+r，我们可以这样构造矩阵第一行为
第一行为　 2 3 …… c+r

第二行为　 2*2 3*2 …… 2*(c+r)

第三行为　 2*3 3*3 …… 3*(c+r)　　

这样就可以构造一个 1 2 3 4 ………… c+r 的数组了，然而zz的我写的时候没注意 1*r 和 r*1 的情况， Wrong answer on pretest 4， zz

D. Decreasing Debts standard input/output2 s, 256 MB

　　想了半天，但是题目给的第一个性质不会用，且不知道用容器什么储存，大概想的是用一个map数组存储 ((pair)ui,vi di) , 再将ui,vi相同的合并下 di 合并完以后跑一遍找最小的 di值，再跑一遍所有的di 都减去最小的di值，最后输出剩下 di不为 0 的个数，和具体 ui,vi di， enmmmmmmm 然后不会写。。。。。而且思路也有问题题目意思应该不是这样。。。

　　题解是不记录具体的借债关系，只记录借债人欠债金额和债主借出的具体金额 (欠钱为- 借钱为+)，每个人的金额为正或者负（）

类似于 1借给2 100元 2借给3 70元 3借给4 50元可以直接转化为 1借给2 30元 1借给3 20元 1借给4 50元，将中间的关系简化，每个人只能是欠钱或者借钱，
每次找到一个债主A 然后减去每个借钱人最多从债主A借的钱x 记录下他们的关系，债主A的钱-x 直到A没钱，到下一个债主
每个债主的钱直接借给某人输出这样的关系和金额即可，

　　Let

E. Spaceship Solitaire standard input/output1 s, 256 MB

　　　题意建造宇宙飞船需要 n 种资源，每生产一个资源需要一次，但是有里程碑相当于任务奖励当达到tj 个 sj 资源时奖励一个 uj资源，（sj, tj, uj）

　　　且当里程碑相同时只能用后者，前者奖励的资源收回

　　　忽略中间状态，直接跳到终态（所有资源已齐备所需要的生产次数），然后分析每个里程碑的贡献
　　　所以可以用个 map 存下里程碑的状态，每次查询下里程碑是否出现过，如有则将该里程碑的奖励收回且如果该里程碑如果对答案有贡献需要减去，如果uj > 0,　则判断下是否能对答案有贡献　如有则答案－－

F. Almost Same Distance standard input/output5 s, 256 MB
G. Permutation Concatenation standard input/output1 s, 256 MB
H. Red-Blue Graph standard input/output4 s, 512 MB

#include <bits/stdc++.h>

using namespace std;
#define ll long long
#define _for(i,a,b) for(int i = (a); i < (b); i++)
#define _rep(i,a,b) for(int i = (a); i <= (b); i++)

void taskA(){
    int t; 
    cin >> t;
    while(t--){
        string s; cin >> s;
        int a = 0, b = 0,d = 0;
        sort(s.begin(), s.end());
        if(s[0] == s[s.size()-1] && s[0] == '0')
        {
            cout << "red
"; continue;  
        }
        for(auto c:s) {
            int x = c-'0';
            if(x == 0) b++;
            if(x && x%2 == 0) d = 1;
            a += x;
        }
        if(a%3==0 && (b>=2 || (b&&d))){
            cout << "red
";    continue;  
        }
        cout << "cyan
";
    }
    return;
}

void taskB(){
    int t;
    cin >> t;
    while(t--){
        ll n;
        cin >> n;
        ll y = (n)%14;
        if(n < 15) cout << "NO
";
        else if(y >= 1 && y <= 6) cout << "YES
";
        else cout << "NO
";
    }
    return;
}

void taskC(){
    int c,r; cin >> r >> c;
    int x = r+c; 
    if(r == 1 && c == 1) { cout << "0
"; return;}
    ll b[505][505];
    if(r == 1) {_rep(i,1,c) cout << i+1 << (i==c?"
":" ");return; }
    if(c == 1) {_rep(i,1,r) cout << 1+i << "
";return;}
    _rep(i,1,r)
      _rep(j,1,c)
        {
            if(i==1)b[i][j] = x*i;
            else b[i][j] = b[1][j]*i;
            x--;
        }

    _rep(i,1,r) _rep(j,1,c) cout << b[i][j] << (j==c ?"
" : " ");
    
    return;
}

void taskD(){
    int n,m; cin >> n >> m;
    //map<pair<int, int>, int> cnt;
    vector<ll> a(n+1, 0);
    vector<pair<pair<int, int>, ll> >mp;

    _rep(i,1,m) {
        int x, y, z; cin >> x >> y >> z;
        a[x] += z, a[y] -= z;
    }

    int x = 1, y = 1;
    for(; x <= n; x++) {
        if(a[x] <= 0) continue;
        while(a[x]) {
            for(; y <= n && a[y] >= 0; y++);
            ll mi = min(-a[y], a[x]);
            mp.push_back(make_pair(make_pair(x, y), mi));
            a[y] += mi, a[x] -= mi;
        }
    }
    n = mp.size();
    cout << n << '
';
    for(auto it:mp) cout << it.first.first << " " << it.first.second 
                         << " " << it.second << "
";
    return;
}

void taskE(){
    int n,q; cin >> n;
    vector<int> a(n+1, 0);
    ll ans = 0;
    _rep(i,1,n) {
        cin >> a[i];
        ans+=a[i];
    }
    
    map<pair<int,int>,int> H;
    cin >> q;
    _rep(i,1,q) {
    //cout << "

 i = " << i+1 << '
';
        int x,y,z;
        cin >> x >> y >> z;
        if(H[{x,y}] > 0){
        //cout << "H " << H[{x,y}] << " a[]" << a[H[{x,y}]] << '
';
            a[H[{x,y}]]++;
            if(a[H[{x,y}]] > 0) ans++;
            H[{x,y}] = 0;
        }
    //cout << "ans = " << ans << '
';
        if(z){
            H[{x,y}] = z;
            a[z]--;
            if(a[z] >= 0)  ans--;
        }
        cout << ans << '
';
    }return;
}

int main(){
    ios::sync_with_stdio(false), cin.tie(nullptr);
    //taskA();
    //taskB();
    //taskC();
    taskD();
    return 0;
}