## 题目描述

Let’s consider a string of non-negative integers, containing $N$ elements. Suppose these elements are $S_1, S_2, \ldots, S_N$, in the order in which they are placed inside the string. Such a string is called ‘funny’ if the string $S_1+1, S_2, S_3, \ldots, S_{N-1}, S_N-1$ can be obtained by rotating the first string (to the left or to the right) several times. For instance, the strings $2, 2, 2, 3$ and $1, 2, 1, 2, 2$ are funny, but the string $1, 2, 1, 2$ is not. Your task is to find a funny string having $N$ elements, for which the sum of its elements $S_1+S_2+ \cdots +S_N$ is equal to $K$.

## 算法分析

0_______1（旧）
1_______0（新）

0______11
1______10

0____1_11
1____1_10

0__1_1_11
1__1_1_10

01_1_1_11
11_1_1_10

010101011
110101010

## 代码

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

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 = 1010;
int n, k, a[N];
void input() { io > n > k; }
void init() {
int t = k / n;
for (int i = 1; i <= n; ++ i) a[i] = t, k -= t;
}
void process() {
int sum = n - 1;
while (sum % k) sum += n;
int p = sum / k + 1;
for (; p < n; p = (p - 1 + sum / k) % n + 1) ++ a[p]; ++ a[n];
for (int i = 1; i <= n; ++ i) io < a[i] < ' ';
io < '\n';
}

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

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


## 题目描述

Little Johnny painted on a sheet of paper a polygon with $N$ vertices. Then, for every edge of the polygon, he drew the middle point of the edge. After that, he went to school. When he came back, he found out that his brother had erased the polygon (both the edges and the vertices). The only thing left were the middle points of the edges of the polygon. Help Johnny redraw his polygon.

## 算法分析

$$\left\{ \begin{array}{c} x_1+x_2=2x_1′ \\ x_2+x_3=2x_2′ \\ \cdots \\ x_N+x_1=2x_N’ \end{array} \right.$$

## 代码

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

#define random (1.0 * rand() / RAND_MAX)

using namespace std;

static const double EPS = 1e-6;
int cmp(double a, double b) {
return fabs(a - b) < EPS ? 0 : a < b ? -1 : 1;
}

struct Point {
double x, y;
Point(double _x = 0, double _y = 0) : x(_x), y(_y) {}
Point operator + (const Point &p) const { return Point(x + p.x, y + p.y); }
Point operator - (const Point &p) const { return Point(x - p.x, y - p.y); }
Point operator * (const double &n) const { return Point(x * n, y * n); }
Point operator / (const double &n) const { return *this * (1 / n); }
Point operator | (const Point &p) const { return *this + (p - *this) * 2; }
};

struct Solver {
private:
static const int N = 10010;
int n;
Point point[N];
vector <Point> ans;
void input() {
scanf("%d", &n);
for (int i = 1; i <= n; ++ i) scanf("%lf%lf", &point[i].x, &point[i].y);
}
void process() {
Point p;
if (n & 1) {
double sum = 0;
for (int i = 1; i <= n; ++ i) sum += point[i].x;
for (int i = 2; i <= n; i += 2) sum -= point[i].x * 2;
p.x = sum, sum = 0;
for (int i = 1; i <= n; ++ i) sum += point[i].y;
for (int i = 2; i <= n; i += 2) sum -= point[i].y * 2;
p.y = sum;
} else p = Point(random * 100000, random * 100000);
for (int i = 1; i <= n; ++ i) ans.push_back(p), p = p | point[i];
if (cmp(p.x, ans[0].x) || cmp(p.y, ans[0].y)) printf("NO\n");
else {
printf("YES\n");
for (int i = 0; i < ans.size(); ++ i) printf("%.6lf %.6lf\n", ans[i].x, ans[i].y);
}
}

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

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


## 题目描述

Bob really LOVES chocolate. He thinks he never gets enough. Imagine his joy when his parents told him that they would buy him many rectangular chocolate pieces for his birthday. A piece of chocolate is a $2 \times 1$ or $1 \times 2$ rectangle. Bob’s parents also bought him a nice birthday cake, which can be imagined as a matrix having $M$ rows and $N$ columns. Some positions on the cake are occupied by candles, the others are empty. Bob’s parents asked their son to place as many chocolate pieces as he can on the empty squares on the cake, in such a manner that no two chocolate pieces overlap. However, he would like to keep the chocolate pieces to himself. That’s why, he wants to place only a minimal amount of them on the cake and keep the rest. In order not to make Mon and Dad suspicious, Bob wants to place the chocolate pieces in such a way, that no other piece may be placed on the cake (that is, there won’t exist any two adjacent empty squares). Find the minimal number of pieces which need to be placed on the cake, so that they do not overlap and no extra piece may be added.

## 代码

#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 = 80;
static const int M = 8;
int n, m, f[2][1 << M][1 << M], mp[N];
void input() {
io > n > m;
for (int i = 1; i <= n; ++ i)
for (int j = 1; j <= m; ++ j) {
char c; io > c, (mp[i] <<= 1) += c == '*';
}
mp[0] = mp[n + 1] = mp[n + 2] = (1 << m) - 1;
}
void init() { memset(f, 0x1f, sizeof f), f[0][mp[0]][mp[1]] = 0; }
bool check(int s) {
bool flag = false;
for (int i = 0; i < m; s >>= 1, ++ i) {
if (s & 1) flag = false;
else { if (flag) return false; flag = true; }
}
return true;
}
void update(int x, int a, int b, int s, int val, int p) {
if (check(b) && ! ((1 << m) - 1 - a & (1 << m) - 1 - b)) minify(f[x][b][s], val);
for (int i = p; i < m; ++ i)
if (! (b & 1 << i)) {
if (! (s & 1 << i)) update(x, a, b | 1 << i, s | 1 << i, val + 1, i + 1);
if (i && ! (b & 1 << i - 1)) update(x, a, b | 1 << i | 1 << i - 1, s, val + 1, i + 1);
}
}
void process() {
int cur = 0;
for (int i = 1; i <= n + 1; cur ^= 1, ++ i) {
memset(f[cur ^ 1], 0x1f, sizeof f[cur ^ 1]);
for (int j = 0; j < 1 << m; ++ j)
for (int k = 0; k < 1 << m; ++ k)
if (f[cur][j][k] < 5e8) update(cur ^ 1, j, k, mp[i + 1], f[cur][j][k], 0);
}
io < f[cur][(1 << m) - 1][(1 << m) - 1] < '\n';
}

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

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


## 题目描述

The banquet hall of Computer Scientists’ Palace has a rectangular form of the size $M \times N$. It is necessary to lay hardwood floors in the hall. There are wood pieces of two forms:

• rectangles ($2 \times 1$)
• corners (squares $2 \times 2$ without one $1 \times 1$ square)

You have to determine $X$ – the number of ways to cover the banquet hall.
Remarks. The number of pieces is large enough. It is not allowed to leave empty places, or to cover any part of a surface twice, or to saw pieces.

## 代码

#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:
static const int N = 11;
int n, m, f[N][1 << N];
void input() { io > n > m; }
void update(int x, int y, int s, int val, int p) {
if (y == (1 << m) - 1) { f[x][s] += val; return; }
for (int i = p; i < m; ++ i)
if (! (y & 1 << i)) {
if (! (s & 1 << i)) {
update(x, y | 1 << i, s | 1 << i, val, i + 1);
if (i && ! (s & 1 << i - 1)) update(x, y | 1 << i, s | 1 << i | 1 << i - 1, val, i + 1);
if (i < m - 1 && ! (s & 1 << i + 1)) update(x, y | 1 << i, s | 1 << i | 1 << i + 1, val, i + 1);
}
if (i < m - 1 && ! (y & 1 << i + 1)) {
update(x, y | 1 << i | 1 << i + 1, s, val, i + 2);
if (! (s & 1 << i)) update(x, y | 1 << i | 1 << i + 1, s | 1 << i, val, i + 2);
if (! (s & 1 << i + 1)) update(x, y | 1 << i | 1 << i + 1, s | 1 << i + 1, val, i + 2);
}
}
}
void process() {
f[0][(1 << m) - 1] = 1;
for (int i = 0; i <= n; ++ i)
for (int j = 0; j < 1 << m; ++ j)
if (f[i][j]) update(i + 1, j, 0, f[i][j], 0);
io < f[n + 1][0] < '\n';
}

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

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


## 题目描述

The old King decided to divide the Kingdom into parts among his three sons. Each part is a polygonal area. Taking into account the bad temper of the middle son the King gave him a part of Kingdom such that moving straight from any place of this part to any other place of this part he will not cross the boundary.
There are several mineral deposits in the Kingdom. Each mineral deposit looks like a straight line segment. The middle son wants to know what part of mineral deposits is located inside his territory (not including the boundaries).

## 代码

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

using namespace std;

static const double EPS = 1e-6;
int cmp(double a, double b) { return fabs(a - b) < EPS ? 0 : a < b ? -1 : 1; }

struct Point {
double x, y;
Point(double _x = 0, double _y = 0) : x(_x), y(_y) {};
bool operator < (const Point &p) const { return ! cmp(x, p.x) ? cmp(y, p.y) == -1 : cmp(x, p.x) == -1; }
Point operator + (const Point &p) const { return Point(x + p.x, y + p.y); }
Point operator - (const Point &p) const { return Point(x - p.x, y - p.y); }
Point operator * (const double &a) const { return Point(x * a, y * a); }
Point operator / (const double &a) const { return Point(x / a, y / a); }
double operator * (const Point &p) const { return x * p.y - y * p.x; }
double operator ! () const { return sqrt(x * x + y * y); }
};

struct Line {
Point a, b;
Line(Point _a = Point(), Point _b = Point()) : a(_a), b(_b) {}
bool operator | (const Line &l) const { return ! cmp((b - a) * (l.b - l.a), 0); }
Point operator & (const Line &l) const {
double t = (a - l.a) * (l.a - l.b) / ((a - b) * (l.a - l.b));
return a + (b - a) * t;
}
};

struct Solver {
private:
static const int N = 410;
int n, q, top;
Point point[N], sta[N];
vector <Point> poly;
void input() {
scanf("%d", &n);
for (int i = 1; i <= n; ++ i) scanf("%lf%lf", &point[i].x, &point[i].y);
scanf("%d", &q);
}
void init() {
sort(point + 1, point + n + 1);
for (int i = 1; i <= n; ++ i) {
while (top > 1 && cmp((sta[top] - sta[top - 1]) * (point[i] - sta[top]), 0) < 1) -- top;
sta[++ top] = point[i];
}
for (int i = 1; i <= top; ++ i) poly.push_back(sta[i]); top = 0;
for (int i = n; i; -- i){
while (top > 1 && cmp((sta[top] - sta[top - 1]) * (point[i] - sta[top]), 0) < 1) -- top;
sta[++ top] = point[i];
}
for (int i = 2; i < top; ++ i) poly.push_back(sta[i]);
}
bool in(Point p) {
for (int i = 0; i < poly.size(); ++ i)
if (cmp((poly[(i + 1) % poly.size()] - poly[i]) * (p - poly[i]), 0) < 0) return false;
return true;
}
void process() {
Line l;
scanf("%lf%lf%lf%lf", &l.a.x, &l.a.y, &l.b.x, &l.b.y);
for (int i = 0; i < poly.size(); ++ i) {
Line tmp(poly[i], poly[(i + 1) % poly.size()]);
if (! cmp((l.b - l.a) * (tmp.a - l.a), 0) && ! cmp((l.b - l.a) * (tmp.b - l.a), 0)) {
printf("0.00\n"); return;
}
}
vector <Point> inter;
for (int i = 0; i < poly.size(); ++ i)
if (! (Line(poly[i], poly[(i + 1) % poly.size()]) | l)) {
Line tmp = Line(poly[i], poly[(i + 1) % poly.size()]);
Point p = tmp & l;
if ((cmp(p.x, l.a.x) || cmp(p.y, l.a.y)) && (cmp(p.x, l.b.x) || cmp(p.y, l.b.y)) && cmp(min(l.a.x, l.b.x), p.x) < 1 && cmp(p.x, max(l.a.x, l.b.x)) < 1 && cmp(min(l.a.y, l.b.y), p.y) < 1 && cmp(p.y, max(l.a.y, l.b.y)) < 1 && cmp(min(tmp.a.x, tmp.b.x), p.x) < 1 && cmp(p.x, max(tmp.a.x, tmp.b.x)) < 1 && cmp(min(tmp.a.y, tmp.b.y), p.y) < 1 && cmp(p.y, max(tmp.a.y, tmp.b.y)) < 1) {
for (int j = 0; j < inter.size(); ++ j) if (! cmp(inter[j].x, p.x) && ! cmp(inter[j].y, p.y)) goto label;
inter.push_back(p);
}
label: ;
}
for (int i = 0; i < poly.size(); ++ i) {
Line tmp(poly[i], poly[(i + 1) % poly.size()]);
if (! cmp((l.b - l.a) * (tmp.a - l.a), 0) && ! cmp((l.b - l.a) * (tmp.b - l.a), 0)) {
printf("0.00\n"); return;
}
}
if (inter.empty())
if (in(l.a) && in(l.b)) printf("%.2lf\n", ! (l.b - l.a));
else printf("0.00\n");
else if (inter.size() == 2) printf("%.2lf\n", ! (inter[1] - inter[0]));
else if (in(l.a)) printf("%.2lf\n", ! (inter[0] - l.a));
else if (in(l.b)) printf("%.2lf\n", ! (inter[0] - l.b));
else printf("0.00\n");
}

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

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


## 题目描述

There is a syntactically correct boolean expression.
The definition of syntactically correct expression follows as:

1. “a”, “b”, “c”, …, “j” are syntactically correct expressions.
2. If A is a correct expression, then !A and (A) are correct expressions too.
3. If A is a correct expression and B is a correct expression, then A||B, A&B, A<=>B, A=>B, A#B are syntactically correct expressions too.

Syntactically correct expression doesn’t contain spaces.
Small Latin letters are variables, ! denotes negation, || – disjunction, & – conjunction, <=> – equality, => – implication, # – excepting or.
Negation has the highest priority, conjunction has middle priority, and other operations have low priority. Brackets change the order of operations executing.
Two expressions are called identical if their values are the same in any values of variables.
Make the expression, which will be identical with given expression. New expression must be free of brackets.

## 代码

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

using namespace std;

struct Solver {
private:
string s;
void input() { cin >> s; }
int len(char c) {
switch (c) {
case '!' : return 0;
case '&' : return 0;
case '|' : return 1;
case '<' : return 2;
case '=' : return 1;
case '#' : return 0;
}
}
int priority(char c) {
switch (c) {
case '!' : return 1;
case '&' : return 2;
case '|' : return 3;
case '<' : return 3;
case '=' : return 3;
case '#' : return 3;
case '(' : return 4;
}
}
bool single(bool a, char c, bool b) {
switch (c) {
case '&' : return a && b;
case '|' : return a || b;
case '<' : return a == b;
case '=' : return a || ! b;
case '#' : return a ^ b;
}
}
int match(string s, int p) {
int cnt = 1;
while (cnt) ++ p, cnt += (s[p] == '(') - (s[p] == ')');
return p;
}
stack <char> symbol;
stack <bool> number;
void pop() {
if (symbol.top() == '!') {
symbol.pop(); bool p = number.top(); number.pop(), number.push(! p);
} else {
bool p = number.top(); number.pop();
bool q = number.top(); number.pop();
number.push(single(p, symbol.top(), q));
symbol.pop();
}
}
bool calc(string s) {
for (int i = 0; i < s.length(); ++ i) {
if (isdigit(s[i])) number.push(s[i] - '0');
else if (s[i] == '(') symbol.push('(');
else if (s[i] == ')') {
while (symbol.top() != '(') pop();
symbol.pop();
} else {
while (! symbol.empty() && priority(symbol.top()) <= priority(s[i])) pop();
symbol.push(s[i]), i += len(s[i]);
}
}
while (! symbol.empty()) pop();
return number.top();
}
bool check(int p, string s) {
for (int i = 0; i < s.length(); ++ i)
if (isalpha(s[i])) s[i] = ((p & 1 << s[i] - 'a') > 0) + '0';
return calc(s);
}
void process() {
for (int i = 0; i + 1 < s.length(); ++ i)
while (i + 1 < s.length() && s[i] == '!' && s[i + 1] == '!')
s = s.substr(0, i) + s.substr(i + 2);
string ans, sep;
for (int i = 0; i < 1 << 10; ++ i)
if (check(i, s)) {
ans += sep, sep = "||";
string s;
for (int j = 0; j < 10; ++ j) {
ans += s, s = "&";
if (! (i & 1 << j)) ans += "!";
ans += j + 'a';
}
}
if (ans.length() == 0) ans = "!a&a";
cout << ans << endl;
}

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

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


## 题目描述

There are $N$ points given by their coordinates on a plane. All coordinates $(x_i, y_i)$ are integers in a range from $-10000$ up to $10000$ inclusive . It is necessary to construct a broken line satisfying the following conditions:

• The broken line should be closed.
• End points of each segment (verteces) of the broken line can only be the given points, and all given points should be used.
• Each two consecutive segments of the broken line should form a corner of 90 degrees in each vertex point.
• The sides of the broken line should be parallel to coordinate axes.
• The broken line should have no self-crossing and self-contact.
• The broken line should have the minimal length.

You have to either find the length $L$ of the constructed broken line, or determine that it is impossible to construct such a broken line.

## 题意概述

• 这个图形是闭合的；
• 每条边的端点必须是给定的点，且每个给定的点必须被用到；
• 每个点连接的两条边必须互相垂直；
• 每条边必须平行于坐标轴；
• 任意两条边除了顶点外不能相交；
• 这个图形的周长最小。

## 代码

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

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 Point { int x, y, id; };

bool cmpx(Point a, Point b) { return a.x == b.x ? a.y < b.y : a.x < b.x; }
bool cmpy(Point a, Point b) { return a.y == b.y ? a.x < b.x : a.y < b.y; }
bool cmpi(Point a, Point b) { return a.id < b.id; }

struct Line { Point a, b; };

struct Solver {
private:
static const int N = 10010;
int n, top, fa[N];
Point point[N];
Line line[N];
void input() {
io > n;
for (int i = 1; i <= n; ++ i) io > point[i].x > point[i].y, point[i].id = i;
}
bool inter(Line p, Line q) {
if (p.a.x == p.b.x && q.a.x == q.b.x) {
if (p.a.y > q.a.y) swap(p, q);
if (p.a.x != q.a.x) return false;
else return p.b.y > q.a.y;
} else if (p.a.y == p.b.y && q.a.y == q.b.y) {
if (p.a.x > q.a.x) swap(p, q);
if (p.a.y != q.a.y) return false;
else return p.b.x > q.a.x;
} else {
if (p.a.x != p.b.x) swap(p, q);
return p.a.y < q.a.y && q.a.y < p.b.y && q.a.x < p.a.x && p.a.x < q.b.x;
}
}
int get_fa(int t) { return t == fa[t] ? t : fa[t] = get_fa(fa[t]); }
void process() {
int l = 0, r = 0, cnt = n - 1;
sort(point + 1, point + n + 1, cmpx);
for (int i = 1; i <= n; i = r) {
l = i, r = i + 1;
while (r <= n && point[r].x == point[l].x) ++ r;
if (r - l & 1) { io < 0 < '\n'; return; }
for (int j = l; j < r; j += 2) line[++ top] = (Line) { point[j], point[j + 1] };
}
sort(point + 1, point + n + 1, cmpy);
for (int i = 1; i <= n; i = r) {
l = i, r = i + 1;
while (r <= n && point[r].y == point[l].y) ++ r;
if (r - l & 1) { io < 0 < '\n'; return; }
for (int j = l; j < r; j += 2) line[++ top] = (Line) { point[j], point[j + 1] };
}
sort(point + 1, point + n + 1, cmpi);
for (int i = 1; i <= top; ++ i)
if (line[i].a.x > line[i].b.x || line[i].a.y > line[i].b.y) swap(line[i].a, line[i].b);
for (int i = 1; i < top; ++ i)
for (int j = i + 1; j <= top; ++ j)
if (inter(line[i], line[j])) { io < 0 < '\n'; return; }
for (int i = 1; i <= n; ++ i) fa[i] = i;
for (int i = 1; i <= top; ++ i) {
int p = get_fa(line[i].a.id), q = get_fa(line[i].b.id);
if (p != q) fa[p] = q, -- cnt;
}
if (cnt) { io < 0 < '\n'; return; }
int ans = 0;
for (int i = 1; i <= top; ++ i) ans += line[i].b.x - line[i].a.x + line[i].b.y - line[i].a.y;
io < ans < '\n';
}

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

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


## 题目描述

There are two boxes. There are $A$ balls in the first box, and $B$ balls in the second box. It is possible to move balls from one box to another. From one box into another one should move as many balls as the other box already contains. You have to determine, whether it is possible to move all balls into one box.

## 题目描述

There is a closed broken line on a plane with sides parallel to coordinate axes, without self-crossings and self-contacts. The broken line consists of $K$ segments. You have to determine, whether a given point with coordinates $(X_0, Y_0)$ is inside this closed broken line, outside or belongs to the broken line.

## 代码

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

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 Line { int x1, y1, x2, y2; };

struct Solver {
private:
static const int K = 10010;
int k, x, y;
Line l[K];
void input() {
io > k;
for (int i = 1; i <= k; ++ i) {
io > l[i].x1 > l[i].y1 > l[i].x2 > l[i].y2;
if (l[i].x1 > l[i].x2 || l[i].y1 > l[i].y2) swap(l[i].x1, l[i].x2), swap(l[i].y1, l[i].y2);
}
io > x > y;
}
bool in(int x, int y, Line l) {
if (l.x1 == l.x2) return x == l.x1 && l.y1 <= y && y <= l.y2;
else return y == l.y1 && l.x1 <= x && x <= l.x2;
}
void process() {
for (int i = 1; i <= k; ++ i) if (in(x, y, l[i])) { io < (char *) "BORDER\n"; return; }
int cnt = 0;
for (int i = 1; i <= k; ++ i)
cnt += l[i].x1 == l[i].x2 && l[i].x1 > x && ((l[i].y1 <= y) ^ (l[i].y2 <= y));
if (cnt & 1) io < (char *) "INSIDE\n"; else io < (char *) "OUTSIDE\n";
}

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

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


## 题目描述

There is a group of $N$ people which are numbered $1$ through $N$, and everyone of them has not less than $\left[ {N + 1 \over 2} \right]$ friends. A man with number $1$ has the book, which others want to read. Write the program which finds a way of transferring the book so that it will visit every man only once, passing from the friend to the friend, and, at last, has come back to the owner. Note: if A is a friend of B then B is a friend of A.

## 算法分析

Ore性质：一张阶数等于$N$的图中任意两个不相邻的点的度数之和不小于$N$。

• 在链上找到一点$p$（设它的下一个点是$q$），满足链头和$q$连通、链尾和$p$连通，可以删去$p$、$q$之间的边，连接链头和$q$、链尾和$p$，构成一个环；
• 如果环上的点数小于$N$，找到一个和环上一点$p$连通且不在环上的点$q$，可以删去一条$p$的边，连接$p$和$q$，构成一条链，回到上一步。

## 代码

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

using namespace std;

char c = getchar(); int len = 0;
while (~ c && c != '\n') s[len ++] = c, c = getchar();
s[len] = '\0'; return len;
}

struct Solver {
private:
static const int N = 1010;
int n, pre[N], nxt[N], near[N];
bool mp[N][N], vis[N];
char s[N << 3];
void input() {
for (int i = 1; i <= n; ++ i) {
int len = read(s), t = 0;
for (int j = 0; j <= len; ++ j)
if (isdigit(s[j])) (t *= 10) += s[j] - '0'; else mp[i][t] = true, t = 0;
}
}
void dfs(int t, int fa) {
vis[t] = true;
for (int i = 1; i <= n; ++ i)
if (mp[t][i] && ! vis[i]) { nxt[t] = i, pre[i] = t, dfs(i, t); return; }
}
int get_pre(int t) { if (! pre[t]) return t; else return get_pre(pre[t]); }
int get_nxt(int t) { if (! nxt[t]) return t; else return get_nxt(nxt[t]); }
void reverse(int p) {
nxt[p] = pre[p]; if (! pre[p]) return; reverse(pre[p]), pre[pre[p]] = p;
}
void process() {
int cnt = 0; dfs(1, 0);
for (int i = 1; i <= n; ++ i) cnt += pre[i] || nxt[i];
for (int i = 1; i <= n; ++ i) if (pre[i] || nxt[i])
for (int j = 1; j <= n; ++ j) if (mp[i][j] && ! pre[j] && ! nxt[j]) near[j] = i;
while (cnt <= n) {
int head = 0, tail = 0;
for (int i = 1; i <= n; ++ i) if (pre[i]) { head = get_pre(i); break; }
for (int i = 1; i <= n; ++ i) if (nxt[i]) { tail = get_nxt(i); break; }
for (; nxt[p]; p = nxt[p])
int tmp = nxt[p]; pre[tmp] = nxt[p] = 0, reverse(p);
nxt[head] = tmp, pre[tmp] = head, nxt[tail] = p, pre[p] = tail;
break;
}
if (cnt < n)
for (int i = 1; i <= n; ++ i) if (! pre[i] && ! nxt[i] && near[i]) {
nxt[i] = near[i], nxt[pre[near[i]]] = 0, pre[near[i]] = i;
for (int j = 1; j <= n; ++ j) if (mp[i][j] && ! pre[j] && ! nxt[j]) near[j] = i;
break;
}
++ cnt;
}
int p = 1; putchar('1');
do printf(" %d", p = nxt[p]); while (p != 1);
putchar('\n');
}

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

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