tourist的剧毒contest，题干长到让人不想做...
A.看不太懂题意直接看下面input output note
n组里有两数不一样的一组就rated
否则单调不增为maybe，否则unrated
B.题干给出了长度为25的数列的构造规则
i := (x div 50) mod 475
repeat 25 times:
i := (i * 96 + 42) mod 475
print (26 + i)
然后我们就需要通过几次成功和不成功的hack来调整读入的x
成功 x + 100，失败 x - 50
使得构造出来的数列中包含p，同时保证 x >= y
数据范围很小，可以直接暴力枚举
#include <bits/stdc++.h> #define rep(i, j, k) for(int i = j;i <= k;i ++) #define rev(i, j, k) for(int i = j;i >= k;i --) using namespace std; typedef long long ll; int p; bool ok(int x) { int i = x / 50 % 475; rep(j, 1, 25) { i = i* 96 + 42, i %= 475; if(i + 26 == p) return 1; } return 0; } int main() { ios::sync_with_stdio(false); int x, y, ans = 66666666; cin >> p >> x >> y; for(int i = x;i >= y;i -= 50) if(ok(i)) { ans = 0; break; } for(int i = x + 50, j = 1;j < ans;i += 50, j = (i + 50 - x) / 100) { if(ok(i)) { ans = j; break; } } cout << ans; return 0; }
C.某人在cf上，通过/提交 = x/y，他想再提交几次使 通过/提交 = p/q
求最少再提交多少次(保证p/q这个分数最简
设提交b次可行 ，则有 y + b = kq ， x <= kp <= x + b
把 b = kq - y 带入右侧不等式，则有
k >= max( ceil(x / p), ceil((y - x)/(q - p)) )
显然满足此条件的 k 均可行，所以
min_k = max( ceil(x / p), ceil((y - x)/(q - p)) )
answer = min_k * q - y
#include <cstdio> typedef long long ll; ll max(ll x, ll y) { return x > y ? x : y; } int main() { int n; ll x, y, p, q, k, k1, k2; scanf("%d", &n); while(n --) { scanf("%I64d %I64d %I64d %I64d", &x, &y, &p, &q); if(p == q) { if(x == y) puts("0"); else puts("-1"); } else if(p == 0) { if(x == 0) puts("0"); else puts("-1"); } else { k1 = x / p + (x % p != 0); k2 = (y - x) / (q - p) + ((y - x) % (q - p) != 0); printf("%I64d ", max(k1, k2) * q - y); } } return 0; }
这道题我写的正解一开始cin就一直WA
改成scanf就对了???贴出 wrong answer 的代码
#include <bits/stdc++.h> #define rep(i, j, k) for(int i = j;i <= k;i ++) #define rev(i, j, k) for(int i = j;i >= k;i --) using namespace std; typedef long long ll; int main() { ios::sync_with_stdio(false); int n; ll x, y, p, q, k; cin >> n; while(n --) { cin >> x >> y >> p >> q; if(x * q == p * y) puts("0"); else if(x * q < p * y) { if(p == q) puts("-1"); else { k = max((x + p - 1) / p, (y - x + q - p - 1) / (q - p)); cout <<k * q - y << endl; } } else { if(p == 0) puts("-1"); else { k = max((x + p - 1) / p, (y - x + q - p - 1) / (q - p)); cout << k * q - y << endl; } } } return 0; }
D.一场比赛2h，5题
给出某个题的总分与 通过人数/总人数 的关系
以及在第 i 分钟通过的人获得的分数为 max_point * (1 - i / 250)
输入包含 n 个人每个题通过的时间
其中选手1可以通过开小号来作弊
他开小号可以提交正确或错误代码
但不可能提交他自己都没过的题目的正确代码
问他最少开多少个小号可以使自己的分数 > 选手2的分数
显然一个贪心策略是(以下时间长短均对比选手2而言)
如果在某个题上选手1时间短
那么他肯定让小号都交错，提高该题分数
如果用的时间长但还是过了肯定小号都交对降低该题分数
没过的话没得选择
加粗部分使我们不能二分！
小号越多对选手1越有利吗？不！
1有个题没过但2过了
继续增加小号反而可能使该题分值增加，不利于1！
但是我们二分的时候发现R = 120 × 32(来自上面表中的 1/32
于是直接从 0 枚举到 5k 就ok...
#include <bits/stdc++.h> #define rep(i, j, k) for(int i = j;i <= k;i ++) #define rev(i, j, k) for(int i = j;i >= k;i --) using namespace std; typedef long long ll; int n; int a[200][6], c[6]; bool judge(int x) { int s = 0, t; rep(i, 1, 5) { if(a[1][i] == a[2][i]) continue; else { if(a[1][i] > a[2][i] && a[1][i] != 250) t = x; else t = 0; if(2 * (t + c[i]) > (x + n)) s += 2 * (a[2][i] - a[1][i]); else if(4 * (t + c[i]) > (x + n)) s += 4 * (a[2][i] - a[1][i]); else if(8 * (t + c[i]) > (x + n)) s += 6 * (a[2][i] - a[1][i]); else if(16 * (t + c[i]) > (x + n)) s += 8 * (a[2][i] - a[1][i]); else if(32 * (t + c[i]) > (x + n)) s += 10 * (a[2][i] - a[1][i]); else s += 12 * (a[2][i] - a[1][i]); } } return s > 0; } int main() { ios::sync_with_stdio(false); cin >> n; rep(i, 1, n) rep(j, 1, 5) { cin >> a[i][j]; if(a[i][j] == -1) a[i][j] = 250; else c[j] ++; } rep(i, 0, 5000) if(judge(i)) { cout << i; return 0; } puts("-1"); return 0; }