Link
- Codeforces Round #373 Div. 2 (Contest 719)
A. Vitya in the Countryside
Basically, check last 2 character to determine its direction is “UP” or “DOWN”. Special case comes when the last number is 0 or 15, in that case the direction changes and you can determine the direction without looking second last character.
#include <cstdio>
#include <iostream>
using namespace std;
int a[100];
int main(){
#ifndef ONLINE_JUDGE
freopen("a3.in", "r", stdin);
#endif
int n;
scanf("%d", &n);
for (int i = 0; i < n; ++i) {
scanf("%d", &a[i]);
}
if (n >= 2) {
if (a[n-1] == 15) {
printf("DOWN\n");
} else if (a[n-1] == 0) {
printf("UP\n");
} else {
if (a[n-1] > a[n-2]) {
printf("UP\n");
} else {
printf("DOWN\n");
}
}
} else if (n == 1) {
if (a[n-1] == 15) {
printf("DOWN\n");
} else if (a[n-1] == 0) {
printf("UP\n");
} else {
printf("-1\n");
}
}
return 0;
}
B. Anatoly and Cockroaches
We can consider 2 patterns for final alignment. Pattern 0 is to align “rbrbrb…” and pattern 1 is to align “brbrbr…”.
We will compare the original alignment and final alignment. For each position i, we need to change the color to…
- Case A: r to b
- Case B: b to r
If both case A and B exists, the optimal way to change color is to replace these cockroaches. and if only case A or case B exists we can change color by can. After this optimal way, the total number of count is same the maximum number of Case A & Case B.
We take smaller number of total count between pattern 0 & 1.
/*
* Accepted 46 ms 244 KB
*/
#include <cstdio>
#include <iostream>
using namespace std;
int main(){
#ifndef ONLINE_JUDGE
freopen("b.in", "r", stdin);
#endif
int n;
scanf("%d", &n);
string s;
cin >> s;
// 0: rbrbrb..., 1 brbrbr...
int rtob[2] = {0};
int btor[2] = {0};
// 0
for (int i = 0; i < n; ++i) {
char target0 = (i%2) ? 'r' : 'b';
if (s[i] == target0) {
//i.e., s[i] != target1
if (i%2==0) {
rtob[1]++;
} else {
btor[1]++;
}
} else {
if (i%2==0) {
btor[0]++;
} else {
rtob[0]++;
}
}
}
int count[2];
count[0] = max(rtob[0], btor[0]);
count[1] = max(rtob[1], btor[1]);
int ans = min(count[0], count[1]);
printf("%d\n", ans);
return 0;
}
C. Efim and Strange Grade
The best policy to update is scan from the nearest integer and if the number is greater than or equal to 5, then round it.
Special case heppens only when the rounded value changes from 4 to 5, then we need to round this value.
So if we have ….444445…., we need to update manytimes. But if you have ….24244336…, rounding 6 one time is enough.
/*
* Accepted 77 ms 500 KB
*/
#include <cstdio>
#include <iostream>
using namespace std;
int main(){
#ifndef ONLINE_JUDGE
freopen("c7.in", "r", stdin);
#endif
int n, t;
scanf("%d %d", &n, &t);
string s;
cin >> s;
int decimalPoint = -1;
for (int i = 0; i < n; ++i) {
if (s[i] == '.') {
decimalPoint = i;
break;
}
}
if (decimalPoint == -1) {
// do nothing
} else {
int left = -1; // position of most left 4 of ...444445...
int right = -1; // position of right 5 of ...444445...
bool reset = true;
for (int i = decimalPoint + 1; i < n; ++i) {
if (s[i] < '4') {
// reset flag
reset = true;
left = -1;
} else if (s[i] == '4') {
if (reset) {
left = i;
reset = false;
} else {
// do nothing
}
} else { // s[i] >= '5'
right = i;
break;
}
}
if (right == -1) {
// nothing should be rounded
} else {
if (left == -1) {
// round up only once at position 'right'
if (right == decimalPoint + 1) {
// increment up integer
int checkPos = decimalPoint-1;
while (checkPos >= 0) {
if (s[checkPos] == '9') {
s[checkPos] = '0';
checkPos--;
} else {
s[checkPos]++;
break;
}
}
s = s.substr(0, decimalPoint);
if (checkPos < 0) {
s = "1" + s;
}
} else {
s[right-1]++;
s = s.substr(0, right);
}
} else { // left != -1
// form of ...4445...
if (t < right-left+1) {
// round up t times is the optimal way
s[right - t] = '5';
s = s.substr(0, right - t + 1);
} else {
// round up only once at position 'left' == 5
if (left == decimalPoint + 1) {
// increment up integer
int checkPos = decimalPoint-1;
while (checkPos >= 0) {
if (s[checkPos] == '9') {
s[checkPos] = '0';
checkPos--;
} else {
s[checkPos]++;
break;
}
}
s = s.substr(0, decimalPoint);
if (checkPos < 0) {
s = "1" + s;
}
} else {
s[left-1]++;
s = s.substr(0, left);
}
}
}
}
}
cout << s;
return 0;
}