Contents
Link
- Codeforces Round #378 Div. 2 (Contest 733)
A. Grasshopper And the String
- Link: Problem
- Category: Implementation
Even this is a first problem, I get wrong answer for first time submission. It is necessary to consider a corner case at the “end of the text”.
Some other solution is inserting extra ‘A’ at the end of text so that you can handle it in the same way. (ex. latte0119’s solution)
/*
* Accepted 15 ms 0 KB
*
* Need to take care the corner case at the end - '\0' works similarly with the vowels.
*/
#include <cstdio>
#include <iostream>
using namespace std;
char s[105];
int main(){
#ifndef ONLINE_JUDGE
freopen("a.in", "r", stdin);
#endif
scanf("%s", s);
int tmp = 0;
int ability = 0;
for (int i = 0; i < 105; ++i) {
tmp++;
if (s[i] == 'A' || s[i] == 'I' || s[i] == 'U' || s[i] == 'E' || s[i] == 'O' || s[i] == 'Y'
|| s[i] == '\0') {
ability = max(ability, tmp);
tmp = 0;
if (s[i] == '\0') break;
}
}
printf("%d\n", ability);
return 0;
}
B. Parade
- Link: Problem
- Category: math
/*
* Accepted 31 ms 0 KB
*/
#include <cstdio>
#include <iostream>
using namespace std;
int main(){
#ifndef ONLINE_JUDGE
freopen("b3.in", "r", stdin);
#endif
int n;
scanf("%d", &n);
int maxb = 0, minb = 0;
int maxIndex = -1, minIndex = -1;
int B = 0; // total
for (int i = 0; i < n; ++i) {
int l, r;
scanf("%d %d", &l, &r);
int tmpb = l - r;
if (tmpb > maxb) { maxb = tmpb; maxIndex = i; }
if (tmpb < minb) { minb = tmpb; minIndex = i;}
B += tmpb;
}
int ans = 0;
int maxB = abs(B);
if (maxB < abs(B-2*maxb)) { maxB = abs(B-2*maxb); ans = maxIndex+1; }
if (maxB < abs(B-2*minb)) { maxB = abs(B-2*minb); ans = minIndex+1; }
printf("%d\n", ans);
return 0;
}
C. Epidemic in Monstropolis
- Link: Problem
- Category: greedy
The implementation amount is big, so it is difficult to solve it in time for me.
/*
* Accepted 15 ms 0 KB
*/
#include <cstdio>
#include <iostream>
#include <list>
using namespace std;
int a[505];
int b[505];
// for answer
int x[505]; // index #of the monster eat
char direction[505]; // eat direction
int main(){
#ifndef ONLINE_JUDGE
freopen("c2.in", "r", stdin);
#endif
int n, k;
scanf("%d", &n);
for (int i = 0; i < n; ++i) scanf("%d", &a[i]);
scanf("%d", &k);
for (int i = 0; i < k; ++i) scanf("%d", &b[i]);
int scanAL = 0, scanA = 0, scanB = 0;
int action = 0;
int A = 0;
bool possible = true;
while (scanA != n && scanB != k) {
A += a[scanA];
if (A == b[scanB]) {
int maxA = 0;
int winner = -1;
bool left = false; // start to eat from left.
for (int i = scanAL; i <= scanA; ++i) {
maxA = max(maxA, a[i]);
}
if (scanAL == scanA) {
// corner case: if already only 1 winner exists in this group
// do nothing
} else {
for (int i = scanAL; i <= scanA; ++i) {
if (a[i] == maxA) {
//cout << "maxA " << maxA << ", a[i] " << a[i] << endl;
if (i != scanAL && a[i-1] < a[i]) {
winner = i - scanAL;
left = true;
break;
} else if (i != scanA && a[i+1] < a[i]) {
winner = i - scanAL;
left = false;
break;
}
}
}
if (winner == -1) {
possible = false;
break;
} else {
for (int i = 0; i < scanA - scanAL; ++i) {
// winner eat all the other monsters.
if (winner > 0 && left) {
// eat L
x[action] = scanB + winner + 1;
direction[action] = 'L';
action++;
winner--;
} else {
// eat R
x[action] = scanB + winner + 1;
direction[action] = 'R';
action++;
left = true;// now possible to eat left monster
}
//cout << "scanB: " << scanB << " " << "winner: " << winner << endl;
}
}
}
scanAL = scanA+1;
scanB++;
A = 0;
} else if (A > b[scanB]) {
// impossible
possible = false;
break;
}
scanA++;
}
if (scanA != n || scanB != k) possible = false;
if (possible) {
printf("YES\n");
for (int i = 0; i < n - k; ++i) {
printf("%d %c\n", x[i], direction[i]);
}
} else {
printf("NO\n");
}
return 0;
}
D. Kostya the Sculptor
- Link: Problem
- Category: data structures – use map, normalized representaion.
Since this problem restricts to consider only 1 or 2 parallelepipe combination, we can check all the posibility. To check 2 parallelepipe combination, it takes \(O(n^2)\) with straight-forward implementation, but by using map we can reduce the search time and it can be done in \(O(nlog(n))\) time.
map‘s key must be comparable, so I used pair<int, int>.
/*
* Accepted 264 ms 11800 KB
*
* O(n log(n))
*/
#include <cstdio>
#include <iostream>
#include <map>
using namespace std;
typedef pair<int, int> P;
map<P, P> stoneMap; // key (1, 2): edge 1 and edge 2. value (first, second): 1st = edge 3, 2nd = index.
int ansNum = 0;
int ans1 = 0, ans2 = 0;
int maxR = 0;
P make_normalized_pair(int a, int b) {
if (a <= b) return make_pair(a, b);
else return make_pair(b, a);
}
void check_combination(int a, int b, int c, int i) {
auto it = stoneMap.find(make_normalized_pair(a,b));
if (it != stoneMap.end()) {
P key = it->first;
P value = it->second;
// key.first <= key.second always, no need to check key.second
int r = min(key.first, value.first + c);
if (maxR < r) {
maxR = r;
ansNum = 2;
ans1 = value.second;
ans2 = i;
}
if (value.first < c) stoneMap[make_normalized_pair(a,b)] = make_pair(c, i); // update this map
} else {// not found
stoneMap[make_normalized_pair(a,b)] = make_pair(c, i);
}
}
int main(){
#ifndef ONLINE_JUDGE
freopen("d2.in", "r", stdin);
#endif
int n;
scanf("%d", &n);
int a, b, c;
for (int i = 1; i <= n; ++i) {
scanf("%d %d %d", &a, &b, &c);
int r = min(min(a, b), c);
// check this parallelepiped
if (maxR < r) {
maxR = r;
ansNum = 1;
ans1 = i;
}
// check 2 combination
check_combination(a, b, c, i);
check_combination(b, c, a, i);
check_combination(c, a, b, i);
}
printf("%d\n", ansNum);
if (ansNum == 1) {
printf("%d\n", ans1);
} else {
printf("%d %d\n", ans1, ans2);
}
return 0;
}