#include #include #include #include #include #include #include #include using namespace std; const int SYMBOLS_CNT=27, TYPES_CNT=3; const long long INF=1e18; string s; int p[SYMBOLS_CNT]; int n, a, b, m, d, h; map mp; map rmp; vector > deques; stack helpStack; int dequeIdx; string uniqueSymbols; int uniqueSymbolsCnt; vector orders; pair dequePos[SYMBOLS_CNT]; int rotations[SYMBOLS_CNT]; long long cost, minCost=INF; vector > ans; void RotateLeft(bool changeCost, bool printing) { deques[dequeIdx].push_back(deques[dequeIdx].front()); deques[dequeIdx].pop_front(); rotations[dequeIdx]=(rotations[dequeIdx]-1+deques[dequeIdx].size())%deques[dequeIdx].size(); if(changeCost) { cost+=a; } if(printing) { ans.push_back({"cl", -1}); } return; } void RotateRight(bool printing) { deques[dequeIdx].push_front(deques[dequeIdx].back()); deques[dequeIdx].pop_back(); rotations[dequeIdx]=(rotations[dequeIdx]+1+deques[dequeIdx].size())%deques[dequeIdx].size(); cost+=b; if(printing) { ans.push_back({"cr", -1}); } return; } void PrintSymbol(int cnt, bool printing) { cost+=m/cnt; RotateLeft(false, false); if(printing) { ans.push_back({"w ", 1}); } return; } void ChangeIdx(int idx, bool printing) { dequeIdx=idx; cost+=d; if(printing) { ans.push_back({"cd ", idx+1}); } return; } void PushHelpStack(bool printing, bool keepOrder) { if(keepOrder) { for(int i=0; idequePos[deques[dequeIdx].front()].second) { dequePos[i].second--; } } rotations[dequeIdx]--; } dequePos[deques[dequeIdx].front()]={-1, 0}; helpStack.push(deques[dequeIdx].front()); deques[dequeIdx].pop_front(); cost+=h; if(printing) { ans.push_back({"push", -1}); } return; } void PopHelpStack(bool printing, bool keepOrder) { if(keepOrder) { for(int i=0; idequePos[deques[dequeIdx].front()].second) { dequePos[i].second++; } } rotations[dequeIdx]++; } dequePos[helpStack.top()]={dequeIdx, dequePos[deques[dequeIdx].front()].second+1}; deques[dequeIdx].push_front(helpStack.top()); helpStack.pop(); cost+=h; if(printing) { ans.push_back({"pop", -1}); } return; } void BuildMap() { char c='a'; for(int i=0; i usedLetters; string res=""; for(int i=0; i > order) { string res=""; for(int i=0; i > order, int symbolIdx) { if(symbolIdx==uniqueSymbols.size()) { orders.push_back(ConvertToString(order)); return; } for(int i=0; i press; press.push_back(mp[uniqueSymbols[symbolIdx]]); order.push_back(press); return GetAllOrders(order, symbolIdx+1); } void GetPartialOrders(vector > order, int symbolIdx, int targetCount) { if(symbolIdx==uniqueSymbols.size()) { orders.push_back(ConvertToString(order)); return; } int cnt=order.size(); if(cnt==0) { deque press; press.push_back(mp[uniqueSymbols[symbolIdx]]); order.push_back(press); GetPartialOrders(order, symbolIdx+1, targetCount); return; } int backCnt=order.back().size(), average=(uniqueSymbolsCnt-symbolIdx+backCnt)/(targetCount-cnt+1); if(cnt==targetCount || backCnt press; press.push_back(mp[uniqueSymbols[symbolIdx]]); order.push_back(press); GetPartialOrders(order, symbolIdx+1, targetCount); } return; } void ClearData() { deques.clear(); while(!helpStack.empty()) { helpStack.pop(); } for(int i=0; i > res; for(pair operation:ans) { if(!res.empty() && operation.first=="w " && res.back().first=="w ") { res.back().second++; } else if(!res.empty() && ((operation.first=="pop" && res.back().first=="push") || (operation.first=="push" && res.back().first=="pop"))) { res.pop_back(); } else if(a+b>2*h && !res.empty() && res.back().first=="cl" && operation.first=="cr") { res.pop_back(); res.push_back({"push", -1}), res.push_back({"pop", -1}); } else { res.push_back(operation); } } while(res.back().first!="w ") { res.pop_back(); } ans.clear(); for(pair operation:res) { ans.push_back(operation); } return; } bool LeftIsCheaper(int idx, int type) { if(type==1) { return idx*a<(deques[dequeIdx].size()-idx)*b; } return idx*h<(deques[dequeIdx].size()-idx)*b; } void PrintText(int type, bool printing) { if(type==0) { int printCnt=0; for(int i=0; iminCost) { return; } if(dequePos[mp[s[i]]].first==-1) { while(deques[dequeIdx].front()!=mp[s[i]]) { PopHelpStack(printing, false); printCnt=0; } } else { if(dequePos[mp[s[i]]].first!=dequeIdx) { while(!helpStack.empty()) { PopHelpStack(printing, false); printCnt=0; } ChangeIdx(dequePos[mp[s[i]]].first, printing); printCnt=0; } while(deques[dequeIdx].front()!=mp[s[i]]) { PushHelpStack(printing, false); printCnt=0; } } if(printing && printCnt!=0) { ans.back().second++; printCnt++; PrintSymbol(printCnt, false); } else { printCnt++; PrintSymbol(printCnt, printing); } } } else if(type==1) { int printCnt=0; for(int i=0; iminCost) { return; } if(dequeIdx!=dequePos[mp[s[i]]].first) { ChangeIdx(dequePos[mp[s[i]]].first, printing); printCnt=0; } while(deques[dequeIdx].front()!=mp[s[i]]) { if(LeftIsCheaper((rotations[dequeIdx]+dequePos[mp[s[i]]].second+deques[dequeIdx].size())%deques[dequeIdx].size(), type)) { RotateLeft(true, printing); printCnt=0; } else { RotateRight(printing); printCnt=0; } } if(printing && printCnt!=0) { ans.back().second++; printCnt++; PrintSymbol(printCnt, false); } else { printCnt++; PrintSymbol(printCnt, printing); } } } else if(type==2) { int printCnt=0; for(int i=0; iminCost) { return; } while(dequePos[mp[s[i]]].first==-1) { PopHelpStack(printing, true); printCnt=0; } if(dequeIdx!=dequePos[mp[s[i]]].first) { ChangeIdx(dequePos[mp[s[i]]].first, printing); printCnt=0; } while(deques[dequeIdx].front()!=mp[s[i]]) { if(LeftIsCheaper((rotations[dequeIdx]+dequePos[mp[s[i]]].second+deques[dequeIdx].size())%deques[dequeIdx].size(), type)) { PushHelpStack(printing, true); printCnt=0; } else { RotateRight(printing); printCnt=0; } } if(printing && printCnt!=0) { ans.back().second++; printCnt++; PrintSymbol(printCnt, false); } else { printCnt++; PrintSymbol(printCnt, printing); } } } if(printing) { OptimizeAns(); } return; } void OrderDeques(string order, int type, bool printing) { ClearData(); deques.resize(1); int idx=0, cnt=1; for(char c:order) { if(c=='<') { idx=0, cnt++; deques.resize(cnt); } else { dequePos[mp[c]]={cnt-1, idx}; deques[cnt-1].push_back(mp[c]); idx++; } } if(printing) { cout << cnt << "\n"; for(char c:order) { if(c=='<') { cout << "\n"; } else { cout << c; } } cout << "\n"; } dequeIdx=0; cost=p[cnt-1]; PrintText(type, printing); return; } void PrintAns() { cout << ans.size() << "\n"; for(pair operation:ans) { cout << operation.first; if(operation.second!=-1) { cout << operation.second; } cout << "\n"; } return; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); freopen("printing.in", "r", stdin); freopen("printing.out", "w", stdout); BuildMap(); cin >> n >> s >> a >> b >> m >> d >> h; for(int i=0; i> p[i]; } uniqueSymbols=GetUniqueSymbols(); if(uniqueSymbols.size()<9) { vector > temp; GetAllOrders(temp, 0); random_shuffle(orders.begin(), orders.end()); orders.resize(min((int)orders.size(), 1000)); } else { vector > temp; for(int i=1; i<=uniqueSymbolsCnt; i++) { GetPartialOrders(temp, 0, i); } } string minOrder; int minType; for(string order:orders) { for(int type=0; type