题面

Fighting_小银考呀考不过四级
Time Limit: 1000MS Memory Limit: 65536KB

Problem Description
四级考试已经过去好几个星期了，但是小银还是对自己的英语水平担心不已。
小银打算好好学习英语，争取下次四级考试和小学弟小学妹一起拿下它！
四级考试的时候，监考老师会按考号分配固定的座位，但唯一不变的是每两个人之间肯定至少会留下两个空座位，原因相信大家都懂得。
那么问题来了，我们现在只关注教室里的一排座位，假设每排有n个座位，小银想知道这一排至少坐一个人的前提下，一共有多少种坐法。

Input
多组输入。
第一行输入整数n，代表教室里这一排的座位数目。(1 <= n <= 45)

Output
输出种类数目。输入输出各占一行，保证数据合法。

Example Input
1
3
5

Example Output
1
3
8

Hint

Author
Casithy

题面

迷の有序序列
Time Limit: 1000MS Memory Limit: 65536KB

Problem Description
n个数，每次可以选择其中一个数移动到序列任意位置。 至少操作几次能让该序列有序

Input
多组输入，输入到文件结束。 每组输入一个正整数n(0 < n <= 1000) 之后一行输入n个正整数xi(0 < xi < 10^9)，表示原始序列

Output
对于每组输入，输出一个整数，表示让序列变为有序所需要的最少操作次数 Hint: 第三组可以选择把1移到2前
也可以把2移动到1后

Example Input
3
1 2 3
3
3 2 1
3
2 1 3

Example Output
0
0
1

Author
LeiQ

题面

MoutainTop
Time Limit: 1000MS Memory Limit: 65536KB

Problem Description
金石山脉有n个山峰，一字排开，从西向东依次编号为1, 2, 3, ……, n。编号为i的山峰高度为hi。每个山峰的高度两两不同
小木示从西向东依次爬过这n个山峰，到每一个山峰的山顶的时候，他都会往西边眺望，并且会记录下自己能看到的山峰的个数。
（比如说小木示现在在4号山峰，前四号山峰的高度分别为9,4,5,1。他现在能看到的山峰个数就是2,因为第二个山峰被第三个山峰挡住了）
严格的来说，小木示在i位置的时候，对于一个山峰j (j < i)，如果不存在一个山峰k满足hj < hk (j < k < i)。则山峰j是可见的。
小木示把自己记录的山峰的个数加和作为这次爬山的快乐值，现在给你n个山峰的高度，求小木示的快乐值。

Input
多组输入，首先输入一个n（1<=n<=10^6）,表示山峰的个数。 接下来一行n个数，表示对应山峰的山峰的高度(1<=h<=10^6)。

Output
输出小木示的快乐值

Example Input
4
1 6 5 1

Example Output
4

Author
JueChen

所需基础

计算几何 - 凸包、了解 Graham's Scan 算法及其极角序实现。

概述

Graham's Scan 算法的水平序实现是不同于「极角序」的另一种实现方式，它将平面点集按照水平序排序，即按 y 坐标排序，相同时再按 x 坐标排序，之后进行扫描来求得凸包。

题面

飞花的传送门
Time Limit: 1000ms Memory limit: 65536K

题目描述
飞花壕最近手头比较宽裕，所以想买两个传送门来代步（夏天太热，实在是懒得走路）。平面上有N个传送门，飞花壕想要挑两个距离最远的传送门带回家（距离为欧几里得距离，即两点之间直线距离）。

请你帮他算一算他所挑选的最远的两个传送门有多远。

输入
多组输入。

对于每组输入，第一行输入一个整数N（2 <= N <= 50000），接下来从第2行到第N+1行，每行两个整数（Xi，Yi），代表第i个传送门的坐标（-1000000 <= Xi , Yi <= 1000000）。

数据为随机生成。

输出
输出一个整数，代表飞花壕要挑选的两个传送门的距离的平方。

示例输入
4
0 0
0 1
1 1
1 0

示例输出
2

提示

来源
GLSilence