/** ____ ____ ____ ____ ____ ____ ||l |||e |||i |||n |||a |||d || ||__|||__|||__|||__|||__|||__|| |/__\|/__\|/__\|/__\|/__\|/__\| **/ #include #define endl '\n' using namespace std; typedef long long ll; const int rep = 9; /** A - price for cyclic shift to the left B - price for cyclic shift to the right M - price for printing D - price for changing active row H - price for using push and pop */ void speed() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); } struct Instruction { string type; int val; void print() { cout << type; if (val != -1) cout << " " << val; cout << endl; } }; int n, A, B, M, D, H, priceK[28]; string text; double func(double x) { double ans = 0.0; for (double div = 1; div <= x; div ++) ans = ans + x / div; return ans; } struct Solution { int k; vector < vector < char > > row; vector < Instruction > query; double cost = 0, to = 0; void calculateCost() { cost = priceK[k]; int cnt = 0; for (int i = 0; i < query.size(); i ++) { Instruction curr = query[i]; if (curr.type == "cl") cost = cost + (double)(A); else if (curr.type == "cr") cost = cost + (double)(B); else if (curr.type == "w") cost = cost + func((double)(curr.val)); else if (curr.type == "cd") cost = cost + (double)(D); else cost = cost + (double)(H); } } void recalc() { while(to < query.size()) { Instruction curr = query[to]; if (curr.type == "cl") cost = cost + (double)(A); else if (curr.type == "cr") cost = cost + (double)(B); else if (curr.type == "w") cost = cost + func((double)(curr.val)); else if (curr.type == "cd") cost = cost + (double)(D); else cost = cost + (double)(H); to ++; } } bool operator < (const Solution &S) const { return cost < S.cost; } void print() { cout << k << endl; for (int i = 1; i <= k; i ++, cout << endl) for (int j = 0; j < row[i].size(); j ++) cout << row[i][j]; cout << query.size() << endl; for (int i = 0; i < query.size(); i ++) query[i].print(); } }; Solution mostFrequent() { map < char, int > freq; set < char > myset; char cp; int max_freq = 0; for (int i = 0; i < text.size(); i ++) { myset.insert(text[i]); freq[text[i]] ++; if (freq[text[i]] > max_freq) { max_freq = freq[text[i]]; cp = text[i]; } } map < char, int > rev; bool tf = false; if (2 * H < D + M / 2) tf = true; int best = myset.size(); for (int i = myset.size() + 1; i <= 27; i ++) if (priceK[i] < priceK[best]) best = i; for (int i = 0; i < 26 && myset.size() < best; i ++) { if (myset.find((char)(i + 'a')) == myset.end()) { myset.insert((char)(i + 'a')); } } if (myset.size() < best) { myset.insert('_'); } Solution Sol; Sol.k = best; Sol.row.resize(best + 1); int idx = 0; for (auto it : myset) { rev[it] = ++ idx; Sol.row[idx].push_back(it); } int active = 1; vector < Instruction > ans; if (tf) { char c = cp; if (active != rev[c]) { ans.push_back({"cd", rev[c]}); active = rev[c]; } ans.push_back({"push", -1}); } int i = 0; while(i < text.size()) { char c = text[i]; if (c != cp || !tf) { if (active != rev[c]) { ans.push_back({"cd", rev[c]}); active = rev[c]; } int j = i; while(j < text.size() && text[j] == text[i]) j ++; ans.push_back({"w", j - i}); i = j; } else { if (i == text.size() - 1 || text[i + 1] == cp) { int j = i; while(j < text.size() && text[j] == text[i]) j ++; if (func(j - i) + D < M * (j - i) + min(A, B)) { if (active != rev[cp]) { ans.push_back({"cd", rev[cp]}); active = rev[cp]; } ans.push_back({"pop", -1}); ans.push_back({"w", j - i}); ans.push_back({"push", -1}); i = j; } else { ans.push_back({"pop", -1}); ans.push_back({"w", 1}); if (rev[cp] != active) { if (A < B) ans.push_back({"cl", -1}); else ans.push_back({"cr", -1}); } ans.push_back({"push", -1}); i ++; } } else { char nxt = text[i + 1]; if (active != rev[nxt]) { ans.push_back({"cd", rev[nxt]}); active = rev[nxt]; } ans.push_back({"pop", -1}); ans.push_back({"w", 2}); ans.push_back({"push", -1}); i += 2; } } } Sol.query = ans; Sol.calculateCost(); return Sol; } Solution best; set < char > st; Solution randomSolution(int numRow) /// make useless letters on separate lines { Solution sol; sol.k = numRow; sol.row.resize(30); string p = ""; map < char, int > mp; for (auto it : st) p = p + it, mp[it] = 1; vector < vector < char > > d, help; d.resize(30); if (p.size() >= numRow) { int sz = p.size(); for (int i = 0; i < sz; i ++) { int j = rand() % sz; swap(p[i], p[j]); } for (int i = 0; i < numRow; i ++) { sol.row[i + 1].push_back(p[i]); d[i + 1].push_back(p[i]); } for (int i = numRow; i < sz; i ++) { int idx = rand() % numRow + 1; sol.row[idx].push_back(p[i]); d[idx].push_back(p[i]); } } else { for (int i = 0; i < 26 && p.size() < numRow; i ++) { char c = (i + 'a'); if (mp[c] == 0) { mp[c] = 1; p = p + c; } } if (p.size() < numRow) p = p + "_"; int sz = p.size(); for (int i = 0; i < sz; i ++) { sol.row[i + 1].push_back(p[i]); d[i + 1].push_back(p[i]); } } sol.k = numRow; bool in_stack[256]; memset(in_stack, false, sizeof(in_stack)); stack < char > ch; int i = 0, active = 1; while(i < n) { vector < char > h; while(in_stack[text[i]]) { char c = ch.top(); ch.pop(); in_stack[c] = false; sol.query.push_back({"pop", -1}); h.push_back(c); } reverse(h.begin(), h.end()); for (int j = 0; j < d[active].size(); j ++) h.push_back(d[active][j]); d[active] = h; int nec = 1; bool done = false; while(!done) { for (int j = 0; j < d[nec].size(); j ++) if (d[nec][j] == text[i]) { done = true; break; } nec ++; } nec --; if (nec != active) { sol.query.push_back({"cd", nec}); active = nec; } int idx = 0; while(d[active][idx] != text[i]) idx ++; if (2 * H > A) { if (idx * A < (d[active].size() - idx) * B) { for (int j = 0; j < idx; j ++) sol.query.push_back({"cl", -1}); } else { for (int j = idx; j < d[active].size(); j ++) sol.query.push_back({"cr", -1}); } vector < char > k; for (int j = idx; j < d[active].size(); j ++) k.push_back(d[active][j]); for (int j = 0; j < idx; j ++) k.push_back(d[active][j]); /*for (int i = 0; i < d[active].size(); i ++) cout << d[active][i] << " "; cout << endl;*/ d[active] = k; int j = i; while(j < n && text[j] == d[active][(j - i) % d[active].size()]) j ++; k.clear(); int len = (j - i) % d[active].size(); sol.query.push_back({"w", j - i}); for (int pt = len; pt < d[active].size(); pt ++) k.push_back(d[active][pt]); for (int pt = 0; pt < len; pt ++) k.push_back(d[active][pt]); d[active] = k; i = j; } else { for (int j = 0; j < idx; j ++) { sol.query.push_back({"push", -1}); ch.push(d[active][j]); in_stack[d[active][j]] = true; } vector < char > k, bk; for (int j = idx; j < d[active].size(); j ++) k.push_back(d[active][j]); d[active] = k; int j = i; while(j < n && text[j] == d[active][(j - i) % d[active].size()]) j ++; k.clear(); int len = (j - i) % d[active].size(); sol.query.push_back({"w", j - i}); for (int pt = len; pt < d[active].size(); pt ++) k.push_back(d[active][pt]); for (int pt = 0; pt < len; pt ++) k.push_back(d[active][pt]); d[active] = k; i = j; } sol.recalc(); if (best.cost < sol.cost && best.cost != 0) return sol; /** for (int i = 0; i < d[active].size(); i ++) cout << d[active][i] << " "; cout << endl; cout << i << endl;*/ } return sol; } void solve() { cin >> n >> text >> A >> B >> M >> D >> H; n = text.size(); for (int i = 1; i <= 27; i ++) cin >> priceK[i]; for (int i = 0; i < n; i ++) st.insert(text[i]); best = randomSolution(2); best.calculateCost(); for (int i = 1; i <= 27; i ++) { for (int j = 1; j <= rep; j ++) { Solution curr = randomSolution(i); curr.calculateCost(); if (curr < best) best = curr; } } Solution also = mostFrequent(); if (also < best) best = also; best.print(); } int main() { speed(); srand(time(NULL)); freopen("printing.in", "r", stdin); freopen("printing.out", "w", stdout); solve(); return 0; } /* /* 1 wawasawasaa_aseassa 100 100 1 1 1 2 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 25 25 7 aaaadgsbsdfdsf 100 100 1 1 1 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 */