## 题目描述

Two of the three members of the winning team of one of the ACM regional contests are going to meet in order to train for the upcoming World Finals. They decided that they will meet sometime between $X$ o’clock and $Y$ o’clock. Because they never get anywhere on time (they were late even on the day of the regional contest), they did not set an exact time when they will meet. However, they decided that the one who gets first at the meeting point will not wait more than $Z$ minutes for the other one (they calculated that, if the other one will not come within $Z$ minutes from the arrival of the first of them, then it is very probable that he will not show up at all).
Knowing that, in the end, both of them will show up at some time between $X$ o’clock and $Y$ o’clock (not necessarily after an integer number of minutes), compute which is the probability that they will actually meet.

## 代码

#include <cstdio>

using namespace std;

struct Solver {
private:
int x, y; double z;
void input() { scanf(" %d %d %lf", &x, &y, &z); }
void process() {
int all = (y - x) * 60;
double sum = 0;
if (2 * z <= all) sum = z + 2 * (all - z) * (z / all) / 2;
else sum = z + 2 * z * (1 - z / all) / 2;
printf("%.8lf\n", sum / all);
}

public:
void solve() { input(), process(); }
} solver;

int main() {
solver.solve();
return 0;
}


## 题目描述

The Queen of Byteland is very loved by her people. In order to show her their love, the Bytelanders have decided to conquer a new country which will be named according to the queen’s name. This new country contains $N$ towns. The towns are connected by bidirectional roads and there is exactly ONE path between any two towns, walking on the country’s roads. For each town, the profit it brings to the owner is known. Although the Bytelanders love their queen very much, they don’t want to conquer all the $N$ towns for her. They will be satisfied with a non-empty subset of these towns, with the following $2$ properties: there exists a path from every town in the subset to every other town in the subset walking only through towns in the subset and the profit of the subset is maximum. The profit of a subset of the $N$ towns is equal to the sum of the profits of the towns which belong to the subset. Your task is to find the maximum profit the Bytelanders may get.

## 代码

#include <cmath>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

namespace std {
template <typename T> void maxify(T &a, T b) { b > a && (a = b); }
template <typename T> void minify(T &a, T b) { b < a && (a = b); }
}

struct IOManager {
template <typename T> inline bool read(T &x) { char c = '\n'; bool flag = false; x = 0; while (~ c && ! isdigit(c = getchar()) && c != '-') ; c == '-' && (flag = true, c = getchar()); if (! ~ c) return false; while (isdigit(c)) x = (x << 3) + (x << 1) + c - '0', c = getchar(); return (flag && (x = -x), true); }
inline bool read(char &c) { c = '\n'; while (~ c && ! (isprint(c = getchar()) && c != ' ')) ; return ~ c; }
inline int read(char s[]) { char c = '\n'; int len = 0; while (~ c && ! (isprint(c = getchar()) && c != ' ')) ; if (! ~ c) return 0; while (isprint(c) && c != ' ') s[len ++] = c, c = getchar(); return (s[len] = '\0', len); }
template <typename T> inline IOManager operator > (T &x) { read(x); return *this; }
template <typename T> inline void write(T x) { if (x < 0) putchar('-'), x = -x; if (x > 9) write(x / 10); putchar(x % 10 + '0'); }
inline void write(char c) { putchar(c); }
inline void write(char s[]) { int pos = 0; while (s[pos] != '\0') putchar(s[pos ++]); }
template <typename T> inline IOManager operator < (T x) { write(x); return *this; }
} io;

struct Solver {
private:
static const int N = 16010;
int n, nume, h[N], w[N], f[N];
struct Edge {
int v, nxt;
} e[N << 1];
void add_edge(int u, int v) {
e[++ nume] = (Edge) { v, h[u] }, h[u] = nume;
e[++ nume] = (Edge) { u, h[v] }, h[v] = nume;
}
void input() {
io > n;
for (int i = 1; i <= n; ++ i) io > w[i];
for (int i = 1; i < n; ++ i) {
int u, v; io > u > v, add_edge(u, v);
}
}
void init() { memset(f, -0x3f, sizeof f); }
void dfs(int t, int fa) {
f[t] = w[t];
for (int i = h[t]; i; i = e[i].nxt)
if (e[i].v != fa) {
dfs(e[i].v, t);
maxify(f[t], max(f[e[i].v], f[e[i].v]));
f[t] += max(f[e[i].v], 0);
}
}
void process() { dfs(1, 0), io < max(f, f) < '\n'; }

public:
void solve() { input(), init(), process(); }
} solver;

int main() {
solver.solve();
return 0;
}


## 题目描述

Joe is a frog who likes to jump a lot. In fact, that’s all he does: he jumps forwards and backwards on the integer axis (a straight line on which all the integer numbers, both positive and negative are marked). At first, Joe sits next to the point marked with $0$. From here, he can jump in the positive or the negative direction a distance equal to either $x_1$ or $x_2$. From the point where he arrived, he can jump again a distance equal to $x_1$ or $x_2$, in the positive or the negative direction and so on.. Joe wants to arrive next to the point marked with the number $P$, after exactly $K$ jumps. You have to decide whether such a thing is possible.

## 题意概述

\left\{ \begin{align} P_1x_1-N_1x_1+P_2x_2-N_2x_2&=P \\ P_1+N_1+P_2+N_2&=K \end{align} \right.

## 代码

#include <cmath>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

#define int long long

using namespace std;

struct IOManager {
template <typename T> inline bool read(T &x) { char c = '\n'; bool flag = false; x = 0; while (~ c && ! isdigit(c = getchar()) && c != '-') ; c == '-' && (flag = true, c = getchar()); if (! ~ c) return false; while (isdigit(c)) x = (x << 3) + (x << 1) + c - '0', c = getchar(); return (flag && (x = -x), true); }
inline bool read(char &c) { c = '\n'; while (~ c && ! (isprint(c = getchar()) && c != ' ')) ; return ~ c; }
inline int read(char s[]) { char c = '\n'; int len = 0; while (~ c && ! (isprint(c = getchar()) && c != ' ')) ; if (! ~ c) return 0; while (isprint(c) && c != ' ') s[len ++] = c, c = getchar(); return (s[len] = '\0', len); }
template <typename T> inline IOManager operator > (T &x) { read(x); return *this; }
template <typename T> inline void write(T x) { if (x < 0) putchar('-'), x = -x; if (x > 9) write(x / 10); putchar(x % 10 + '0'); }
inline void write(char c) { putchar(c); }
inline void write(char s[]) { int pos = 0; while (s[pos] != '\0') putchar(s[pos ++]); }
template <typename T> inline IOManager operator < (T x) { write(x); return *this; }
} io;

struct Solver {
private:
int x1, x2, p, k;
void input() { io > x1 > x2 > p > k; }
int ex_gcd(int a, int b, int &x, int &y) {
if (! b) { x = 1, y = 0; return a; }
int ret = ex_gcd(b, a % b, y, x); y -= a / b * x; return ret;
}
bool check(int x, int y) {
if (abs(x) + abs(y) > k) return false;
if (k - abs(x) - abs(y) & 1) return false;
io < (char *) "YES\n";
int t = k - abs(x) - abs(y) >> 1;
if (x > 0) io < x + t < ' ' < t < ' ';
else io < t < ' ' < -x + t < ' ';
if (y > 0) io < y < ' ' < 0 < '\n';
else io < 0 < ' ' < -y < '\n';
return true;
}
void process() {
int x, y, gcd = ex_gcd(x1, x2, x, y);
if (p % gcd) io < (char *) "NO\n";
else {
x1 /= gcd, x2 /= gcd, p /= gcd, x *= p, y *= p;
for (int i = -abs(p) - 1; i <= abs(p) + 1; ++ i)
if (check(x + x2 * i, y - x1 * i)) goto label;
io < (char *) "NO\n";
label: ;
}
}

public:
void solve() { input(), process(); }
} solver;

signed main() {
solver.solve();
return 0;
}


## 题目描述

A sequence $A$ is called an integer sequence of length $N$ if all its elements $A_1, A_2, \ldots, A_N$ are non-negative integers less than $2000000000$. Consider two integer sequences of length $N, A$ and $X$. The result of their multiplication $(A \cdot X)$ is an integer number $R=\sum_{i=1}^N A_iX_i$. Your task is to solve the equation $A \cdot X \equiv B \pmod P$, given the integer sequence $A$ and the integer numbers $B$ and $P$.

## 算法分析

\left\{ \begin{align} A_1x_1+A_2y_1&=g_2 \\ g_2x_2+A_3y_2&=g_3 \\ \cdots& \\ g_{N-1}x_{N-1}+A_Ny_{N-1}&=g_N \\ g_Nx_N+Py_N&=(g_N, P) \end{align} \right.

## 代码

#include <cctype>
#include <cstdio>

using namespace std;

struct IOManager {
template <typename T> inline bool read(T &x) { char c = '\n'; bool flag = false; x = 0; while (~ c && ! isdigit(c = getchar()) && c != '-') ; c == '-' && (flag = true, c = getchar()); if (! ~ c) return false; while (isdigit(c)) x = (x << 3) + (x << 1) + c - '0', c = getchar(); return (flag && (x = -x), true); }
inline bool read(char &c) { c = '\n'; while (~ c && ! (isprint(c = getchar()) && c != ' ')) ; return ~ c; }
inline int read(char s[]) { char c = '\n'; int len = 0; while (~ c && ! (isprint(c = getchar()) && c != ' ')) ; if (! ~ c) return 0; while (isprint(c) && c != ' ') s[len ++] = c, c = getchar(); return (s[len] = '\0', len); }
template <typename T> inline IOManager operator > (T &x) { read(x); return *this; }
template <typename T> inline void write(T x) { if (x < 0) putchar('-'), x = -x; if (x > 9) write(x / 10); putchar(x % 10 + '0'); }
inline void write(char c) { putchar(c); }
inline void write(char s[]) { int pos = 0; while (s[pos] != '\0') putchar(s[pos ++]); }
template <typename T> inline IOManager operator < (T x) { write(x); return *this; }
} io;

struct Solver {
private:
static const int N = 101;
int n, p, m, a[N], x[N], y[N];
int ex_gcd(int a, int b, int &x, int &y) {
if (! b) { x = 1, y = 0; return a; }
int ret = ex_gcd(b, a % b, y, x); y -= a / b * x; return ret;
}
void input() {
io > n > p > m;
for (int i = 1; i <= n; ++ i) io > a[i], a[i] %= p;
}
void process() {
int g = a; x = y = 1;
for (int i = 2; i <= n; ++ i) g = ex_gcd(g, a[i], x[i - 1], y[i - 1]);
g = ex_gcd(g, p, x[n], y[n]);
if (m % g) io < (char *) "NO\n";
else {
io < (char *) "YES\n", g = m / g;
for (int i = 1; i <= n; ++ i) {
int t = g * (y[i - 1] + p);
for (int j = i; j <= n; ++ j) t = 1ll * t * (x[j] + p) % p;
io < t < ' ';
}
io < '\n';
}
}

public:
void solve() { input(), process(); }
} solver;

int main() {
solver.solve();
return 0;
}


## 题目描述

$N$ friends gathered in order to play chess, according to the following rules. In the first game, two of the $N$ friends will play. In the second game, the winner of the first game will play against another friend (maybe even the same friend who lost the first game). In the third game, the winner of the second game will play against someone else and so on.. No game will end as a draw (tie). Given the number of games each of the $N$ friends played, find a schedule for the games, so that the above rules are obeyed.

## 代码

#include <cmath>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

struct IOManager {
template <typename T> inline bool read(T &x) { char c = '\n'; bool flag = false; x = 0; while (~ c && ! isdigit(c = getchar()) && c != '-') ; c == '-' && (flag = true, c = getchar()); if (! ~ c) return false; while (isdigit(c)) x = (x << 3) + (x << 1) + c - '0', c = getchar(); return (flag && (x = -x), true); }
inline bool read(char &c) { c = '\n'; while (~ c && ! (isprint(c = getchar()) && c != ' ')) ; return ~ c; }
inline int read(char s[]) { char c = '\n'; int len = 0; while (~ c && ! (isprint(c = getchar()) && c != ' ')) ; if (! ~ c) return 0; while (isprint(c) && c != ' ') s[len ++] = c, c = getchar(); return (s[len] = '\0', len); }
template <typename T> inline IOManager operator > (T &x) { read(x); return *this; }
template <typename T> inline void write(T x) { if (x < 0) putchar('-'), x = -x; if (x > 9) write(x / 10); putchar(x % 10 + '0'); }
inline void write(char c) { putchar(c); }
inline void write(char s[]) { int pos = 0; while (s[pos] != '\0') putchar(s[pos ++]); }
template <typename T> inline IOManager operator < (T x) { write(x); return *this; }
} io;

struct Solver {
private:
static const int N = 110;
int n, sum;
pair <int, int> a[N];
vector <pair <int, int> > ans;
void input() {
io > n;
for (int i = 1; i <= n; ++ i) io > a[i].first, a[i].second = i, sum += a[i].first;
}
void process() {
io < sum >> 1 < '\n';
sort(a + 1, a + n + 1, greater <pair <int, int> >());
int p = 1;
for (int i = 0; i < sum >> 1; ++ i) {
if (a[p].first == 1) ans.push_back(make_pair(a[p + 1].second, a[p].second)), -- a[p].first, -- a[++ p].first;
else ans.push_back(make_pair(a[p].second, 0)), -- a[p].first;
}
for (int i = 0; i < sum >> 1; ++ i)
if (! ans[i].second)
for (int j = 1; j <= n; ++ j) if (a[j].first && a[j].second != ans[i].first) { ans[i].second = a[j].second, -- a[j].first; break; }
for (int i = 0; i < sum >> 1; ++ i) io < ans[i].first < ' ' < ans[i].second < '\n';
}

public:
void solve() { input(), process(); }
} solver;

int main() {
solver.solve();
return 0;
}