A ZYB's Biology
Problem Description
After getting 600 scores in NOIP ZYB(ZJ-267) begins to work with biological questions.Now he give you a simple 阅读全文 »
Codeforces Round #334(Div.2) (3/5) (Div.1) (1/5)
maksyuki 发表于 比赛 分类，标签: 比赛-codeforces
06
12月
2015
A Uncowed Forces
Kevin Sun has just finished competing in Codeforces Round #334! The round was 120 minutes long and featured five problems with maximum point values of 500, 1000, 1500, 2000, and 2500, respectively. Despite the challenging tasks, Kevin was uncowed and bulldozed through all of them, distinguishing himself from the herd as the best cowmputer scientist in all of Bovinia. Kevin knows his submission time for each problem, the number of wrong submissions that he made on each problem, and his total numbers of successful and unsuccessful hacks. Because Codeforces scoring is complicated, Kevin wants you to write a program to compute his final score.
Codeforces scores are computed as follows: If the maximum point value of a problem is x, and Kevin submitted correctly at minute m but made w wrong submissions, then his score on that problem is . His total score is equal to the sum of his scores for each problem. In addition, Kevin's total score gets increased by 100 points for each successful hack, but gets decreased by 50 points for each unsuccessful hack.
All arithmetic operations are performed with absolute precision and no rounding. It is guaranteed that Kevin's final score is an integer.
Input
The first line of the input contains five space-separated integers m1, m2, m3, m4, m5, where mi (0 ≤ mi ≤ 119) is the time of Kevin's last submission for problem i. His last submission is always correct and gets accepted.
The second line contains five space-separated integers w1, w2, w3, w4, w5, where wi (0 ≤ wi ≤ 10) is Kevin's number of wrong submissions on problem i.
The last line contains two space-separated integers hs and hu (0 ≤ hs, hu ≤ 20), denoting the Kevin's numbers of successful and unsuccessful hacks, respectively.
Output
Print a single integer, the value of Kevin's final score.
Sample test(s)
input
20 40 60 80 100
0 1 2 3 4
1 0
output
4900
input
119 119 119 119 119
0 0 0 0 0
10 0
output
4930
Note
In the second sample, Kevin takes 119 minutes on all of the problems. Therefore, he gets of the points on each problem. So his score from solving problems is . Adding in 10·100 = 1000 points from hacks, his total score becomes 3930 + 1000 = 4930.
题目类型：水题
算法分析：直接按照题目模拟即可，注意0.3x在计算时需要用3 * x / 10来计算！！！
|
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 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 |
/************************************************* Author :supermaker Created Time :2015/12/16 23:22:28 File Location :C:\Users\abcd\Desktop\TheEternalPoet **************************************************/ #pragma comment(linker, "/STACK:102400000,102400000") #include <set> #include <bitset> #include <list> #include <map> #include <stack> #include <queue> #include <deque> #include <string> #include <vector> #include <ios> #include <iostream> #include <fstream> #include <sstream> #include <iomanip> #include <algorithm> #include <utility> #include <complex> #include <numeric> #include <functional> #include <cmath> #include <ctime> #include <climits> #include <cstdarg> #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <cassert> using namespace std; #define CFF freopen ("aaa.txt", "r", stdin) #define CPPFF ifstream cin ("aaa.txt") #define DB(ccc) cout << #ccc << " = " << ccc << endl #define PB push_back #define MP(A, B) make_pair(A, B) typedef long long LL; typedef unsigned long long ULL; typedef double DB; typedef pair <int, int> PII; typedef pair <int, bool> PIB; const int INF = 0x7F7F7F7F; const int MOD = 1e9 + 7; const double EPS = 1e-10; const double PI = 2 * acos (0.0); const int maxn = 1e5 + 6666; const int cnt[] = { 0, 500, 1000, 1500, 2000, 2500 }; int m[16], w[16]; int main() { //CFF; //CPPFF; for (int i = 1; i <= 5; i++) scanf ("%d", &m[i]); for (int i = 1; i <= 5; i++) scanf ("%d", &w[i]); int h1, h2; scanf ("%d %d", &h1, &h2); int res = 0; for (int i = 1; i <= 5; i++) { int tt = max (3 * cnt[i] / 10, (250 - m[i]) * cnt[i] / 250 - 50 * w[i]); res += tt; } res += 100 * h1; res -= 50 * h2; printf ("%d\n", res); return 0; } |
B More Cowbell
Kevin Sun wants to move his precious collection of n cowbells from Naperthrill to Exeter, where there is actually grass instead of corn. Before moving, he must pack his cowbells into k boxes of a fixed size. In order to keep his collection safe during transportation, he won't place more than two cowbells into a single box. Since Kevin wishes to minimize expenses, he is curious about the smallest size box he can use to pack his entire collection.
Kevin is a meticulous cowbell collector and knows that the size of his i-th (1 ≤ i ≤ n) cowbell is an integer si. In fact, he keeps his cowbells sorted by size, so si - 1 ≤ si for any i > 1. Also an expert packer, Kevin can fit one or two cowbells into a box of size s if and only if the sum of their sizes does not exceed s. Given this information, help Kevin determine the smallest s for which it is possible to put all of his cowbells into k boxes of size s.
Input
The first line of the input contains two space-separated integers n and k (1 ≤ n ≤ 2·k ≤ 100 000), denoting the number of cowbells and the number of boxes, respectively.
The next line contains n space-separated integers s1, s2, ..., sn (1 ≤ s1 ≤ s2 ≤ ... ≤ sn ≤ 1 000 000), the sizes of Kevin's cowbells. It is guaranteed that the sizes si are given in non-decreasing order.
Output
Print a single integer, the smallest s for which it is possible for Kevin to put all of his cowbells into k boxes of size s.
Sample test(s)
input
2 1
2 5
output
7
input
4 3
2 3 5 9
output
9
input
3 2
3 5 7
output
8
Note
In the first sample, Kevin must pack his two cowbells into the same box.
In the second sample, Kevin can pack together the following sets of cowbells: {2, 3}, {5} and {9}.
In the third sample, the optimal solution is {3, 5} and {7}.
题目类型：简单贪心
算法分析：贪心策略是最大的值尽量要单独放，由题目可以算出有多少个箱子是只装一个物品的，然后对于装两个物品的箱子，每次枚举当前最小和当前最大的值并更新
|
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 65 66 67 68 69 70 71 72 73 74 75 |
/************************************************* Author :supermaker Created Time :2015/12/16 23:47:40 File Location :C:\Users\abcd\Desktop\TheEternalPoet **************************************************/ #pragma comment(linker, "/STACK:102400000,102400000") #include <set> #include <bitset> #include <list> #include <map> #include <stack> #include <queue> #include <deque> #include <string> #include <vector> #include <ios> #include <iostream> #include <fstream> #include <sstream> #include <iomanip> #include <algorithm> #include <utility> #include <complex> #include <numeric> #include <functional> #include <cmath> #include <ctime> #include <climits> #include <cstdarg> #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <cassert> using namespace std; #define CFF freopen ("aaa.txt", "r", stdin) #define CPPFF ifstream cin ("aaa.txt") #define DB(ccc) cout << #ccc << " = " << ccc << endl #define PB push_back #define MP(A, B) make_pair(A, B) typedef long long LL; typedef unsigned long long ULL; typedef double DB; typedef pair <int, int> PII; typedef pair <int, bool> PIB; const int INF = 0x7F7F7F7F; const int MOD = 1e9 + 7; const double EPS = 1e-10; const double PI = 2 * acos (0.0); const int maxn = 1e5 + 6666; int aa[maxn], cnt[maxn]; int main() { //CFF; //CPPFF; int n, k; scanf ("%d %d", &n, &k); for (int i = 1; i <= n; i++) scanf ("%d", &aa[i]); int single = min (n, 2 * k - n); int pair = n - single; int res = aa[n]; for (int i = 1, j = pair; i < j; i++, j--) res = max (res, aa[i] + aa[j]); printf ("%d\n", res); return 0; } |
C Alternative Thinking
Kevin has just recevied his disappointing results on the USA Identification of Cows Olympiad (USAICO) in the form of a binary string of length n. Each character of Kevin's string represents Kevin's score on one of the n questions of the olympiad—'1' for a correctly identified cow and '0' otherwise.
However, all is not lost. Kevin is a big proponent of alternative thinking and believes that his score, instead of being the sum of his points, should be the length of the longest alternating subsequence of his string. Here, we define analternating subsequence of a string as a not-necessarily contiguous subsequence where no two consecutive elements are equal. For example, {0, 1, 0, 1}, {1, 0, 1}, and {1, 0, 1, 0} are alternating sequences, while{1, 0, 0} and {0, 1, 0, 1, 1} are not.
Kevin, being the sneaky little puffball that he is, is willing to hack into the USAICO databases to improve his score. In order to be subtle, he decides that he will flip exactly one substring—that is, take a contiguous non-empty substring of his score and change all '0's in that substring to '1's and vice versa. After such an operation, Kevin wants to know the length of the longest possible alternating subsequence that his string could have.
Input
The first line contains the number of questions on the olympiad n (1 ≤ n ≤ 100 000).
The following line contains a binary string of length n representing Kevin's results on the USAICO.
Output
Output a single integer, the length of the longest possible alternating subsequence that Kevin can create in his string after flipping a single substring.
Sample test(s)
input
8
10000011
output
5
input
2
01
output
2
Note
In the first sample, Kevin can flip the bolded substring '10000011' and turn his string into '10011011', which has an alternating subsequence of length 5: '10011011'.
In the second sample, Kevin can flip the entire string and still have the same score.
题目类型：构造
算法分析：将一个对任意区间的翻转行为看作是由两个前缀区间翻转得到的，而且相邻相同的值可以缩成一个值。这样一来易知若一个前缀区间最后一个值两边的值相同，则翻转这个区间会使得总个数+1，反之，则会使得总个数-1。简单化简并计算即可
|
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 65 66 67 68 69 70 |
/************************************************* Author :supermaker Created Time :2016/1/20 23:23:31 File Location :C:\Users\abcd\Desktop\TheEternalPoet **************************************************/ #pragma comment(linker, "/STACK:102400000,102400000") #include <set> #include <bitset> #include <list> #include <map> #include <stack> #include <queue> #include <deque> #include <string> #include <vector> #include <ios> #include <iostream> #include <fstream> #include <sstream> #include <iomanip> #include <algorithm> #include <utility> #include <complex> #include <numeric> #include <functional> #include <cmath> #include <ctime> #include <climits> #include <cstdarg> #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <cassert> using namespace std; #define CFF freopen ("aaa.txt", "r", stdin) #define CPPFF ifstream cin ("aaa.txt") #define DB(ccc) cout << #ccc << " = " << ccc << endl #define PB push_back #define MP(A, B) make_pair(A, B) typedef long long LL; typedef unsigned long long ULL; typedef double DB; typedef pair <int, int> PII; typedef pair <int, bool> PIB; const int INF = 0x7F7F7F7F; const int MOD = 1e9 + 7; const double EPS = 1e-10; const double PI = 2 * acos (0.0); const int maxn = 1e5 + 6666; int main() { //CFF; //CPPFF; int n; cin >> n; string s; cin >> s; int res = 1; for (int i = 0; i < s.size () - 1; i++) if (s[i] != s[i+1]) res++; cout << min (res + 2, n) << endl; return 0; } |