CODE THANKS FESTIVAL 2017(Parallel)
A - Time Penalty
最大値出力。
#include <algorithm> #include <cstdio> #include <iostream> #include <map> #include <cmath> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <vector> #include <stdlib.h> #include <stdio.h> #include <bitset> #include <cstring> #include <deque> using namespace std; #define FOR(I,A,B) for(int I = (A); I < (B); ++I) #define CLR(mat) memset(mat, 0, sizeof(mat)) typedef long long ll; int main() { ios::sync_with_stdio(false); cin.tie(0); int ans = 0; FOR(i,0,8) { int in; cin >> in; ans = max(ans, in); } cout << ans << endl; return 0; }
B - Concatenated Palindrome
sの最後の文字を含む最長の回文を求める。回文でない部分の文字数がTの文字数となる。
#include <algorithm> #include <cstdio> #include <iostream> #include <map> #include <cmath> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <vector> #include <stdlib.h> #include <stdio.h> #include <bitset> #include <cstring> #include <deque> using namespace std; #define FOR(I,A,B) for(int I = (A); I < (B); ++I) #define CLR(mat) memset(mat, 0, sizeof(mat)) typedef long long ll; int main() { ios::sync_with_stdio(false); cin.tie(0); string s; cin >> s; int len = s.length(); int ans = len - 1; // 中心1つ FOR(i,0,len) { int r = i, l = i; while(r < len && l >= 0 && s[l] == s[r]) { l--; r++; } if(r == len) { ans = min(ans, l + 1); } } // 中心二つ FOR(i,0,len-1) { int r = i + 1, l = i; while(r < len && l >= 0 && s[l] == s[r]) { l--; r++; } if(r == len) { ans = min(ans, l + 1); } } cout << ans << endl; return 0; }
C - Factory
次にi番目の機械を使うときにかかる時間とiをpriority_queueに保存。
#include <algorithm> #include <cstdio> #include <iostream> #include <map> #include <cmath> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <vector> #include <stdlib.h> #include <stdio.h> #include <bitset> #include <cstring> #include <deque> using namespace std; #define FOR(I,A,B) for(int I = (A); I < (B); ++I) #define CLR(mat) memset(mat, 0, sizeof(mat)) typedef long long ll; typedef pair<ll, int> P; int main() { ios::sync_with_stdio(false); cin.tie(0); int N, K; cin >> N >> K; ll a[N], b[N]; FOR(i,0,N) cin >> a[i] >> b[i]; priority_queue<P, vector<P>, greater<P> > Q; FOR(i,0,N) Q.push(P(a[i], i)); ll ans = 0; FOR(i,0,K) { P p = Q.top(); Q.pop(); ans += p.first; Q.push(P(p.first + b[p.second], p.second)); } cout << ans << endl; return 0; }
D - Bus Tour
証明はできないけどM - gcd(N, M)でできた。。。
#include <algorithm> #include <cstdio> #include <iostream> #include <map> #include <cmath> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <vector> #include <stdlib.h> #include <stdio.h> #include <bitset> #include <cstring> #include <deque> using namespace std; #define FOR(I,A,B) for(int I = (A); I < (B); ++I) #define CLR(mat) memset(mat, 0, sizeof(mat)) typedef long long ll; //最大公約数 int gcd(int a, int b) { while (a && b) { if (a >= b) a %= b; else b %= a; } return a + b; } int main() { ios::sync_with_stdio(false); cin.tie(0); int N, M; cin >> N >> M; int g = gcd(N, M); cout << M - g << endl; return 0; }
E - Coin Authentication
インタラクティブ問題
袋が最大50個で10回まで質問できる。つまり5個ずつ質問できる。この5個の袋について1,10,100,1000,10000枚秤に乗せることで、8,9,10,11,12を区別できる。
秤に乗せたコインの合計の重さがsumの時、
重さxのコインを1枚乗せている場合 (sum - x ) % 10 == 0となる。
次に10枚乗せたコインの重さを調べる場合sum = (sum - x) / 10として、1枚乗せている場合と同じ方法で重さを求める。
#include <algorithm> #include <cstdio> #include <iostream> #include <map> #include <cmath> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <vector> #include <stdlib.h> #include <stdio.h> #include <bitset> #include <cstring> #include <deque> using namespace std; #define FOR(I,A,B) for(int I = (A); I < (B); ++I) #define CLR(mat) memset(mat, 0, sizeof(mat)) typedef long long ll; int sum; bool f() { bool ret = 0; if((sum - 8) % 10 == 0) { sum -= 8; ret = 0; } else if((sum - 9) % 10 == 0) { sum -= 9; ret = 1; } else if((sum - 10) % 10 == 0) { sum -= 10; ret = 0; } else if((sum - 11) % 10 == 0) { sum -= 11; ret = 1; } else if((sum - 12) % 10 == 0) { sum -= 12; ret = 0; } return ret; } int main() { ios::sync_with_stdio(false); cin.tie(0); int N; cin >> N; int s = 0; vector<int> ans; while(s < N) { cout << "? "; FOR(i,0,s) cout << "0 "; cout << "1 "; s++; if(s < N) cout << "10 "; s++; if(s < N) cout << "100 "; s++; if(s < N) cout << "1000 "; s++; if(s < N) cout << "10000 "; s++; FOR(i,s,N) cout << "0 "; cout << endl; cin >> sum; while(sum) { if(f()) ans.push_back(1); else ans.push_back(0); sum /= 10; } } cout << "! "; FOR(i,0,ans.size()) printf("%d%c", ans[i], (i == ans.size() - 1 ? '\n' : ' ')); return 0; }