SRM398Div.2あと糞問
@kagamizさん、@siquareさん、@Lepton_sさんとプラクティス
内容はThe Div.2だったけど、条件ゲーで、英語ゲーだった。
Cubicさんは途中でVSにEmacsのキーバインド登録し間違えてたり、英語に苦戦してたりしてた
MinDifference
数列列挙→ソート→全探査
class MinDifference { public: int closestElements( int A0, int X, int Y, int M, int n ) { vector<int> a(1, A0); for (int i=1; i<n; i++) { a.push_back((a[i-1]*X+Y)%M); } sort(a.begin(), a.end()); int res = 10001; for (int i=1; i<n; i++) { res = min(res, a[i]-a[i-1]); } return res; } };
CountExpressions
最初計算の順序普通だと思ってて書くのめんどくさとか思ってましたが、実は掛け算とか気にしなくてよくて、ようするにやるだけだった(ねくすとぱ〜みゅて〜しょん)
class CountExpressions { public: int calcExpressions( int x, int y, int val ) { int num[4] = {x, x, y, y}; sort(num, num+4); int cnt = 0; do { for (int i=0; i<3; i++) { for (int j=0; j<3; j++) { for (int k=0; k<3; k++) { int r=num[0]; if (i==0) r+=num[1]; else if (i==1) r-=num[1]; else r*=num[1]; if (j==0) r+=num[2]; else if (j==1) r-=num[2]; else r*=num[2]; if (k==0) r+=num[3]; else if (k==1) r-=num[3]; else r*=num[3]; if (r==val) { cnt++; } } } } } while(next_permutation(num, num+4)); return cnt; } };
MatchString
最初スライドが右だけということに気づかずなんでテスト1の答え違うのとか思ってましたが…
どっちにしろやるだけ
class MatchString { public: int placeWords( string matchString, vector <string> matchWords ) { vector<int> ismatch[50]; int n = matchString.length(); memset(ismatch, 0, sizeof(ismatch)); bool flag=true; for (int i=0; i<n; i++) { bool flag2=false; for (int j=0; j<matchWords[i].length(); j++) { if (matchString[i]==matchWords[i][j]) { flag2=true; ismatch[i].push_back(j); } } if (!flag2) flag=false; } // puts("ok"); if (!flag) return -1; int res = INT_MAX / 2; for (int l=0; l<n; l++) { for (int i=0; i<ismatch[l].size(); i++) { int adr = ismatch[l][i]; int temp = 0; bool flag = true; for (int j=0; j<n; j++) { if (l==j) continue; int mins = INT_MAX / 2; for (int k=0; k<ismatch[j].size(); k++) { if (adr < ismatch[j][k]) break; mins = min(mins, abs(ismatch[j][k]-adr)); } if (mins==INT_MAX/2) { flag = false; break; } temp += mins; } if (flag) res = min(res, temp); } } return res; } };
AOJ 0238
#include <cstdio> int main() { int t, n; while (scanf("%d",&t)) { if (t==0) break; scanf("%d",&n); int sum = 0; for (int i=0; i<n; i++) { int s, f; scanf("%d%d",&s,&f); sum += f - s; } if (sum >= t) puts("OK"); else printf("%d\n",t-sum); } }