# Soutions for 2016-01-20

Solutions to div 2 problems:

``````/* Solution to problem A, by mallocanswer */
import java.util.*;

public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int a = in.nextInt();
int b = in.nextInt();

int temp = 0, len = 0;
while (a > 0) {
int tempA = a % 10;
int tempB = b % 10;
a /= 10;
b /= 10;
temp = temp * 10 + Math.abs(tempA - tempB);
len ++;
}

int result = 0;
while (len -- > 0) {
result = result * 10 + temp % 10;
temp /= 10;
}
System.out.println(result);
}
}

/* Solution to problem B, by MattSun */
/**
* Created by haonansun on 16/1/20.
*/

import java.util.ArrayList;
import java.util.Scanner;

public class Emoticons {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);

int n = scan.nextInt();
int res = 0;
String s = scan.next();
for (int i = 0; i < s.length(); i++) {
if (i == 0) {
continue;
}
// i != 0
char cur = s.charAt(i);
char prev = s.charAt(i - 1);
if (prev == '(' && cur == ':' || prev == ':' && cur == ')') {
res += 1;
} else if (prev == ')' && cur == ':' || prev == ':' && cur == '(') {
res -= 1;
}
}
if(res == 0){
System.out.println("BORED");
} else if(res > 0){
System.out.println("HAPPY");
} else {
}
}
}

/* Solution to problem C by MattSun */
/**
* Created by haonansun on 16/1/20.
*/

import java.util.Scanner;

public class RobotWalk {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);

int n = scan.nextInt();
int x = scan.nextInt() - 1;
String s = scan.next();
char[] src = s.toCharArray();

int l = scan.nextInt();
String dir = scan.next();
char[] res = new char[l + 1];

res[0] = src[x];

for (int i = 0; i < l; i++) {
char d = dir.charAt(i);
if (d == 'R'){
x += 1;
} else {
x -= 1;
}
res[i+1] = src[x];
}

System.out.println(res);

}
}
``````

Here are Raymond's solutions to all the div 1 problems:

``````/* Problem A */
#include <bits/stdc++.h>
using namespace std;
int main() {
int N;
scanf("%d", &N);
while (N--) {
long long l, r;
scanf("%I64d%I64d", &l, &r);
printf("%.12lf\n", 1.0 / l - 1.0 / (r + 1));
}
}

/* Problem B */
#include <bits/stdc++.h>
using namespace std;
int main() {
long long N, M;
scanf("%I64d%I64d", &N, &M);
printf("%I64d\n", (2 * M * N + M + N - abs(N - M)) / 2);
}

/* Problem C */
#include <bits/stdc++.h>
using namespace std;
int main() {
double r, R, h;
scanf("%lf%lf%lf", &r, &R, &h);
double v = r * h / (R - r);
double y = h + v;
double z = sqrt(y * y + R * R);
double x = (z * y / R) / (1 + z / R);
double d = y - x;
printf("%.12lf\n", min(h / 2, d));
}

/* Problem D */
#include <bits/stdc++.h>
using namespace std;
long long fac[20];
map<long long, int> M;
void gen(long long x, int pi) {
M[x] = true;
for (int i = pi; i <= 19; ++i)
if (x <= 1000000000000000000LL / fac[i])
gen(x * fac[i], i);
}
int main() {
fac[0] = 1;
for (int i = 1; i <= 19; ++i) fac[i] = fac[i - 1] * i;
gen(1, 2);
int N;
scanf("%d", &N);
while (N--) {
long long a;
scanf("%I64d", &a);
printf(M.find(a) != M.end() ? "YES\n" : "NO\n");
}
}

/* Problem E */
#include <bits/stdc++.h>
using namespace std;
vector<int> C[100005];
int A[100005], m;
bool minning;
const int INF = 1000000000;
int need(int x) {
if (C[x].empty()) {
if (!minning) return A[x] >= m ? 0 : INF;
return A[x] <= m ? 0 : INF;
}
int mn = INF;
long long sum = 0;
for (auto y : C[x]) {
int v = need(y);
mn = min(mn, v);
sum += v;
}
int ret = min(mn + 1LL, sum);
return ret;
}
int main() {
int N, K;
scanf("%d%d", &N, &K);
for (int i = 2; i <= N; ++i) {
int p;
scanf("%d", &p);
C[p].push_back(i);
}
int L = 0;
for (int i = 1; i <= N; ++i) {
scanf("%d", &A[i]);
if (C[i].empty()) ++L;
}
int lo = 0, hi = INF;
while (lo < hi) {
m = (lo + hi + 1) / 2;
if (need(1) <= N - L - K) lo = m;
else hi = m - 1;
}
int maxans = lo;
minning = true;
lo = 0;
hi = INF;
while (lo < hi) {
m = (lo + hi) / 2;
if (need(1) <= K) hi = m;
else lo = m + 1;
}
printf("%d %d\n", lo, maxans);
}

/* Problem F */
#include <bits/stdc++.h>
using namespace std;
int main() {
int N;
scanf("%d", &N);
set<pair<int, int> > S;
S.insert(make_pair(2000000003, 0));
while (N--) {
int sx, sy;
scanf("%d%d", &sx, &sy);
++sx;
++sy;
long long x = sx, y = sy;
auto it = S.upper_bound(make_pair(x, 1000000002));
// Check if previous guy covers
long long ans = 0;
long long h = 0;
if (it != S.begin()) {
auto pit = it;
--pit;
long long px = pit->first, py = pit->second;
if (y + x - px <= py) {
// Cover!
printf("0\n");
continue;
}
if (x == px && py <= y) {
S.erase(pit);
}
h = max(0LL, py - (x - px));
}
// We will definitely insert (x, y)
while (it != S.end()) {
long long px = it->first, py = it->second;
// Compute diff between this and previous one
// If this is too far away, break out
if (px >= x + y) {
long long add = (y - h) * h + (y - h) * (y - h + 1) / 2;
break;
}
long long add = (y - h) * (px - x);
if (h < px - x) {
add = (y - h) * h + (px - x - h) * ((y - h) + (y - (px - x)) + 1) / 2;
}
y -= (px - x);
h = py;
x = px;
// Check covered
if (y <= py) {
break;
}
S.erase(it++);
}
S.insert(make_pair(sx, sy));
printf("%I64d\n", ans);
}
}
``````

Danny Sleator
Last modified: Sat Jan 30 15:01:56 2016