1.stone
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> using namespace std; const int N = 1e6 + 10; int a[N], n; int main() { scanf("%d", &n); for (int i = 1; i <= n; ++ i) scanf("%d", &a[i]); double res = 1.0; for (int i = 2; i <= n; ++ i) { res += (double)a[i] / (a[i] + a[1]); } printf("%.6lf\n", res); } |
2.memory
60pts ~~
|
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 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 |
#include <bits/stdc++.h> using namespace std; const int N = 1e5 + 10, INF = 0x3f3f3f3f; int a[N], b[N]; int n, m, k; int f(int x) { int cnt = 1, sum = 0; for (int i = 1; i <= n; ++ i) { if (b[i] > x) return INF; if (b[i] + sum > x) { sum = b[i]; cnt ++; } else sum += b[i]; } return cnt; } int main() { // freopen("memory.in", "r", stdin); // freopen("memory.ans", "w", stdout); scanf("%d%d%d", &n, &m, &k); for (int i = 1; i <= n; ++ i) scanf("%d", &a[i]); int res = INF; for (int x = 0; x < m; ++ x) { for (int i = 1; i <= n; ++ i) b[i] = (a[i] + x) % m; int l = 0, r = 1e9; while (l < r) { int mid = l + r >> 1; if (f(mid) > k) l = mid + 1; else r = mid; } res = min(res, l); } cout << res << endl; } |
3.subset
20pts ~~
|
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 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 |
#include <bits/stdc++.h> typedef long long LL; using namespace std; LL n; vector<int> a; int gcd(int a, int b) { return b ? gcd(b, a % b) : a; } int ff(int a, int b) { return a * b / gcd(a, b); } bool isp(LL x) { if (x <= 1) return false; for (LL i = 2; i <= x / i; ++ i) if (x % i == 0) return false; return true; } int main() { freopen("subset.in", "r", stdin); freopen("subset.ans", "w", stdout); cin >> n; if (isp(n)) { cout << 1 << endl; return 0; } for (int i = 1; i <= n; ++ i) if (n % i == 0) a.push_back(i); int res = 0; for (int i = 0; i < 1 << a.size(); ++ i) { int x, y; bool falg = false; for (int j = 0; j < a.size(); ++ j) { if ((i >> j & 1) && falg) { x = gcd(x, a[j]); y = ff(y, a[j]); } if (!falg && (i >> j & 1)) { x = a[j]; y = a[j]; falg = true; } } if (falg && x == 1 && y == n) res ++; } cout << res << endl; } |
发表回复