# Codeforces Round #377 Div. 2 review

It can be paid without change if the change is 0 or $$r$$.

#include <cstdio>
#include <iostream>

using namespace std;

int main(){
#ifndef ONLINE_JUDGE
freopen("a3.in", "r", stdin);
#endif
int k, r;
scanf("%d %d", &k, &r);

int i;
for (i = 1; i < 10; ++i) {
int change = k * i % 10;
if (change == 0 || change == r) break;
}
printf("%d", i);
return 0;
}

## B. Cormen — The Best Friend Of a Man

At day $$i$$, dog need to walk $$k−a[i−1]$$ times.
/*
*
*/
#include <cstdio>
#include <iostream>

using namespace std;

int a[505];

int main(){
#ifndef ONLINE_JUDGE
freopen("b3.in", "r", stdin);
#endif
int n, k;
scanf("%d %d", &n, &k);
for (int i = 0; i < n; ++i) {
scanf("%d", &a[i]);
}

int inc = 0;
for (int i = 1; i < n; ++i) {
if (a[i-1] + a[i] >= k) continue;
inc += k - a[i-1] - a[i];
a[i] = k - a[i-1];
}
printf("%d\n", inc);
for (int i = 0; i < n; ++i) {
printf("%d%c", a[i], i==n-1 ? '\n' : ' ');
}

return 0;
}

## C. Sanatorium

Basic idea to the solution is not difficult, just check all the popssibility of what time start eating (enter room) and what time end eating (exit room). But the corner case handling makes this problem difficult and I cannot answer correctly in one time.

Rather than below, more elegant/ short code solution can be found at pekempey’s solution.

#include <cstdio>
#include <iostream>

using namespace std;
typedef long long ll;

int main(){
#ifndef ONLINE_JUDGE
freopen("c4.in", "r", stdin);
#endif
ll b[3];
cin >> b[0] >> b[1] >> b[2];

ll minimum = 3000000000000000000LL;
for (int i = 0; i < 3; ++i) {// 0: 0,0,0. 1: 0,0,1, 2: 0,1,1
for (int k = 0; k < i; ++k) { b[2-k]--; }
for (int j = 0; j < 3; ++j) {// 0: 0,0,0. 1: 1,0,0, 2: 1,1,0
for (int k = 0; k < j; ++k) { b[k]--; }
ll missed = 0;
ll middleDay = max(max(b[0], b[1]), b[2]);
if (middleDay >= 0) {
missed += middleDay*3 - (b[0]+b[1]+b[2]);
minimum = min(minimum, missed);
}
for (int k = 0; k < j; ++k) { b[k]++; }
}
for (int k = 0; k < i; ++k) { b[2-k]++; }
}
if (b[0] == 0 && b[1] == 1 && b[2] == 0) minimum = 0;
cout << minimum;
return 0;
}

## D. Exams

Use binary search. Fix the duration x days, and we can check if it is possible to pass all the tests in x days or not.

In each check it costs $$O(N)$$, so in total it takes $$O(NlogN)$$ to find the solution.
/*
* Binary search
* O(NlogN)
*
* Check if all tests can be passed by n days or not.
*/
#include <cstdio>
#include <iostream>

using namespace std;

int n, m;
int d[100005];
int a[100005];
bool used[100005];

//Check if all tests can be passed by x days or not.
bool C(int x) {
used[0] = true;
for (int i = 1; i <= m; ++i) {
used[i] = false; // init
}
int passed = 0;  // #of passed subject
int day = 0;     // total necessary preparation days
for (int i = x - 1; i >= 0; --i) {
if (!used[d[i]]) { // take exam of d[i]
passed++;
day += a[d[i]];
used[d[i]] = true;
} else {  // study subject of used[d[i]] == true.
if(day > 0) day--;
}
}
if (passed == m && day == 0) return true;
else return false;
}

int main(){
#ifndef ONLINE_JUDGE
freopen("d3.in", "r", stdin);
#endif
scanf("%d %d", &n, &m);
for (int i = 0; i < n; ++i) {
scanf("%d", &d[i]);
}
for (int i = 1; i <= m; ++i) {
scanf("%d", &a[i]);
}
int lb=0, ub=n;  // can do between (lb, ub]
while (ub - lb > 1) {
int middle = (lb+ub)/2;
if (C(middle)) ub = middle;
else lb = middle;
//cout << lb << " " << ub << " " << middle << endl;
}
if (ub == n && !C(n)) ub = -1;
printf("%d\n", ub);

return 0;
}