Submission #599178

#	Time	Username	Problem	Language	Result	Execution time	Memory
599178		_martynas	ASM (LMIO18_asm)	C++11	26 / 100	25 ms	364 KiB

asm

#include <bits/stdc++.h>

using namespace std;

#define DEBUG(x) cerr << #x << " = " << x << "\n";

using ll = long long;

const int MXN = 55;

int n;
ll A[MXN];
string B[MXN];
ll X[MXN];

int main()
{
    cin >> n;
    for(int i = 0; i < n; i++) {
        cin >> A[i] >> B[i];
    }

    if(n == 1) {
        ll x = A[0];
        ll x0 = stoll(B[0]);
        stringstream sstr;
        int commands = 0;
        if(x0 != x) {
            if(x0 > x) {
                sstr << "add " << x0-x << "\n";
                commands++;
            }
            else {
                sstr << "multiply " << 0 << "\n";
                commands++;
                if(x0) {
                    sstr << "add " << x0 << "\n";
                    commands++;
                }
            }
        }
        commands++;
        sstr << "print\n";
        cout << commands << "\n";
        cout << sstr.str();
        return 0;
    }

    const int L = 17;
    string best = "";
    int best_commands = 10000;
    int cnt = 0, ccnt = 0;

    vector<int> bits;

    // b0, b1 - spliting (printing) points
    // never makes sense to multiply by 0:
    // can be changed to mupltiply by 10^x and addition then print
    for(int b = 0; b < (1<<L); b++) {
        int temp = b;
        vector<int> gaps;
        while(temp) {
            gaps.push_back(__builtin_ctz(temp));
            temp >>= __builtin_ctz(temp)+1;
        }
        if(!is_sorted(gaps.begin(), gaps.end())) continue;
        bits.push_back(b);
    }

    cerr << bits.size() << "\n";
    bits = {0};

    for(int b0 : bits) {
        for(int b1 : bits) {
            for(int k = 0; k < n; k++) {
                X[k] = A[k];
            }
            // ax+b=x0
            // ay+b=y0
            bool flag = false;
            int commands = 0;
            vector<pair<ll, ll>> C;
            int i = 0, j = 0;
            ll x = A[0], y = A[1];
            while(i < B[0].size() || j < B[1].size()) {
                ll x0 = 0, y0 = 0;
                // construct numbers until break or end
                while(i < B[0].size()) {
                    x0 *= 10;
                    x0 += B[0][i]-'0';
                    i++;
                    if(((b0 >> (i-1)) & 1)) {
                        break;
                    }
                }
                while(j < B[1].size()) {
                    y0 *= 10;
                    y0 += B[1][j]-'0';
                    j++;
                    if(((b1 >> (j-1)) & 1)) {
                        break;
                    }
                }
                // ax+b=x0
                // ay+b=y0 | (-1)
                // a(x-y)=x0-y0
                // a = x0-y0/(x-y)
                // b = x0-ax
                // (visos A[i] reiksmes skirtingos)
                if(x == y || (x0-y0)%(x-y) != 0) {
                    flag = true; break;
                }
                ll a = (x0-y0)/(x-y);
                ll b = x0-a*x;
                if(a < 0 || b < 0) {
                    flag = true; break;
                }
                if(a != 1) {
                    commands++;
                }
                if(b != 0) {
                    commands++;
                }
                commands++;
                if(1.0*a*x > 1.1e18 || 1.0*a*y > 1.1e18) {
                    flag = true; break;
                }
                x *= a; x += b;
                y *= a; y += b;
                C.push_back({a, b});
            }
            if(flag) continue;
            if(commands < best_commands) {
                for(int k = 0; k < n; k++) {
                    string s = "";
                    for(auto p : C) {
                        if(1.0*X[k]*p.first > 1.1e18) {
                            flag = true;
                            break;
                        }
                        X[k] *= p.first, X[k] += p.second;
                        s += to_string(X[k]);
                    }
                    if(B[k] != s) {
                        flag = true;
                    }
                    if(flag) break;
                }
                if(flag) continue;
                best_commands = commands;
                best = "";
                for(auto p : C) {
                    if(p.first != 1) {
                        best += "multiply " + to_string(p.first) + "\n";
                    }
                    if(p.second != 0) {
                        best += "add " + to_string(p.second) + "\n";
                    }
                    best += "print\n";
                }
            }
            // found answer
            //return 0;
        }
    }

    if(best == "") {
        cout << "-1\n";
    }
    else {
        cout << best_commands << "\n";
        cout << best;
    }

    return 0;
}
/*
2
1 2
2 3

2
11 1122
22 2244

3
12 783206442672750426
0 6326442672750426
3 241046442672750426
*/

Compilation message (stderr)

asm.cpp: In function 'int main()':
asm.cpp:85:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |             while(i < B[0].size() || j < B[1].size()) {
      |                   ~~^~~~~~~~~~~~~
asm.cpp:85:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |             while(i < B[0].size() || j < B[1].size()) {
      |                                      ~~^~~~~~~~~~~~~
asm.cpp:88:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |                 while(i < B[0].size()) {
      |                       ~~^~~~~~~~~~~~~
asm.cpp:96:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |                 while(j < B[1].size()) {
      |                       ~~^~~~~~~~~~~~~
asm.cpp:52:9: warning: unused variable 'cnt' [-Wunused-variable]
   52 |     int cnt = 0, ccnt = 0;
      |         ^~~
asm.cpp:52:18: warning: unused variable 'ccnt' [-Wunused-variable]
   52 |     int cnt = 0, ccnt = 0;
      |                  ^~~~

• Subtask 1: 9 / 9
• Subtask 2: 17 / 17
• Subtask 3: 0 / 53
• Subtask 4: 0 / 21