title: A+B Problem

type: P

background:
强烈推荐[新用户必读帖](/discuss/show/241461)。

**不熟悉算法竞赛的选手请看这里：**

算法竞赛中要求的输出格式中，**不能有多余的内容**，**这也包括了“请输入整数 $\bm a$ 和 $\bm b$” 这一类的提示用户输入信息的内容**。若包含了这些内容，将会被认为是 `Wrong Answer`，即洛谷上的 `WA`。在对比代码输出和标准输出时，系统将忽略每一行结尾的空格，以及最后一行之后多余的换行符。

若因此类问题出现本机似乎输出了正确的结果，但是实际提交结果为错误的现象，请勿认为是洛谷评测机出了问题，而是你的代码中可能存在多余的输出信息。用户可以参考在题目末尾提供的代码。

此外，**请善用应用中的在线 IDE 功能**，以避免不同平台的评测产生差异。

最后，请不要在对应的题目讨论区中发布自己的题解，请发布到题解区域中，否则将处以删除或禁言的处罚。若发现无法提交题解则表明本题题解数量过多，仍不应发布讨论。若您的做法确实与其他所有题解均不一样，请联系管理员添加题解。

description:
输入两个整数 $a, b$，输出它们的和（$|a|,|b| \le {10}^9$）。

注意

1. Pascal 使用 `integer` 会爆掉哦！
2. 有负数哦！
3. C/C++ 的 main 函数必须是 `int` 类型，而且 C 最后要 `return 0`。这不仅对洛谷其他题目有效，而且也是 NOIP/CSP/NOI 比赛的要求！

好吧，同志们，我们就从这一题开始，向着大牛的路进发。

> 任何一个伟大的思想，都有一个微不足道的开始。

inputFormat: 两个以空格分开的整数。

outputFormat: 一个整数。

hint:
**广告**

洛谷出品的算法教材，帮助您更简单的学习基础算法。[【官方网店绝赞热卖中！】>>>](https://item.taobao.com/item.htm?id=637730514783)

[![](https://cdn.luogu.com.cn/upload/image_hosting/njc7dlng.png)](https://item.taobao.com/item.htm?id=637730514783)

**本题各种语言的程序范例：**

C
```c
#include <stdio.h>

int main()
{
    int a,b;
    scanf("%d%d",&a,&b);
    printf("%d\n", a+b);
    return 0;
}
```
----------------

C++
```cpp
#include <iostream>
#include <cstdio>

using namespace std;

int main()
{
    int a,b;
    cin >> a >> b;
    cout << a+b << endl;
    return 0;
}
```
----------------

Pascal
```cpp
var a, b: longint;
begin
    readln(a,b);
    writeln(a+b);
end.
```
-----------------

Python2

```cpp
s = raw_input().split()
print int(s[0]) + int(s[1])
```
-----------------

Python3

```cpp
s = input().split()
print(int(s[0]) + int(s[1]))
```
-----------------

Java
```java
import java.io.*;
import java.util.*;
public class Main {
    public static void main(String args[]) throws Exception {
        Scanner cin=new Scanner(System.in);
        int a = cin.nextInt(), b = cin.nextInt();
        System.out.println(a+b);
    }
}
```
-----------------

JavaScript （Node.js）

```javascript
const fs = require('fs')
const data = fs.readFileSync('/dev/stdin')
const result = data.toString('ascii').trim().split(' ').map(x => parseInt(x)).reduce((a, b) => a + b, 0)
console.log(result)
process.exit() // 请注意必须在出口点处加入此行
```

-----------------

Ruby

```ruby
a, b = gets.split.map(&:to_i)
print a+b
```

-----------------

PHP

```php
<?php
$input = trim(file_get_contents("php://stdin"));
list($a, $b) = explode(' ', $input);
echo $a + $b;
```

-----------------

Rust

```rust
use std::io;

fn main(){
    let mut input=String::new();
    io::stdin().read_line(&mut input).unwrap();
    let mut s=input.trim().split(' ');

    let a:i32=s.next().unwrap()
               .parse().unwrap();
    let b:i32=s.next().unwrap()
               .parse().unwrap();
    println!("{}",a+b);
}
```

-----------------

Go

```go
package main

import "fmt"

func main() {
    var a, b int
    fmt.Scanf("%d%d", &a, &b)
    fmt.Println(a+b)
}
```

-----------------

C# Mono

```cs
using System;

public class APlusB{
    private static void Main(){
        string[] input = Console.ReadLine().Split(' ');
        Console.WriteLine(int.Parse(input[0]) + int.Parse(input[1]));
    }
}
```

------------------

Visual Basic Mono

```vb
Imports System

Module APlusB
    Sub Main()
        Dim ins As String() = Console.ReadLine().Split(New Char(){" "c})
        Console.WriteLine(Int(ins(0))+Int(ins(1)))
    End Sub
End Module
```

------------------

Kotlin

```kotlin
fun main(args: Array<String>) {
    val (a, b) = readLine()!!.split(' ').map(String::toInt)
    println(a + b)
}
```

------------------

Haskell

```haskell
main = do
    [a, b] <- (map read . words) `fmap` getLine
    print (a+b)
```

------------------

Lua

```lua
a = io.read('*n')
b = io.read('*n')
print(a + b)
```

------------------

OCaml

```ocaml
Scanf.scanf "%i %i\n" (fun a b -> print_int (a + b))
```

------------------

Julia

```julia
nums = map(x -> parse(Int, x), split(readline(), " "))
println(nums[1] + nums[2])
```

------------------

Scala

```scala
object Main extends App {
    println(scala.io.StdIn.readLine().split(" ").map(_.toInt).sum)
}
```

------------------

Perl

```perl
my $in = <STDIN>;
chomp $in;
$in = [split /[\s,]+/, $in];
my $c = $in->[0] + $in->[1];
print "$c\n";
```


title: [NOIP2002 普及组] 过河卒

description:
棋盘上 $A$ 点有一个过河卒，需要走到目标 $B$ 点。卒行走的规则：可以向下、或者向右。同时在棋盘上 $C$ 点有一个对方的马，该马所在的点和所有跳跃一步可达的点称为对方马的控制点。因此称之为“马拦过河卒”。

棋盘用坐标表示，$A$ 点 $(0, 0)$、$B$ 点 $(n, m)$，同样马的位置坐标是需要给出的。

![](https://cdn.luogu.com.cn/upload/image_hosting/ipmwl52i.png)

现在要求你计算出卒从 $A$ 点能够到达 $B$ 点的路径的条数，假设马的位置是固定不动的，并不是卒走一步马走一步。

inputFormat: 一行四个正整数，分别表示 $B$ 点坐标和马的坐标。

outputFormat: 一个整数，表示所有的路径条数。

hint:
对于 $100 \%$ 的数据，$1 \le n, m \le 20$，$0 \le$ 马的坐标 $\le 20$。

**【题目来源】**

NOIP 2002 普及组第四题


title: [NOIP2011 提高组] 铺地毯

description:
为了准备一个独特的颁奖典礼，组织者在会场的一片矩形区域（可看做是平面直角坐标系的第一象限）铺上一些矩形地毯。一共有 $n$ 张地毯，编号从 $1$ 到 $n$。现在将这些地毯按照编号从小到大的顺序平行于坐标轴先后铺设，后铺的地毯覆盖在前面已经铺好的地毯之上。

地毯铺设完成后，组织者想知道覆盖地面某个点的最上面的那张地毯的编号。注意：在矩形地毯边界和四个顶点上的点也算被地毯覆盖。

inputFormat:
输入共 $n + 2$ 行。

第一行，一个整数 $n$，表示总共有 $n$ 张地毯。

接下来的 $n$ 行中，第 $i+1$ 行表示编号 $i$ 的地毯的信息，包含四个整数 $a ,b ,g ,k$，每两个整数之间用一个空格隔开，分别表示铺设地毯的左下角的坐标 $(a, b)$ 以及地毯在 $x$ 轴和 $y$ 轴方向的长度。

第 $n + 2$ 行包含两个整数 $x$ 和 $y$，表示所求的地面的点的坐标 $(x, y)$。

outputFormat: 输出共 $1$ 行，一个整数，表示所求的地毯的编号；若此处没有被地毯覆盖则输出 `-1`。

hint:
【样例解释 1】

如下图，$1$ 号地毯用实线表示，$2$ 号地毯用虚线表示，$3$ 号用双实线表示，覆盖点 $(2,2)$ 的最上面一张地毯是 $3$ 号地毯。

![](https://cdn.luogu.com.cn/upload/image_hosting/q4izfzpb.png)

【数据范围】

对于 $30\%$ 的数据，有 $n \le 2$。
对于 $50\%$ 的数据，$0 \le a, b, g, k \le 100$。
对于 $100\%$ 的数据，有 $0 \le n \le 10^4$, $0 \le a, b, g, k \le {10}^5$。

noip2011 提高组 day1 第 $1$ 题。


title: [NOIP2000 提高组] 方格取数

background: NOIP 2000 提高组 T4

description:
设有 $N \times N$ 的方格图 $(N \le 9)$，我们将其中的某些方格中填入正整数，而其他的方格中则放入数字 $0$。如下图所示（见样例）:

![](https://cdn.luogu.com.cn/upload/image_hosting/0bpummja.png)

某人从图的左上角的 $A$ 点出发，可以向下行走，也可以向右走，直到到达右下角的 $B$ 点。在走过的路上，他可以取走方格中的数（取走后的方格中将变为数字 $0$）。
此人从 $A$ 点到 $B$ 点共走两次，试找出 $2$ 条这样的路径，使得取得的数之和为最大。

inputFormat: 输入的第一行为一个整数 $N$（表示 $N \times N$ 的方格图），接下来的每行有三个整数，前两个表示位置，第三个数为该位置上所放的数。一行单独的 $0$ 表示输入结束。

outputFormat: 只需输出一个整数，表示 $2$ 条路径上取得的最大的和。

hint: 数据范围：$1\le N\le 9$。


title: [NOIP2007 提高组] 矩阵取数游戏

description:
帅帅经常跟同学玩一个矩阵取数游戏：对于一个给定的 $n \times m$ 的矩阵，矩阵中的每个元素 $a_{i,j}$ 均为非负整数。游戏规则如下：

1. 每次取数时须从每行各取走一个元素，共 $n$ 个。经过 $m$ 次后取完矩阵内所有元素；
2. 每次取走的各个元素只能是该元素所在行的行首或行尾；
3. 每次取数都有一个得分值，为每行取数的得分之和，每行取数的得分 = 被取走的元素值 $\times 2^i$，其中 $i$ 表示第 $i$ 次取数（从 $1$ 开始编号）；
4. 游戏结束总得分为 $m$ 次取数得分之和。

帅帅想请你帮忙写一个程序，对于任意矩阵，可以求出取数后的最大得分。

inputFormat:
输入文件包括 $n+1$ 行：

第一行为两个用空格隔开的整数 $n$ 和 $m$。

第 $2\sim n+1$ 行为 $n \times m$ 矩阵，其中每行有 $m$ 个用单个空格隔开的非负整数。

outputFormat: 输出文件仅包含 $1$ 行，为一个整数，即输入矩阵取数后的最大得分。

hint:
**【数据范围】**

对于 $60\%$ 的数据，满足 $1\le n,m\le 30$，答案不超过 $10^{16}$。
对于 $100\%$ 的数据，满足 $1\le n,m\le 80$，$0\le a_{i,j}\le1000$。

**【题目来源】**

NOIP 2007 提高第三题。


title: [NOIP2008 提高组] 传纸条

description:
小渊和小轩是好朋友也是同班同学，他们在一起总有谈不完的话题。一次素质拓展活动中，班上同学安排坐成一个 $m$ 行 $n$ 列的矩阵，而小渊和小轩被安排在矩阵对角线的两端，因此，他们就无法直接交谈了。幸运的是，他们可以通过传纸条来进行交流。纸条要经由许多同学传到对方手里，小渊坐在矩阵的左上角，坐标 $(1,1)$，小轩坐在矩阵的右下角，坐标 $(m,n)$。从小渊传到小轩的纸条只可以向下或者向右传递，从小轩传给小渊的纸条只可以向上或者向左传递。

在活动进行中，小渊希望给小轩传递一张纸条，同时希望小轩给他回复。班里每个同学都可以帮他们传递，但只会帮他们一次，也就是说如果此人在小渊递给小轩纸条的时候帮忙，那么在小轩递给小渊的时候就不会再帮忙。反之亦然。

还有一件事情需要注意，全班每个同学愿意帮忙的好感度有高有低（注意：小渊和小轩的好心程度没有定义，输入时用 $0$ 表示），可以用一个 $[0,100]$ 内的自然数来表示，数越大表示越好心。小渊和小轩希望尽可能找好心程度高的同学来帮忙传纸条，即找到来回两条传递路径，使得这两条路径上同学的好心程度之和最大。现在，请你帮助小渊和小轩找到这样的两条路径。

inputFormat:
第一行有两个用空格隔开的整数 $m$ 和 $n$，表示班里有 $m$ 行 $n$ 列。

接下来的 $m$ 行是一个 $m \times n$ 的矩阵，矩阵中第 $i$ 行 $j$ 列的整数表示坐在第 $i$ 行 $j$ 列的学生的好心程度。每行的 $n$ 个整数之间用空格隔开。

outputFormat: 输出文件共一行一个整数，表示来回两条路上参与传递纸条的学生的好心程度之和的最大值。

hint:
**【数据范围】**

对于 $30\%$ 的数据，满足 $1 \le m,n \le 10$。
对于 $100\%$ 的数据，满足 $1 \le m,n \le 50$。

**【题目来源】**

NOIP 2008 提高组第三题。


title: 独木桥

background: 战争已经进入到紧要时间。你是运输小队长，正在率领运输部队向前线运送物资。运输任务像做题一样的无聊。你希望找些刺激，于是命令你的士兵们到前方的一座独木桥上欣赏风景，而你留在桥下欣赏士兵们。士兵们十分愤怒，因为这座独木桥十分狭窄，只能容纳 $1$ 个人通过。假如有 $2$ 个人相向而行在桥上相遇，那么他们 $2$ 个人将无法绕过对方，只能有 $1$ 个人回头下桥，让另一个人先通过。但是，可以有多个人同时呆在同一个位置。

description:
突然，你收到从指挥部发来的信息，敌军的轰炸机正朝着你所在的独木桥飞来！为了安全，你的部队必须撤下独木桥。独木桥的长度为 $L$，士兵们只能呆在坐标为整数的地方。所有士兵的速度都为 $1$，但一个士兵某一时刻来到了坐标为 $0$ 或 $L+1$ 的位置，他就离开了独木桥。

每个士兵都有一个初始面对的方向，他们会以匀速朝着这个方向行走，中途不会自己改变方向。但是，如果两个士兵面对面相遇，他们无法彼此通过对方，于是就分别转身，继续行走。转身不需要任何的时间。

由于先前的愤怒，你已不能控制你的士兵。甚至，你连每个士兵初始面对的方向都不知道。因此，你想要知道你的部队最少需要多少时间就可能全部撤离独木桥。另外，总部也在安排阻拦敌人的进攻，因此你还需要知道你的部队最多需要多少时间才能全部撤离独木桥。

inputFormat:
第一行共一个整数 $L$，表示独木桥的长度。桥上的坐标为 $1, 2, \cdots, L$。

第二行共一个整数 $N$，表示初始时留在桥上的士兵数目。

第三行共有 $N$ 个整数，分别表示每个士兵的初始坐标。

outputFormat: 共一行，输出 $2$ 个整数，分别表示部队撤离独木桥的最小时间和最大时间。$2$ 个整数由一个空格符分开。

hint: 对于 $100\%$ 的数据，满足初始时，没有两个士兵同在一个坐标，$1\le  L\le5\times 10^3$，$0\le N\le5\times10^3$，且数据保证 $N\le L$。


title: [NOIP1998 普及组] 三连击

background: 本题为提交答案题，您可以写程序或手算在本机上算出答案后，直接提交答案文本，也可提交答案生成程序。

description: 将 $1, 2, \ldots , 9$ 共 $9$ 个数分成 $3$ 组，分别组成 $3$ 个三位数，且使这 $3$ 个三位数构成 $1 : 2 : 3$ 的比例，试求出所有满足条件的 $3$ 个三位数。

inputFormat: 无

outputFormat: 若干行，每行 $3$ 个数字。按照每行第 $1$ 个数字升序排列。

hint: NOIP1998 普及组 第一题


title: [NOIP1998 普及组] 阶乘之和

description:
用高精度计算出 $S = 1! + 2! + 3! + \cdots + n!$（$n \le 50$）。

其中 `!` 表示阶乘，定义为 $n!=n\times (n-1)\times (n-2)\times \cdots \times 1$。例如，$5! = 5 \times 4 \times 3 \times 2 \times 1=120$。

inputFormat: 一个正整数 $n$。

outputFormat: 一个正整数 $S$，表示计算结果。

hint:
**【数据范围】**

对于 $100 \%$ 的数据，$1 \le n \le 50$。

**【其他说明】**

注，《深入浅出基础篇》中使用本题作为例题，但是其数据范围只有 $n \le 20$，使用书中的代码无法通过本题。

如果希望通过本题，请继续学习第八章高精度的知识。

NOIP1998 普及组 第二题


title: [NOIP1998 普及组] 幂次方

description:
任何一个正整数都可以用 $2$ 的幂次方表示。例如 $137=2^7+2^3+2^0 $。

同时约定次方用括号来表示，即 $a^b$ 可表示为 $a(b)$。

由此可知，$137$ 可表示为 $2(7)+2(3)+2(0)$

进一步：

$7= 2^2+2+2^0$  ( $2^1$ 用 $2$ 表示)，并且 $3=2+2^0$。

所以最后 $137$ 可表示为 $2(2(2)+2+2(0))+2(2+2(0))+2(0)$。

又如 $1315=2^{10} +2^8 +2^5 +2+1$

所以 $1315$ 最后可表示为 $2(2(2+2(0))+2)+2(2(2+2(0)))+2(2(2)+2(0))+2+2(0)$。

inputFormat: 一行一个正整数 $n$。

outputFormat: 符合约定的 $n$ 的 $0, 2$ 表示（在表示中不能有空格）。

hint:
**【数据范围】**

对于 $100\%$ 的数据，$1 \le n \le 2 \times {10}^4$。

NOIP1998 普及组 第三题


title: [NOIP1998 提高组] 车站

description: 火车从始发站（称为第 $1$ 站）开出，在始发站上车的人数为 $a$，然后到达第 $2$ 站，在第 $2$ 站有人上、下车，但上、下车的人数相同，因此在第 $2$ 站开出时（即在到达第 $3$ 站之前）车上的人数保持为 $a$ 人。从第 $3$ 站起（包括第 $3$ 站）上、下车的人数有一定规律：上车的人数都是前两站上车人数之和，而下车人数等于上一站上车人数，一直到终点站的前一站（第 $n-1$ 站），都满足此规律。现给出的条件是：共有 $n$ 个车站，始发站上车的人数为 $a$，最后一站下车的人数是 $m$（全部下车）。试问 $x$ 站开出时车上的人数是多少？

inputFormat: 输入只有一行四个整数，分别表示始发站上车人数 $a$，车站数 $n$，终点站下车人数 $m$ 和所求的站点编号 $x$。

outputFormat: 输出一行一个整数表示答案：从 $x$ 站开出时车上的人数。

hint:
对于全部的测试点，保证 $1 \leq a \leq 20$，$1 \leq x \leq n \leq 20$，$1 \leq m \leq 2 \times 10^4$。

NOIP1998 提高组 第一题


title: [NOIP1998 提高组] 拼数

description: 设有 $n$ 个正整数 $a_1 \dots a_n$，将它们联接成一排，相邻数字首尾相接，组成一个最大的整数。

inputFormat:
第一行有一个整数，表示数字个数 $n$。

第二行有 $n$ 个整数，表示给出的 $n$ 个整数 $a_i$。

outputFormat: 一个正整数，表示最大的整数

hint:
对于全部的测试点，保证 $1 \leq n \leq 20$，$1 \leq a_i \leq 10^9$。

NOIP1998 提高组 第二题


title: [NOIP1998 提高组] 进制位

description:
著名科学家卢斯为了检查学生对进位制的理解，他给出了如下的一张加法表，表中的字母代表数字。 例如：

$$
\def\arraystretch{2}
\begin{array}{c||c|c|c|c}
\rm +  & \kern{.5cm} \rm \mathclap{L} \kern{.5cm}  &  \kern{.5cm} \rm \mathclap{K} \kern{.5cm} &  \kern{.5cm} \rm \mathclap{V} \kern{.5cm} & \kern{.5cm} \rm \mathclap{E} \kern{.5cm} \\ \hline\hline
\rm L  &  \rm L  &  \rm K  &  \rm V  & \rm E  \\ \hline
\rm K  &  \rm K  &  \rm V  &  \rm E  & \rm \mathclap{KL} \\ \hline
\rm V  &  \rm V  &  \rm E  &  \rm \mathclap{KL} & \rm \mathclap{KK} \\ \hline
\rm E  &  \rm E  &  \rm \mathclap{KL} &  \rm \mathclap{KK} & \rm \mathclap{KV} \\
\end{array}$$

其含义为：

$L+L=L$，$L+K=K$，$L+V=V$，$L+E=E$

$K+L=K$，$K+K=V$，$K+V=E$，$K+E=KL$

$\cdots$

$E+E=KV$

根据这些规则可推导出：$L=0$，$K=1$，$V=2$，$E=3$。

同时可以确定该表表示的是 $4$ 进制加法。

inputFormat:
第一行一个整数 $n$（$3\le n\le9$）表示行数。

以下 $n$ 行，每行包括 $n$ 个字符串，每个字符串间用空格隔开。）

若记 $s_{i,j}$ 表示第 $i$ 行第 $j$ 个字符串，数据保证 $s_{1,1}=\texttt +$，$s_{i,1}=s_{1,i}$，$|s_{i,1}|=1$，$s_{i,1}\ne s_{j,1}$ （$i\ne j$）。

保证至多有一组解。

outputFormat:
第一行输出各个字母表示什么数，格式如：`L=0 K=1` $\cdots$ 按给出的字母顺序排序。不同字母必须代表不同数字。

第二行输出加法运算是几进制的。

若不可能组成加法表，则应输出 `ERROR!`。

samples:
5
+ L K V E
L L K V E
K K V E KL
V V E KL KK
E E KL KK KV

hint: NOIP1998 提高组 第三题


title: [NOIP1999 普及组] Cantor 表

description:
现代数学的著名证明之一是 Georg Cantor 证明了有理数是可枚举的。他是用下面这一张表来证明这一命题的：

![](https://cdn.luogu.com.cn/upload/image_hosting/jdjdaf73.png)

我们以 Z 字形给上表的每一项编号。第一项是 $1/1$，然后是 $1/2$，$2/1$，$3/1$，$2/2$，…

inputFormat: 整数$N$（$1 \leq N \leq 10^7$）。

outputFormat: 表中的第 $N$ 项。


title: [NOIP1999 普及组] 回文数

description:
若一个数（首位不为零）从左向右读与从右向左读都一样，我们就将其称之为回文数。

例如：给定一个十进制数 $56$，将 $56$ 加 $65$（即把 $56$ 从右向左读），得到 $121$ 是一个回文数。

又如：对于十进制数 $87$：

STEP1：$87+78=165$
STEP2：$165+561=726$
STEP3：$726+627=1353$
STEP4：$1353+3531=4884$

在这里的一步是指进行了一次 $N$ 进制的加法，上例最少用了 $4$ 步得到回文数 $4884$。

写一个程序，给定一个 $N$（$2 \le N \le 10$ 或 $N=16$）进制数 $M$（$100$ 位之内），求最少经过几步可以得到回文数。如果在 $30$ 步以内（包含 $30$ 步）不可能得到回文数，则输出 `Impossible!`。

inputFormat: 两行，分别是 $N$，$M$。

outputFormat:
如果能在 $30$ 步以内得到回文数，输出格式形如 `STEP=ans`，其中 $\text{ans}$ 为最少得到回文数的步数。

否则输出 `Impossible!`。


title: [NOIP1999 提高组] 旅行家的预算

description: 一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市（假设出发时油箱是空的）。给定两个城市之间的距离 $D_1$、汽车油箱的容量 $C$（以升为单位）、每升汽油能行驶的距离 $D_2$、出发点每升汽油价格$P$和沿途油站数 $N$（$N$ 可以为零），油站 $i$ 离出发点的距离 $D_i$、每升汽油价格 $P_i$（$i=1,2,…,N$）。计算结果四舍五入至小数点后两位。如果无法到达目的地，则输出 `No Solution`。

inputFormat:
第一行，$D_1$，$C$，$D_2$，$P$，$N$。

接下来有 $N$ 行。

第 $i+1$ 行，两个数字，油站 $i$ 离出发点的距离 $D_i$ 和每升汽油价格 $P_i$。

outputFormat: 所需最小费用，计算结果四舍五入至小数点后两位。如果无法到达目的地，则输出 `No Solution`。

hint:
$N \le 6$，其余数字 $ \le 500$。

NOIP1999 普及组第三题、提高组第三题


title: [NOIP2000 提高组] 进制转换

background: NOIP2000 提高组 T1

description:
我们可以用这样的方式来表示一个十进制数：将每个阿拉伯数字乘以一个以该数字所处位置为指数，以 $10$ 为底数的幂之和的形式。例如 $123$ 可表示为 $1 \times 10^2+2\times 10^1+3\times 10^0$ 这样的形式。

与之相似的，对二进制数来说，也可表示成每个二进制数码乘以一个以该数字所处位置为指数，以 $2$ 为底数的幂之和的形式。

一般说来，任何一个正整数 $R$ 或一个负整数 $-R$ 都可以被选来作为一个数制系统的基数。如果是以 $R$ 或 $-R$ 为基数，则需要用到的数码为 $0,1,\dots,R-1$。

例如当 $R=7$ 时,所需用到的数码是 $0,1,2,3,4,5,6$，这与其是 $R$ 或 $-R$ 无关。如果作为基数的数绝对值超过 $10$，则为了表示这些数码，通常使用英文字母来表示那些大于 $9$ 的数码。例如对 $16$ 进制数来说,用 $A$ 表示 $10$，用 $B$ 表示 $11$，用 $C$ 表示 $12$，以此类推。

在负进制数中是用 $-R $ 作为基数，例如 $-15$（十进制）相当于 $(110001)_{-2}$（$-2$进制），并且它可以被表示为 $2$ 的幂级数的和数：

$$(110001)_{-2}=1\times (-2)^5+1\times (-2)^4+0\times (-2)^3+0\times (-2)^2+0\times (-2)^1 +1\times (-2)^0$$

设计一个程序，读入一个十进制数和一个负进制数的基数，并将此十进制数转换为此负进制下的数。

inputFormat:
输入的每行有两个输入数据。

第一个是十进制数 $n$。第二个是负进制数的基数 $R$。

outputFormat: 输出此负进制数及其基数，若此基数超过 $10$，则参照 $16$ 进制的方式处理。


title: [NOIP2000 提高组] 乘积最大

background: NOIP2000 提高组 T2

description:
今年是国际数学联盟确定的“2000——世界数学年”，又恰逢我国著名数学家华罗庚先生诞辰 90 周年。在华罗庚先生的家乡江苏金坛，组织了一场别开生面的数学智力竞赛的活动，你的一个好朋友 XZ 也有幸得以参加。活动中，主持人给所有参加活动的选手出了这样一道题目：

设有一个长度为 $N$ 的数字串，要求选手使用 $K$ 个乘号将它分成 $K+1$ 个部分，找出一种分法，使得这 $K+1$ 个部分的乘积能够为最大。

同时，为了帮助选手能够正确理解题意，主持人还举了如下的一个例子：

有一个数字串：$312$，当 $N=3,K=1$ 时会有以下两种分法：

1. $3  \times  12=36$
2. $31  \times   2=62$

这时，符合题目要求的结果是：$31  \times  2 = 62$。

现在，请你帮助你的好朋友 XZ 设计一个程序，求得正确的答案。

inputFormat:
程序的输入共有两行：

第一行共有 $2$ 个自然数 $N,K$。

第二行是一个长度为 $N$ 的数字串。

outputFormat: 结果显示在屏幕上，相对于输入，应输出所求得的最大乘积（一个自然数）。

hint:
**数据范围与约定**

对于 $60\%$ 的测试数据满足 $6≤N≤20$。
对于所有测试数据，$6≤N≤40,1≤K≤6$。


title: [NOIP2000 提高组] 单词接龙

background:
注意：本题为上古 NOIP 原题，不保证存在靠谱的做法能通过该数据范围下的所有数据。

本题为搜索题，本题不接受 hack 数据。[关于此类题目的详细内容](https://www.luogu.com.cn/paste/isdgwj5l)

NOIP2000 提高组 T3

description: 单词接龙是一个与我们经常玩的成语接龙相类似的游戏，现在我们已知一组单词，且给定一个开头的字母，要求出以这个字母开头的最长的“龙”（每个单词都最多在“龙”中出现两次），在两个单词相连时，其重合部分合为一部分，例如 `beast` 和 `astonish`，如果接成一条龙则变为 `beastonish`，另外相邻的两部分不能存在包含关系，例如 `at` 和 `atide` 间不能相连。

inputFormat: 输入的第一行为一个单独的整数 $n$ 表示单词数，以下 $n$ 行每行有一个单词，输入的最后一行为一个单个字符，表示“龙”开头的字母。你可以假定以此字母开头的“龙”一定存在。

outputFormat: 只需输出以此字母开头的最长的“龙”的长度。

hint:
样例解释：连成的“龙”为 `atoucheatactactouchoose`。

$n \le 20$。


title: [NOIP1999 提高组] 导弹拦截

description:
某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。

输入导弹依次飞来的高度，计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。

inputFormat: 一行，若干个整数，中间由空格隔开。

outputFormat: 两行，每行一个整数，第一个数字表示这套系统最多能拦截多少导弹，第二个数字表示如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。

hint:
对于前 $50\%$ 数据（NOIP 原题数据），满足导弹的个数不超过 $10^4$ 个。该部分数据总分共 $100$ 分。可使用$\mathcal O(n^2)$ 做法通过。
对于后 $50\%$ 的数据，满足导弹的个数不超过 $10^5$ 个。该部分数据总分也为 $100$ 分。请使用 $\mathcal O(n\log n)$ 做法通过。

对于全部数据，满足导弹的高度为正整数，且不超过 $5\times 10^4$。

此外本题开启 spj，每点两问，按问给分。

NOIP1999 提高组 第一题

---

$\text{upd 2022.8.24}$：新增加一组 Hack 数据。


title: [NOIP1999 提高组] 邮票面值设计

background:
除直接打表外，本题不保证存在**正确且时间复杂度可以通过全部数据**做法。由于测试数据过水，部分错误做法可以通过此题，通过不代表做法正确。本题不接受 hack 数据。

[关于此类题目的详细内容](https://www.luogu.com.cn/paste/isdgwj5l)

description:
给定一个信封，最多只允许粘贴 $N$ 张邮票，计算在给定 $K$（$N+K \le 15$）种邮票的情况下（假定所有的邮票数量都足够），如何设计邮票的面值，能得到最大值 $\mathsf{MAX}$，使在 $1$ 至 $\mathsf{MAX}$ 之间的每一个邮资值都能得到。

例如，$N=3$，$K=2$，如果面值分别为 $1$ 分、$4$ 分，则在 $1\sim 6$ 分之间的每一个邮资值都能得到（当然还有 $8$ 分、$9$ 分和 $12$ 分）；如果面值分别为 $1$ 分、$3$ 分，则在 $1\sim 7$ 分之间的每一个邮资值都能得到。可以验证当 $N=3$，$K=2$ 时，$7$ 分就是可以得到的连续的邮资最大值，所以 $\mathsf{MAX}=7$，面值分别为 $1$ 分、$3$ 分。

inputFormat: $2$ 个整数，代表 $N$，$K$。

outputFormat:
输出共 $2$ 行。

第一行输出若干个数字，表示选择的面值，从小到大排序。

第二行，输出 `MAX=S`，$S$ 表示最大的面值。


title: [NOIP2000 普及组] 计算器的改良

background: NCL 是一家专门从事计算器改良与升级的实验室，最近该实验室收到了某公司所委托的一个任务：需要在该公司某型号的计算器上加上解一元一次方程的功能。实验室将这个任务交给了一个刚进入的新手 ZL 先生。

description:
为了很好的完成这个任务，ZL 先生首先研究了一些一元一次方程的实例：

- $4+3x=8$。
- $6a-5+1=2-2a$。
- $-5+12y=0$。

ZL 先生被主管告之，在计算器上键入的一个一元一次方程中，只包含整数、小写字母及 `+`、`-`、`=` 这三个数学符号（当然，符号“`-`”既可作减号，也可作负号）。方程中并没有括号，也没有除号，方程中的字母表示未知数。

你可假设对键入的方程的正确性的判断是由另一个程序员在做，或者说可认为键入的一元一次方程均为合法的，且有唯一实数解。

inputFormat: 一个一元一次方程。

outputFormat: 解方程的结果（精确至小数点后三位）。


title: [NOIP2000 普及组] 税收与补贴问题

background:
每样商品的价格越低，其销量就会相应增大。现已知某种商品的成本及其在若干价位上的销量（产品不会低于成本销售），并假设相邻价位间销量的变化是线性的且在价格高于给定的最高价位后，销量以某固定数值递减。（我们假设价格及销售量都是整数）

对于某些特殊商品，不可能完全由市场去调节其价格。这时候就需要政府以税收或补贴的方式来控制。（所谓税收或补贴就是对于每个产品收取或给予生产厂家固定金额的货币）

description:
你是某家咨询公司的项目经理，现在你已经知道政府对某种商品的预期价格，以及在各种价位上的销售情况。要求你确定政府对此商品是应收税还是补贴的最少金额（也为整数），才能使商家在这样一种政府预期的价格上，获取相对其他价位上的最大总利润。

- 总利润 $=$ 单位商品利润 $\times$ 销量
- 单位商品利润 $=$ 单位商品价格 $-$ 单位商品成本（减去税金 或者 加上补贴）

inputFormat:
输入的第一行为政府对某种商品的预期价；

 第二行有两个整数，第一个整数为商品成本，第二个整数为以成本价销售时的销售量；

 接下来若干行，每行都有两个整数，第一个为某价位时的单价，第二个为此时的销量，以一行 `-1 -1` 表示所有已知价位及对应的销量输入完毕；

 输入的最后一行为一个单独的整数表示在已知的最高单价外每升高一块钱将减少的销量。

outputFormat:
输出有两种情况：若在政府预期价上能得到最大总利润，则输出一个单独的整数，数的正负表示是补贴还是收税，数的大小表示补贴或收税的金额最小值。若有多解，取绝对值最小的输出。

如在政府预期价上不能得到最大总利润，则输出 `NO SOLUTION`。

hint:
### 数据范围及约定

保证输入的所有数字均小于 $10^5$。

### 样例解释（2023/6/22 更新）

如下图所示是输入样例所对应的价格变化图，横轴表示销售价格，纵轴表示销量。

![](https://cdn.luogu.com.cn/upload/image_hosting/21mhtm5i.png)

根据题意，$28$ 元是商品的成本。销售价格不应该低于 $28$ 元；当销售价格大于给出的价格的最大值 $31$ 元后，按照售价每提高一元，销量降低 $15$ 计算，例如当售价为 $33$ 元时，销量为 $110-15\times (33-31)=80$。在给出来的价位之间，销量呈线性变化。

当政府给该商品补贴 $4$ 元后，企业将该商品定价为 $31$ 元时，取得的利润为 $31-28+4=7$ 元，销量为 $110$ 件，总利润为 $7\times 110=770$ 元，是企业在所有定价下能够取得的最大的总利润。此时企业的售价为政府的期望售价，因此是一个合法方案。


title: [NOIP2001 提高组] 一元三次方程求解

description:
有形如：$a x^3 + b x^2 + c x + d = 0$  这样的一个一元三次方程。给出该方程中各项的系数（$a,b,c,d$ 均为实数），并约定该方程存在三个不同实根（根的范围在 $-100$ 至 $100$ 之间），且根与根之差的绝对值 $\ge 1$。要求由小到大依次在同一行输出这三个实根(根与根之间留有空格)，并精确到小数点后 $2$ 位。

提示：记方程 $f(x) = 0$，若存在 $2$ 个数 $x_1$ 和 $x_2$，且 $x_1 < x_2$，$f(x_1) \times f(x_2) < 0$，则在 $(x_1, x_2)$ 之间一定有一个根。

inputFormat: 一行，$4$ 个实数 $a, b, c, d$。

outputFormat: 一行，$3$ 个实根，从小到大输出，并精确到小数点后 $2$ 位。

hint:
**【题目来源】**

NOIP 2001 提高组第一题


title: [NOIP2001 提高组] 数的划分

description:
将整数 $n$ 分成 $k$ 份，且每份不能为空，任意两个方案不相同（不考虑顺序）。

例如：$n=7$，$k=3$，下面三种分法被认为是相同的。

$1,1,5$;
$1,5,1$;
$5,1,1$.

问有多少种不同的分法。

outputFormat: $1$ 个整数，即不同的分法。


title: [NOIP2001 提高组] 统计单词个数

description:
给出一个长度不超过 $200$ 的由小写英文字母组成的字母串（该字串以每行 $20$ 个字母的方式输入，且保证每行一定为 $20$ 个）。要求将此字母串分成
 $k$ 份，且每份中包含的单词个数加起来总数最大。

每份中包含的单词可以部分重叠。当选用一个单词之后，其第一个字母不能再用。例如字符串 `this` 中可包含 `this` 和 `is`，选用 `this` 之后就不能包含
 `th`。

单词在给出的一个不超过 $6$ 个单词的字典中。

要求输出最大的个数。

inputFormat:
每组的第一行有两个正整数 $p,k$。
$p$ 表示字串的行数，$k$ 表示分为 $k$ 个部分。

接下来的 $p$ 行，每行均有 $20$ 个字符。

再接下来有一个正整数 $s$，表示字典中单词个数。
接下来的 $s$ 行，每行均有一个单词。

outputFormat: $1$个整数，分别对应每组测试数据的相应结果。

hint:
【数据范围】
对于 $100\%$ 的数据，$2 \le k \le 40$，$1 \le s \le 6$。

【样例解释】
划分方案为 this / isabookyoua / reaoh

**【题目来源】**

NOIP 2001 提高组第三题


title: [NOIP2001 提高组] Car 的旅行路线

description:
又到暑假了，住在城市 A 的 Car 想和朋友一起去城市旅游。
她知道每个城市都有 $4$ 个飞机场，分别位于一个矩形的 $4$ 个顶点上，同一个城市中两个机场之间有一条笔直的高速铁路，第 $i$ 个城市中高速铁路的单位里程价格为 $T_i$，任意两个不同城市的机场之间均有航线，所有航线单位里程的价格均为 $t$。

![](https://cdn.luogu.com.cn/upload/image_hosting/odqxn9sz.png)

**注意**：图中并没有标出所有的铁路与航线。

那么 Car 应如何安排到城市 B 的路线才能尽可能的节省花费呢？她发现这并不是一个简单的问题，于是她来向你请教。

找出一条从城市 A 到 B 的旅游路线，出发和到达城市中的机场可以任意选取，要求总的花费最少。

inputFormat:
第一行为一个正整数 $n$，表示有 $n$ 组测试数据。

每组的第一行有 $4$ 个正整数 $S,t,A,B$。

$S$ 表示城市的个数，$t$ 表示飞机单位里程的价格，$A$，$B$ 分别为城市A，B 的序号。

接下来有 $S$ 行，其中第 $i$ 行均有 $7$ 个正整数$x_{i1},y_{i1},x_{i2},y_{i2},x_{i3},y_{i3},T_i$，这当中的 $(x_{i1},y_{i1}), (x_{i2},y_{i2}), (x_{i3},y_{i3})$，分别是第 $i$ 个城市中任意 $3$ 个机场的坐标，$T_i$ 为第 $i$ 个城市高速铁路单位里程的价格。

outputFormat:
共有 $n$ 行，每行 $1$ 个数据对应测试数据。
保留一位小数。

hint:
【数据范围】
对于 $100\%$ 的数据，$1\le n \le 10$，$1\le S \le 100$，$1\le A,B \le S$。

**【题目来源】**

NOIP 2001 提高组第四题


title: [NOIP2001 普及组] 数的计算

description:
给出正整数 $n$，要求按如下方式构造数列：

1. 只有一个数 $n$ 的数列是一个合法的数列。
2. 在一个合法的数列的末尾加入一个正整数，但是这个正整数不能超过该数列最后一项的一半，可以得到一个新的合法数列。

请你求出，一共有多少个合法的数列。两个合法数列 $a, b$ 不同当且仅当两数列长度不同或存在一个正整数 $i \leq |a|$，使得 $a_i \neq b_i$。

inputFormat: 输入只有一行一个整数，表示 $n$。

outputFormat: 输出一行一个整数，表示合法的数列个数。

hint:
### 样例 1 解释

满足条件的数列为：
- $6$
- $6, 1$
- $6, 2$
- $6, 3$
- $6, 2, 1$
- $6, 3, 1$

### 数据规模与约定

对于全部的测试点，保证 $1 \leq n \leq 10^3$。

### 说明

本题数据来源是 NOIP 2001 普及组第一题，但是原题的题面描述和数据不符，故对题面进行了修改，使之符合数据。原题面如下，谨供参考：

> 我们要求找出具有下列性质数的个数（包含输入的正整数 $n$）。
>
> 先输入一个正整数 $n$（$n \le 1000$），然后对此正整数按照如下方法进行处理：
>
> 1. 不作任何处理；
> 2. 在它的左边拼接一个正整数，但该正整数不能超过原数，或者是上一个被拼接的数的一半；
> 3. 加上数后，继续按此规则进行处理，直到不能再加正整数为止。

感谢 @[dbxxx](/user/120868) 对本题情况的反馈，原题面的问题见[本贴](https://www.luogu.com.cn/discuss/526184)。


title: [NOIP2001 普及组] 最大公约数和最小公倍数问题

description:
输入两个正整数 $x_0, y_0$，求出满足下列条件的 $P, Q$ 的个数：

1. $P,Q$ 是正整数。

2. 要求 $P, Q$ 以 $x_0$ 为最大公约数，以 $y_0$ 为最小公倍数。

试求：满足条件的所有可能的 $P, Q$ 的个数。

inputFormat: 一行两个正整数 $x_0, y_0$。

outputFormat: 一行一个数，表示求出满足条件的 $P, Q$ 的个数。


title: [NOIP2001 普及组] 求先序排列

description: 给出一棵二叉树的中序与后序排列。求出它的先序排列。（约定树结点用不同的大写字母表示，且二叉树的节点个数 $ \le 8$）。

inputFormat: 共两行，均为大写字母组成的字符串，表示一棵二叉树的中序与后序排列。

outputFormat: 共一行一个字符串，表示一棵二叉树的先序。

hint:
**【题目来源】**

NOIP 2001 普及组第三题


title: [NOIP2002 提高组] 均分纸牌

description:
有 $N$ 堆纸牌，编号分别为 $1,2,\ldots,N$。每堆上有若干张，但纸牌总数必为 $N$ 的倍数。可以在任一堆上取若干张纸牌，然后移动。

移牌规则为：在编号为 $1$ 堆上取的纸牌，只能移到编号为 $2$ 的堆上；在编号为 $N$ 的堆上取的纸牌，只能移到编号为 $N-1$ 的堆上；其他堆上取的纸牌，可以移到相邻左边或右边的堆上。

现在要求找出一种移动方法，用最少的移动次数使每堆上纸牌数都一样多。

例如 $N=4$ 时，$4$ 堆纸牌数分别为 $9,8,17,6$。

移动 $3$ 次可达到目的：

- 从第三堆取 $4$ 张牌放到第四堆，此时每堆纸牌数分别为 $9,8,13,10$。
- 从第三堆取 $3$ 张牌放到第二堆，此时每堆纸牌数分别为 $9,11,10,10$。
- 从第二堆取 $1$ 张牌放到第一堆，此时每堆纸牌数分别为  $10,10,10,10$。

inputFormat:
第一行共一个整数 $N$，表示纸牌堆数。
第二行共 $N$ 个整数 $A_1,A_2,\ldots,A_N$，表示每堆纸牌初始时的纸牌数。

outputFormat: 共一行，即所有堆均达到相等时的最少移动次数。

hint:
对于 $100\%$ 的数据，$1  \le  N  \le  100$，$1 \le  A_i  \le 10000$。

**【题目来源】**

NOIP 2002 提高组第一题


title: [NOIP2002 提高组] 字串变换

background:
本题不保证存在靠谱的多项式复杂度的做法。测试数据非常的水，各种做法都可以通过，不代表算法正确。因此本题题目和数据仅供参考。

本题为搜索题，本题不接受 hack 数据。[关于此类题目的详细内容](https://www.luogu.com.cn/paste/isdgwj5l)

description:
已知有两个字串 $A,B$ 及一组字串变换的规则（至多 $6$ 个规则），形如：

- $A_1\to B_1$。
- $A_2\to B_2$。

规则的含义为：在 $A$ 中的子串 $A_1$ 可以变换为 $ B_1$，$A_2$ 可以变换为 $B_2\cdots$。

例如：$A=\texttt{abcd}$，$B＝\texttt{xyz}$，

变换规则为：

- $\texttt{abc}\rightarrow\texttt{xu}$，$\texttt{ud}\rightarrow\texttt{y}$，$\texttt{y}\rightarrow\texttt{yz}$。

则此时，$A$ 可以经过一系列的变换变为 $B$，其变换的过程为：

- $\texttt{abcd}\rightarrow\texttt{xud}\rightarrow\texttt{xy}\rightarrow\texttt{xyz}$。

共进行了 $3$ 次变换，使得 $A$ 变换为 $B$。

inputFormat:
第一行有两个字符串 $A,B$。

接下来若干行，每行有两个字符串 $A_i,B_i$，表示一条变换规则。

outputFormat: 若在 $10$ 步（包含 $10$ 步）以内能将 $A$ 变换为 $B$，则输出最少的变换步数；否则输出 `NO ANSWER!`。

hint:
对于 $100\%$ 数据，保证所有字符串长度的上限为 $20$。

**【题目来源】**

NOIP 2002 提高组第二题


title: [NOIP2002 提高组] 自由落体

description:
在高为 $H$ 的天花板上有 $n$ 个小球，体积不计，位置分别为 $0,1,2,\cdots,n-1$。在地面上有一个小车（长为 $L$，高为 $K$，距原点距离为 $S_1$）。已知小球下落距离计算公式为 $d=0.5 \times g \times (t^2)$，其中 $g=10$，$t$ 为下落时间。地面上的小车以速度 $V$ 前进。

如下图：

![](https://cdn.luogu.com.cn/upload/image_hosting/1d177dhg.png)

小车与所有小球同时开始运动，当小球距小车的距离 $\le  0.0001$ (感谢 Silver_N 修正) 时，即认为小球被小车接受（小球落到地面后不能被接受）。

请你计算出小车能接受到多少个小球。

outputFormat: 小车能接受到的小球个数。

hint:
当球落入车的尾部时，算作落入车内。

**【题目来源】**

NOIP 2002 提高组第三题


title: [NOIP2002 提高组] 矩形覆盖

description:
在平面上有 $n$ 个点，每个点用一对整数坐标表示。例如：当 $n=4$ 时，$4$ 个点的坐标分别为：$p_1(1,1)$，$p_2(2,2)$，$p_3(3,6)$，$p_4(0,7)$，见图一。

![](https://cdn.luogu.com.cn/upload/image_hosting/dxc1c5k9.png)

这些点可以用 $k$ 个矩形全部覆盖，矩形的边平行于坐标轴。当 $k=2$ 时，可用如图二的两个矩形 $s_1,s_2$ 覆盖，$s_1,s_2$ 面积和为 $4$。问题是当 $n$ 个点坐标和 $k$ 给出后，怎样才能使得覆盖所有点的 $k$ 个矩形的面积之和为最小呢？
约定：覆盖一个点的矩形面积为 $0$；覆盖平行于坐标轴直线上点的矩形面积也为 $0$。各个矩形必须完全分开（边线与顶点也都不能重合）。

inputFormat:
第一行共两个整数 $n,k$，含义如题面所示。

接下来 $n$ 行，其中第 $i+1$ 行有两个整数 $x_i,y_i$，表示平面上第 $i$ 个点的坐标。

outputFormat: 共一行一个整数，为满足条件的最小的矩形面积之和。

hint:
对于 $100\%$ 数据，满足 $1\le n \le  50$，$1 \le k \le 4$，$0 \le x_i,y_i  \le 500$。

**【题目来源】**

NOIP 2002 提高组第四题


title: [NOIP2002 普及组] 级数求和

description:
已知：$S_n= 1+\dfrac{1}{2}+\dfrac{1}{3}+…+\dfrac{1}{n}$。显然对于任意一个整数 $k$，当 $n$ 足够大的时候，$S_n>k$。

现给出一个整数 $k$，要求计算出一个最小的 $n$，使得 $S_n>k$。

inputFormat: 一个正整数 $k$。

outputFormat: 一个正整数 $n$。

hint:
**【数据范围】**

对于 $100\%$ 的数据，$1\le k \le 15$。

**【题目来源】**

NOIP 2002 普及组第一题


title: [NOIP2002 普及组] 选数

description:
已知 $n$ 个整数 $x_1,x_2,\cdots,x_n$，以及 $1$ 个整数 $k$（$k<n$）。从 $n$ 个整数中任选 $k$ 个整数相加，可分别得到一系列的和。例如当 $n=4$，$k=3$，$4$ 个整数分别为 $3,7,12,19$ 时，可得全部的组合与它们的和为：

$3+7+12=22$

$3+7+19=29$

$7+12+19=38$

$3+12+19=34$

现在，要求你计算出和为素数共有多少种。

例如上例，只有一种的和为素数：$3+7+19=29$。

inputFormat:
第一行两个空格隔开的整数 $n,k$（$1 \le n \le 20$，$k<n$）。

第二行 $n$ 个整数，分别为 $x_1,x_2,\cdots,x_n$（$1 \le x_i \le 5\times 10^6$）。

outputFormat: 输出一个整数，表示种类数。

hint:
**【题目来源】**

NOIP 2002 普及组第二题


title: [NOIP2002 普及组] 产生数

description:
给出一个整数 $n$ 和 $k$ 个变换规则。

规则：
- 一位数可变换成另一个一位数。
- 规则的右部不能为零。

例如：$n=234,k=2$。有以下两个规则：

- $2\longrightarrow 5$。
- $3\longrightarrow 6$。

上面的整数 $234$ 经过变换后可能产生出的整数为（包括原数）:

- $234$。
- $534$。
- $264$。
- $564$。

共 $4$ 种不同的产生数。

现在给出一个整数 $n$ 和 $k$ 个规则。求出经过任意次的变换（$0$ 次或多次），能产生出多少个不同整数。

仅要求输出个数。

inputFormat:
第一行两个整数 $n,k$，含义如题面所示。

接下来 $k$ 行，每行两个整数 $x_i,y_i$，表示每条规则。

outputFormat: 共一行，输出能生成的数字个数。

hint:
对于 $100\%$ 数据，满足 $n \lt 10^{30}$，$k \le 15$。

**【题目来源】**

NOIP 2002 普及组第三题


title: [NOIP2003 提高组] 神经网络

background: 人工神经网络（Artificial Neural Network）是一种新兴的具有自我学习能力的计算系统，在模式识别、函数逼近及贷款风险评估等诸多领域有广泛的应用。对神经网络的研究一直是当今的热门方向，兰兰同学在自学了一本神经网络的入门书籍后，提出了一个简化模型，他希望你能帮助他用程序检验这个神经网络模型的实用性。

description:
在兰兰的模型中，神经网络就是一张有向图，图中的节点称为神经元，而且两个神经元之间至多有一条边相连，下图是一个神经元的例子：

![](https://cdn.luogu.com.cn/upload/image_hosting/61qm40kj.png)

神经元（编号为 $i$）

图中，$X_1 \sim X_3$ 是信息输入渠道，$Y_1 \sim Y_2$ 是信息输出渠道，$C_i$ 表示神经元目前的状态，$U_i$ 是阈值，可视为神经元的一个内在参数。

神经元按一定的顺序排列，构成整个神经网络。在兰兰的模型之中，神经网络中的神经元分为几层；称为输入层、输出层，和若干个中间层。每层神经元只向下一层的神经元输出信息，只从上一层神经元接受信息。下图是一个简单的三层神经网络的例子。

![](https://cdn.luogu.com.cn/upload/image_hosting/4xd7f8yz.png)

兰兰规定，$C_i$ 服从公式：（其中 $n$ 是网络中所有神经元的数目）

$$C_i=\left(\sum\limits_{(j,i) \in E} W_{ji}C_{j}\right)-U_{i}$$

公式中的 $W_{ji}$（可能为负值）表示连接 $j$ 号神经元和 $i$ 号神经元的边的权值。当 $C_i$ 大于 $0$ 时，该神经元处于兴奋状态，否则就处于平静状态。当神经元处于兴奋状态时，下一秒它会向其他神经元传送信号，信号的强度为 $C_i$。

如此．在输入层神经元被激发之后，整个网络系统就在信息传输的推动下进行运作。现在，给定一个神经网络，及当前输入层神经元的状态（$C_i$），要求你的程序运算出最后网络输出层的状态。

inputFormat: 输入文件第一行是两个整数 $n$（$1 \le n \le 100$）和 $p$。接下来 $n$ 行，每行 $2$ 个整数，第 $i+1$ 行是神经元 $i$ 最初状态和其阈值（$U_i$），非输入层的神经元开始时状态必然为 $0$。再下面 $p$ 行，每行有两个整数 $i,j$ 及一个整数 $W_{ij}$，表示连接神经元 $i,j$ 的边权值为 $W_{ij}$。

outputFormat:
输出文件包含若干行，每行有 $2$ 个整数，分别对应一个神经元的编号，及其最后的状态，$2$ 个整数间以空格分隔。仅输出最后状态大于 $0$ 的输出层神经元状态，并且按照编号由小到大顺序输出。

若输出层的神经元最后状态均小于等于 $0$，则输出 `NULL`。

hint:
**【题目来源】**

NOIP 2003 提高组第一题


title: [NOIP2003 提高组] 侦探推理

description:
明明同学最近迷上了侦探漫画《柯南》并沉醉于推理游戏之中，于是他召集了一群同学玩推理游戏。游戏的内容是这样的，明明的同学们先商量好由其中的一个人充当罪犯（在明明不知情的情况下），明明的任务就是找出这个罪犯。接着，明明逐个询问每一个同学，被询问者可能会说：

$$
\def\arraystretch{1.5}
\begin{array}{|l|l|}\hline
\textbf{\textsf{证词内容}} & \textbf{\textsf{证词含义}}\\\hline
\text{I am guilty.} & \text{我是罪犯。} \\\hline
\text{I am not guilty.} & \text{我不是罪犯。} \\\hline
\text{{\tt XXX} is guilty.} & \text{{\tt XXX} 是罪犯。其中 {\tt XXX} 表示某个同学的名字。} \\\hline
\text{{\tt XXX} is not guilty.} & \text{{\tt XXX} 不是罪犯。} \\\hline
\text{Today is {\tt XXX}.} &
\begin{aligned}
&\text{今天是 {\tt XXX}。其中 {\tt XXX} 表示某个星期的单词。}\\
&\text{星期只有可能是以下之一：}\\
&\texttt{Monday}, \texttt{Tuesday}, \texttt{Wednesday}, \texttt{Thursday}, \\
&\texttt{Friday}, \texttt{Saturday}, \texttt{Sunday}。
\end{aligned}
\\\hline
\end{array}$$

证词中出现的其他话，都不列入逻辑推理的内容。

明明所知道的是，他的同学中有 $N$ 个人始终说假话，其余的人始终说真。

现在，明明需要你帮助他从他同学的话中推断出谁是真正的凶手，请记住，凶手只有一个！

inputFormat:
输入由若干行组成。

第一行有三个整数，$M,N$ 和 $P$。$M$ 是参加游戏的明明的同学数，$N$ 是其中始终说谎的人数，$P$ 是证言的总数。

接下来 $M$ 行，每行是明明的一个同学的名字（英文字母组成，没有空格，全部大写）。

往后有 $P$ 行，每行开始是某个同学的名宇，紧跟着一个冒号和一个空格，后面是一句证词，符合前表中所列格式。证词每行不会超过 $250$ 个字符。

输入中不会出现连续的两个空格，而且每行开头和结尾也没有空格。

outputFormat: 如果你的程序能确定谁是罪犯，则输出他的名字；如果程序判断出不止一个人可能是罪犯，则输出 `Cannot Determine`；如果程序判断出没有人可能成为罪犯，则输出 `Impossible`。

samples:
3 1 5
MIKE
CHARLES
KATE
MIKE: I am guilty.
MIKE: Today is Sunday.
CHARLES: MIKE is guilty.
KATE: I am guilty.
KATE: How are you??

hint:
对于 $100\%$ 数据，满足 $1\le M\le 20$，$0\le N\le M$，$1\le P\le 100$。

**【题目来源】**

NOIP 2003 提高组第二题


title: [NOIP2003 提高组] 加分二叉树

description:
设一个 $n$ 个节点的二叉树 $\text{tree}$ 的中序遍历为$(1,2,3,\ldots,n)$，其中数字 $1,2,3,\ldots,n$ 为节点编号。每个节点都有一个分数（均为正整数），记第 $i$ 个节点的分数为 $d_i$，$\text{tree}$ 及它的每个子树都有一个加分，任一棵子树 $\text{subtree}$（也包含 $\text{tree}$ 本身）的加分计算方法如下：

$\text{subtree}$ 的左子树的加分 $\times$ $\text{subtree}$ 的右子树的加分 $+$ $\text{subtree}$ 的根的分数。

若某个子树为空，规定其加分为 $1$，叶子的加分就是叶节点本身的分数。不考虑它的空子树。

试求一棵符合中序遍历为 $(1,2,3,\ldots,n)$ 且加分最高的二叉树 $\text{tree}$。要求输出

1. $\text{tree}$ 的最高加分。

2. $\text{tree}$ 的前序遍历。

inputFormat:
第 $1$ 行 $1$ 个整数 $n$，为节点个数。

第 $2$ 行 $n$ 个用空格隔开的整数，为每个节点的分数

outputFormat:
第 $1$ 行 $1$ 个整数，为最高加分（$ Ans \le 4,000,000,000$）。

第 $2$ 行 $n$ 个用空格隔开的整数，为该树的前序遍历。

hint:
### 数据规模与约定

对于全部的测试点，保证 $1 \leq n< 30$，节点的分数是小于 $100$ 的正整数，答案不超过 $4 \times 10^9$。


title: [NOIP2003 提高组] 传染病控制

background:
本题是错题，后来被证明没有靠谱的多项式复杂度的做法。测试数据非常的水，各种玄学做法都可以通过，不代表算法正确。因此本题题目和数据仅供参考。

[关于此类题目的详细内容](https://www.luogu.com.cn/paste/isdgwj5l)

---

近来，一种新的传染病肆虐全球。蓬莱国也发现了零星感染者，为防止该病在蓬莱国大范围流行，该国政府决定不惜一切代价控制传染病的蔓延。不幸的是，由于人们尚未完全认识这种传染病，难以准确判别病毒携带者，更没有研制出疫苗以保护易感人群。于是，蓬莱国的疾病控制中心决定采取切断传播途径的方法控制疾病传播。经过 WHO（世界卫生组织）以及全球各国科研部门的努力，这种新兴传染病的传播途径和控制方法已经研究清楚，剩下的任务就是由你协助蓬莱国疾控中心制定一个有效的控制办法。

description:
研究表明，这种传染病的传播具有两种很特殊的性质；

第一是它的传播途径是树型的，一个人 $X$ 只可能被某个特定的人 $Y$ 感染，只要 $Y$ 不得病，或者是 $XY$ 之间的传播途径被切断，则 $X$ 就不会得病。

第二是，这种疾病的传播有周期性，在一个疾病传播周期之内，传染病将只会感染一代患者，而不会再传播给下一代。

这些性质大大减轻了蓬莱国疾病防控的压力，并且他们已经得到了国内部分易感人群的潜在传播途径图（一棵树）。但是，麻烦还没有结束。由于蓬莱国疾控中心人手不够，同时也缺乏强大的技术，以致他们在一个疾病传播周期内，只能设法切断一条传播途径，而没有被控制的传播途径就会引起更多的易感人群被感染（也就是与当前已经被感染的人有传播途径相连，且连接途径没有被切断的人群）。当不可能有健康人被感染时，疾病就中止传播。所以，蓬莱国疾控中心要制定出一个切断传播途径的顺序，以使尽量少的人被感染。

你的程序要针对给定的树，找出合适的切断顺序。

inputFormat:
输入格式：
第一行是两个整数 $n$ 和 $p$。
接下来 $p$ 行，每一行有 $2$ 个整数 $i$ 和 $j$，表示节点 $i$ 和 $j$ 间有边相连。（意即，第 $i$ 人和第 $j$ 人之间有传播途径相连）。其中节点 $1$ 是已经被感染的患者。

outputFormat: $1$ 行，总共被感染的人数。

hint:
对于 $100\%$ 的数据，$1 \leq n \leq 300$。

**【题目来源】**

NOIP 2003 提高组第四题


title: [NOIP2003 普及组] 乒乓球

background: 国际乒联现在主席沙拉拉自从上任以来就立志于推行一系列改革，以推动乒乓球运动在全球的普及。其中 $11$ 分制改革引起了很大的争议，有一部分球员因为无法适应新规则只能选择退役。华华就是其中一位，他退役之后走上了乒乓球研究工作，意图弄明白 $11$ 分制和 $21$ 分制对选手的不同影响。在开展他的研究之前，他首先需要对他多年比赛的统计数据进行一些分析，所以需要你的帮忙。

description:
华华通过以下方式进行分析，首先将比赛每个球的胜负列成一张表，然后分别计算在 $11$ 分制和 $21$ 分制下，双方的比赛结果（截至记录末尾）。

比如现在有这么一份记录，（其中 $\texttt W$ 表示华华获得一分，$\texttt L$ 表示华华对手获得一分）：

$\texttt{WWWWWWWWWWWWWWWWWWWWWWLW}$

在 $11$ 分制下，此时比赛的结果是华华第一局 $11$ 比 $0$ 获胜，第二局 $11$ 比 $0$ 获胜，正在进行第三局，当前比分 $1$ 比 $1$。而在 $21$ 分制下，此时比赛结果是华华第一局 $21$ 比 $0$ 获胜，正在进行第二局，比分 $2$ 比 $1$。如果一局比赛刚开始，则此时比分为 $0$ 比 $0$。直到分差大于或者等于 $2$，才一局结束。

你的程序就是要对于一系列比赛信息的输入（$\texttt{WL}$ 形式），输出正确的结果。

inputFormat: 每个输入文件包含若干行字符串，字符串由大写的 $\texttt W$ 、 $\texttt L$ 和 $\texttt E$ 组成。其中 $\texttt E$ 表示比赛信息结束，程序应该忽略 $\texttt E$ 之后的所有内容。

outputFormat: 输出由两部分组成，每部分有若干行，每一行对应一局比赛的比分（按比赛信息输入顺序）。其中第一部分是 $11$ 分制下的结果，第二部分是 $21$ 分制下的结果，两部分之间由一个空行分隔。

hint:
每行至多 $25$ 个字母，最多有 $2500$ 行。

（注：事实上有一个测试点有 $2501$ 行数据。）

**【题目来源】**

NOIP 2003 普及组第一题


title: [NOIP2003 普及组] 数字游戏

description:
丁丁最近沉迷于一个数字游戏之中。这个游戏看似简单，但丁丁在研究了许多天之后却发觉原来在简单的规则下想要赢得这个游戏并不那么容易。游戏是这样的，在你面前有一圈整数（一共 $n$ 个），你要按顺序将其分为 $m$ 个部分，各部分内的数字相加，相加所得的 $m$ 个结果对 $10$ 取模后再相乘，最终得到一个数 $k$。游戏的要求是使你所得的 $k$ 最大或者最小。

例如，对于下面这圈数字（$n=4$，$m=2$）：

![](https://cdn.luogu.com.cn/upload/image_hosting/gy407k49.png)

要求最小值时，$((2-1)\bmod10)\times ((4+3)\bmod10)=1\times 7=7$，要求最大值时，为 $((2+4+3)\bmod10)\times (-1\bmod10)=9\times 9=81$。特别值得注意的是，无论是负数还是正数，对 $10$ 取模的结果均为非负值。

丁丁请你编写程序帮他赢得这个游戏。

inputFormat: 输入文件第一行有两个整数，$n$ （$1\le n\le 50$） 和 $m$ （$1\le m\le 9$）。以下 $n$ 行每行有个整数，其绝对值 $\le10^4$，按顺序给出圈中的数字，首尾相接。

outputFormat: 输出文件有 $2$ 行，各包含 $1$ 个非负整数。第 $1$ 行是你程序得到的最小值，第 $2$ 行是最大值。

hint:
**【题目来源】**

NOIP 2003 普及组第二题


title: [NOIP2003 普及组] 栈

background:
栈是计算机中经典的数据结构，简单的说，栈就是限制在一端进行插入删除操作的线性表。

栈有两种最重要的操作，即 pop（从栈顶弹出一个元素）和 push（将一个元素进栈）。

栈的重要性不言自明，任何一门数据结构的课程都会介绍栈。宁宁同学在复习栈的基本概念时，想到了一个书上没有讲过的问题，而他自己无法给出答案，所以需要你的帮忙。

description:
![](https://cdn.luogu.com.cn/upload/image_hosting/5qxy9fz2.png)

宁宁考虑的是这样一个问题：一个操作数序列，$1,2,\ldots ,n$（图示为 1 到 3 的情况），栈 A 的深度大于 $n$。

现在可以进行两种操作，

1. 将一个数，从操作数序列的头端移到栈的头端（对应数据结构栈的 push 操作）
2. 将一个数，从栈的头端移到输出序列的尾端（对应数据结构栈的 pop 操作）

使用这两种操作，由一个操作数序列就可以得到一系列的输出序列，下图所示为由 `1 2 3` 生成序列 `2 3 1` 的过程。

![](https://cdn.luogu.com.cn/upload/image_hosting/8uwv2pa2.png)

（原始状态如上图所示）

你的程序将对给定的 $n$，计算并输出由操作数序列 $1,2,\ldots,n$ 经过操作可能得到的输出序列的总数。

inputFormat: 输入文件只含一个整数 $n$（$1 \leq n \leq 18$）。

outputFormat: 输出文件只有一行，即可能输出序列的总数目。

hint:
**【题目来源】**

NOIP 2003 普及组第三题


title: [NOIP2003 普及组] 麦森数

description:
形如 $2^{P}-1$ 的素数称为麦森数，这时 $P$ 一定也是个素数。但反过来不一定，即如果 $P$ 是个素数，$2^{P}-1$ 不一定也是素数。到 1998 年底，人们已找到了 37 个麦森数。最大的一个是 $P=3021377$，它有 909526 位。麦森数有许多重要应用，它与完全数密切相关。

任务：输入 $P(1000<P<3100000)$，计算 $2^{P}-1$ 的位数和最后 $500$ 位数字（用十进制高精度数表示）

outputFormat:
第一行：十进制高精度数 $2^{P}-1$ 的位数。

第 $2\sim 11$ 行：十进制高精度数 $2^{P}-1$ 的最后 $500$ 位数字。（每行输出 $50$ 位，共输出 $10$ 行，不足 $500$ 位时高位补 $0$）

不必验证 $2^{P}-1$ 与 $P$ 是否为素数。

hint:
**【题目来源】**

NOIP 2003 普及组第四题


title: [NOIP2005 普及组] 陶陶摘苹果

description:
陶陶家的院子里有一棵苹果树，每到秋天树上就会结出 $10$ 个苹果。苹果成熟的时候，陶陶就会跑去摘苹果。陶陶有个 $30$ 厘米高的板凳，当她不能直接用手摘到苹果的时候，就会踩到板凳上再试试。

现在已知 $10$ 个苹果到地面的高度，以及陶陶把手伸直的时候能够达到的最大高度，请帮陶陶算一下她能够摘到的苹果的数目。假设她碰到苹果，苹果就会掉下来。

inputFormat: 输入包括两行数据。第一行包含 $10$ 个 $100$ 到 $200$ 之间（包括 $100$ 和 $200$）的整数（以厘米为单位）分别表示 $10$ 个苹果到地面的高度，两个相邻的整数之间用一个空格隔开。第二行只包括一个 $100$ 到 $120$ 之间（包含 $100$ 和 $120$）的整数（以厘米为单位），表示陶陶把手伸直的时候能够达到的最大高度。

outputFormat: 输出包括一行，这一行只包含一个整数，表示陶陶能够摘到的苹果的数目。

hint:
**【题目来源】**

NOIP 2005 普及组第一题


title: [NOIP2005 普及组] 校门外的树

description:
某校大门外长度为 $l$ 的马路上有一排树，每两棵相邻的树之间的间隔都是 $1$ 米。我们可以把马路看成一个数轴，马路的一端在数轴 $0$ 的位置，另一端在 $l$ 的位置；数轴上的每个整数点，即 $0,1,2,\dots,l$，都种有一棵树。

由于马路上有一些区域要用来建地铁。这些区域用它们在数轴上的起始点和终止点表示。已知任一区域的起始点和终止点的坐标都是整数，区域之间可能有重合的部分。现在要把这些区域中的树（包括区域端点处的两棵树）移走。你的任务是计算将这些树都移走后，马路上还有多少棵树。

inputFormat:
第一行有两个整数，分别表示马路的长度 $l$ 和区域的数目 $m$。

接下来 $m$ 行，每行两个整数 $u, v$，表示一个区域的起始点和终止点的坐标。

outputFormat: 输出一行一个整数，表示将这些树都移走后，马路上剩余的树木数量。

hint:
**【数据范围】**

- 对于 $20\%$ 的数据，保证区域之间没有重合的部分。
- 对于 $100\%$ 的数据，保证 $1 \leq l \leq 10^4$，$1 \leq m \leq 100$，$0 \leq u \leq v \leq l$。

**【题目来源】**

NOIP 2005 普及组第二题


title: [NOIP2005 普及组] 采药

description:
辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”

如果你是辰辰，你能完成这个任务吗？

inputFormat:
第一行有 $2$ 个整数 $T$（$1 \le T \le 1000$）和 $M$（$1 \le  M \le 100$），用一个空格隔开，$T$ 代表总共能够用来采药的时间，$M$ 代表山洞里的草药的数目。

接下来的 $M$ 行每行包括两个在 $1$ 到 $100$ 之间（包括 $1$ 和 $100$）的整数，分别表示采摘某株草药的时间和这株草药的价值。

outputFormat: 输出在规定的时间内可以采到的草药的最大总价值。

hint:
**【数据范围】**

- 对于 $30\%$ 的数据，$M \le 10$；
- 对于全部的数据，$M \le 100$。

**【题目来源】**

NOIP 2005 普及组第三题


title: [NOIP2001 普及组] 装箱问题

description:
有一个箱子容量为 $V$，同时有 $n$ 个物品，每个物品有一个体积。

现在从 $n$ 个物品中，任取若干个装入箱内（也可以不取），使箱子的剩余空间最小。输出这个最小值。

inputFormat:
第一行共一个整数 $V$，表示箱子容量。

第二行共一个整数 $n$，表示物品总数。

接下来 $n$ 行，每行有一个正整数，表示第 $i$ 个物品的体积。

outputFormat: - 共一行一个整数，表示箱子最小剩余空间。

hint:
对于 $100\%$ 数据，满足 $0<n \le 30$，$1 \le V \le 20000$。

**【题目来源】**

NOIP 2001 普及组第四题


title: [NOIP2005 普及组] 循环

description:
乐乐是一个聪明而又勤奋好学的孩子。他总喜欢探求事物的规律。一天，他突然对数的正整数次幂产生了兴趣。

众所周知，$2$ 的正整数次幂最后一位数总是不断的在重复 $2,4,8,6,2,4,8,6…$ 我们说 $2$ 的正整数次幂最后一位的循环长度是 $4$（实际上 $4$ 的倍数都可以说是循环长度，但我们只考虑最小的循环长度）。类似的，其余的数字的正整数次幂最后一位数也有类似的循环现象：

$$
\def\arraystretch{1.5}
\begin{array}{c|c|c}\hline
\textbf{数字}& \textbf{循环} & \textbf{循环长度} \cr\hline\hline
2 & 2,4,8,6 & 4\cr\hline
3 & 3,9,7,1 & 4\cr\hline
4 & 4,6 & 2\cr\hline
5 & 5 &  1\cr\hline
6 & 6 & 1\cr\hline
7 & 7,9,3,1 & 4\cr\hline
8 & 8,4,2,6 & 4\cr\hline
9 & 9,1 & 2\cr\hline
\end{array}
$$

这时乐乐的问题就出来了：是不是只有最后一位才有这样的循环呢？对于一个整数 $n$ 的正整数次幂来说，它的后 $k$ 位是否会发生循环？如果循环的话，循环长度是多少呢？

注意：

1. 如果 $n$ 的某个正整数次幂的位数不足 $k$，那么不足的高位看做是 $0$。
2. 如果循环长度是 $L$，那么说明对于任意的正整数 $a$，$n$ 的 $a$ 次幂和 $a+L$ 次幂的最后 $k$ 位都相同。

inputFormat: 共一行，包含两个整数 $n$ 和 $k$。$n$ 和 $k$ 之间用一个空格隔开，表示要求 $n$ 的正整数次幂的最后 $k$ 位的循环长度。

outputFormat: 一个整数，表示循环长度。如果循环不存在，输出 $-1$。

hint:
**【数据范围】**

对于 $30 \%$ 的数据，满足 $k \le 4$；
对于$100 \%$ 的数据，满足 $1 \le n < {10}^{100}$，$1 \le k \le 100$。

**【题目来源】**

NOIP 2005 普及组第四题


title: [NOIP2005 提高组] 谁拿了最多奖学金

description:
某校的惯例是在每学期的期末考试之后发放奖学金。发放的奖学金共有五种，获取的条件各自不同：

1. 院士奖学金，每人 $8000$ 元，期末平均成绩高于 $80$ 分（$>80$），并且在本学期内发表$1$篇或$1$篇以上论文的学生均可获得；
2. 五四奖学金，每人 $4000$ 元，期末平均成绩高于 $85$ 分（$>85$），并且班级评议成绩高于 $80$ 分（$>80$）的学生均可获得；
3. 成绩优秀奖，每人 $2000$ 元，期末平均成绩高于 $90$ 分（$>90$）的学生均可获得；
4. 西部奖学金，每人 $1000$ 元，期末平均成绩高于 $85$ 分（$>85$）的西部省份学生均可获得；
5. 班级贡献奖，每人 $850$ 元，班级评议成绩高于 $80$ 分（$>80$）的学生干部均可获得；

只要符合条件就可以得奖，每项奖学金的获奖人数没有限制，每名学生也可以同时获得多项奖学金。例如姚林的期末平均成绩是 $87$ 分，班级评议成绩 $82$ 分，同时他还是一位学生干部，那么他可以同时获得五四奖学金和班级贡献奖，奖金总数是 $4850$ 元。

现在给出若干学生的相关数据，请计算哪些同学获得的奖金总数最高（假设总有同学能满足获得奖学金的条件）。

inputFormat:
第一行是$1$个整数 $N$，表示学生的总数。

接下来的 $N$ 行每行是一位学生的数据，从左向右依次是姓名，期末平均成绩，班级评议成绩，是否是学生干部，是否是西部省份学生，以及发表的论文数。姓名是由大小写英文字母组成的长度不超过 $20$ 的字符串（不含空格）；期末平均成绩和班级评议成绩都是 $0$ 到 $100$ 之间的整数（包括 $0$ 和 $100$）；是否是学生干部和是否是西部省份学生分别用 $1$ 个字符表示，$\tt Y$ 表示是，$\tt N$ 表示不是；发表的论文数是 $0$ 到 $10$ 的整数（包括 $0$ 和 $10$）。每两个相邻数据项之间用一个空格分隔。

outputFormat:
共 $3$ 行。

- 第 $1$ 行是获得最多奖金的学生的姓名。如果有两位或两位以上的学生获得的奖金最多，输出他们之中在输入文件中出现最早的学生的姓名。
- 第 $2$ 行是这名学生获得的奖金总数。
- 第 $3$ 行是这 $N$ 个学生获得的奖学金的总数。

samples:
4
YaoLin 87 82 Y N 0
ChenRuiyi 88 78 N Y 1
LiXin 92 88 N N 0
ZhangQin 83 87 Y N 1

hint:
**【数据范围】**

对于 $100\%$ 的数据，满足 $1 \le  N \le  100$。

**【题目来源】**

NOIP 2005 提高组第一题


title: [NOIP2005 提高组] 过河

description:
在河上有一座独木桥，一只青蛙想沿着独木桥从河的一侧跳到另一侧。在桥上有一些石子，青蛙很讨厌踩在这些石子上。由于桥的长度和青蛙一次跳过的距离都是正整数，我们可以把独木桥上青蛙可能到达的点看成数轴上的一串整点：$0,1,\cdots,L$（其中 $L$ 是桥的长度）。坐标为 $0$ 的点表示桥的起点，坐标为 $L$ 的点表示桥的终点。青蛙从桥的起点开始，不停的向终点方向跳跃。一次跳跃的距离是 $S$ 到 $T$ 之间的任意正整数（包括 $S,T$）。当青蛙跳到或跳过坐标为 $L$ 的点时，就算青蛙已经跳出了独木桥。

题目给出独木桥的长度 $L$，青蛙跳跃的距离范围 $S,T$，桥上石子的位置。你的任务是确定青蛙要想过河，最少需要踩到的石子数。

inputFormat:
输入共三行，

- 第一行有 $1$ 个正整数 $L$，表示独木桥的长度。
- 第二行有 $3$ 个正整数 $S,T,M$，分别表示青蛙一次跳跃的最小距离，最大距离及桥上石子的个数。
- 第三行有 $M$ 个不同的正整数分别表示这 $M$ 个石子在数轴上的位置（数据保证桥的起点和终点处没有石子）。所有相邻的整数之间用一个空格隔开。

outputFormat: 一个整数，表示青蛙过河最少需要踩到的石子数。

hint:
**【数据范围】**

- 对于 $30\%$ 的数据，$1\le L \le 10^4$；
- 对于 $100\%$ 的数据，$1\le L \le 10^9$，$1\le S\le T\le10$，$1\le M\le100$。

**【题目来源】**

NOIP 2005 提高组第二题


title: [NOIP2005 提高组] 篝火晚会

description:
佳佳刚进高中，在军训的时候，由于佳佳吃苦耐劳，很快得到了教官的赏识，成为了“小教官”。在军训结束的那天晚上，佳佳被命令组织同学们进行篝火晚会。一共有 $n$ 个同学，编号从 $1$ 到 $n$。一开始，同学们按照 $1,2,\cdots ,n$ 的顺序坐成一圈，而实际上每个人都有两个最希望相邻的同学。如何下命令调整同学的次序，形成新的一个圈，使之符合同学们的意愿，成为摆在佳佳面前的一大难题。

佳佳可向同学们下达命令，每一个命令的形式如下：

$$(b_1, b_2,... b_{m-1}, b_m)$$

这里 $m$ 的值是由佳佳决定的，每次命令 $m$ 的值都可以不同。这个命令的作用是移动编号是 $b_1,b_2,\cdots, b_m$ 的这 $m$ 个同学的位置。要求 $b_1$ 换到 $b_2$ 的位置上，$b_2$ 换到 $b_3$ 的位置上，……，要求 $b_m$ 换到 $b_1$ 的位置上。执行每个命令都需要一些代价。我们假定如果一个命令要移动 $m$ 个人的位置，那么这个命令的代价就是 $m$。我们需要佳佳用最少的总代价实现同学们的意愿，你能帮助佳佳吗？

inputFormat:
第一行是一个整数 $n$，表示一共有 $n$ 个同学。

其后 $n$ 行每行包括 $2$ 个不同的正整数，以一个空格隔开，分别表示编号是 $1$ 的同学最希望相邻的两个同学的编号，编号是 $2$  的同学最希望相邻的两个同学的编号，……，编号是$n$的同学最希望相邻的两个同学的编号。

outputFormat: 一个整数，为最小的总代价。如果无论怎么调整都不能符合每个同学的愿望，则输出 $-1$。

hint:
- 对于 $30\%$ 的数据，满足 $n \le 1000$；
- 对于 $100\%$ 的数据，满足 $3\le n  \le  50000$。

**【题目来源】**

NOIP 2005 提高组第三题


title: [NOIP2005 提高组] 等价表达式

description:
明明进了中学之后，学到了代数表达式。有一天，他碰到一个很麻烦的选择题。这个题目的题干中首先给出了一个代数表达式，然后列出了若干选项，每个选项也是一个代数表达式，题目的要求是判断选项中哪些代数表达式是和题干中的表达式等价的。

这个题目手算很麻烦，因为明明对计算机编程很感兴趣，所以他想是不是可以用计算机来解决这个问题。假设你是明明，能完成这个任务吗？

这个选择题中的每个表达式都满足下面的性质：

1. 表达式只可能包含一个变量 $\tt a$。
2. 表达式中出现的数都是正整数，而且都小于 $10000$。
3. 表达式中可以包括四种运算 `+`（加），`-`（减），`*`（乘），`^`（乘幂），以及小括号 `()`。小括号的优先级最高，其次是 `^`，然后是 `*`，最后是 `+` 和 `-`。`+` 和 `-` 的优先级是相同的。相同优先级的运算（**包括 `^` 运算**）都是**从左到右**进行。
4. 幂指数只可能是 $1$ 到 $10$ 之间的正整数（包括 $1$ 和 $10$）。
5. 表达式内部，头部或者尾部都可能有一些多余的空格。

下面是一些合理的表达式的例子：

`((a^1) ^ 2)^3`，`a*a+a-a`，`((a+a))`，`9999+(a-a)*a`，`1 + (a -1)^3`，`1^10^9`

inputFormat:
第一行给出的是题干中的表达式。

第二行是一个整数 $n$，表示选项的个数。后面$n$行，每行包括一个选项中的表达式。这 $n$ 个选项的标号分别是 $A,B,C,D\cdots $

输入中的表达式的长度都不超过 $50$ 个字符，而且保证选项中总有表达式和题干中的表达式是等价的。

outputFormat: 一行，包括一系列选项的标号，表示哪些选项是和题干中的表达式等价的。选项的标号按照字母顺序排列，而且之间没有空格。

hint:
- 对于 $30\%$ 的数据，表达式中只可能出现两种运算符 `+` 和 `-`；
- 对于其它的数据，四种运算符 `+-*^` 在表达式中都可能出现。
- 对于 $100\%$ 的数据，表达式中都可能出现小括号 `()`，$2 \le n \le  26$。

**【题目来源】**

NOIP 2005 提高组第四题


title: [NOIP2008 普及组] ISBN 号码

description:
每一本正式出版的图书都有一个 ISBN 号码与之对应，ISBN 码包括 $9$ 位数字、$1$ 位识别码和 $3$ 位分隔符，其规定格式如 `x-xxx-xxxxx-x`，其中符号 `-` 就是分隔符（键盘上的减号），最后一位是识别码，例如 `0-670-82162-4`就是一个标准的 ISBN 码。ISBN 码的首位数字表示书籍的出版语言，例如 $0$ 代表英语；第一个分隔符 `-` 之后的三位数字代表出版社，例如 $670$ 代表维京出版社；第二个分隔符后的五位数字代表该书在该出版社的编号；最后一位为识别码。

识别码的计算方法如下：

首位数字乘以 $1$ 加上次位数字乘以 $2$ ……以此类推，用所得的结果 $ \bmod 11$，所得的余数即为识别码，如果余数为 $10$，则识别码为大写字母 $X$。例如 ISBN 号码 `0-670-82162-4` 中的识别码 $4$ 是这样得到的：对 `067082162` 这 $9$ 个数字，从左至右，分别乘以 $1,2,\dots,9$ 再求和，即 $0\times 1+6\times 2+……+2\times 9=158$，然后取 $158 \bmod 11$ 的结果 $4$ 作为识别码。

你的任务是编写程序判断输入的 ISBN 号码中识别码是否正确，如果正确，则仅输出 `Right`；如果错误，则输出你认为是正确的 ISBN 号码。

inputFormat: 一个字符序列，表示一本书的 ISBN 号码（保证输入符合 ISBN 号码的格式要求）。

outputFormat: 一行，假如输入的 ISBN 号码的识别码正确，那么输出 `Right`，否则，按照规定的格式，输出正确的 ISBN 号码（包括分隔符 `-`）。

hint: 2008 普及组第一题


title: [NOIP2008 普及组] 排座椅

description:
上课的时候总会有一些同学和前后左右的人交头接耳，这是令小学班主任十分头疼的一件事情。不过，班主任小雪发现了一些有趣的现象，当同学们的座次确定下来之后，只有有限的 $D$ 对同学上课时会交头接耳。

同学们在教室中坐成了 $M$ 行 $N$ 列，坐在第 $i$ 行第 $j$ 列的同学的位置是 $(i,j)$，为了方便同学们进出，在教室中设置了 $K$ 条横向的通道，$L$ 条纵向的通道。

于是，聪明的小雪想到了一个办法，或许可以减少上课时学生交头接耳的问题：她打算重新摆放桌椅，改变同学们桌椅间通道的位置，因为如果一条通道隔开了 $2$ 个会交头接耳的同学，那么他们就不会交头接耳了。

请你帮忙给小雪编写一个程序，给出最好的通道划分方案。在该方案下，上课时交头接耳的学生的对数最少。

inputFormat:
第一行，有 $5$ 个用空格隔开的整数，分别是 $M,N,K,L,D(2 \le N,M \le 1000,0 \le K<M,0 \le L<N,D \le 2000)$。

接下来的 $D$ 行，每行有 $4$ 个用空格隔开的整数。第 $i$ 行的 $4$ 个整数 $X_i,Y_i,P_i,Q_i$，表示坐在位置 $(X_i,Y_i)$ 与 $(P_i,Q_i)$ 的两个同学会交头接耳（输入保证他们前后相邻或者左右相邻）。

输入数据保证最优方案的唯一性。

outputFormat:
共两行。
第一行包含 $K$ 个整数 $a_1,a_2,\ldots,a_K$，表示第 $a_1$ 行和 $a_1+1$ 行之间、第 $a_2$ 行和 $a_2+1$ 行之间、…、第 $a_K$ 行和第 $a_K+1$ 行之间要开辟通道，其中 $a_i< a_{i+1}$，每两个整数之间用空格隔开（行尾没有空格）。

第二行包含 $L$ 个整数 $b_1,b_2,\ldots,b_L$，表示第 $b_1$ 列和 $b_1+1$ 列之间、第 $b_2$ 列和 $b_2+1$ 列之间、…、第 $b_L$ 列和第 $b_L+1$ 列之间要开辟通道，其中$b_i< b_{i+1}$，每两个整数之间用空格隔开（列尾没有空格）。

hint:
![](https://cdn.luogu.com.cn/upload/image_hosting/0z0p5x1i.png)

上图中用符号\*、※、+标出了 $3$ 对会交头接耳的学生的位置，图中 $3$ 条粗线的位置表示通道，图示的通道划分方案是唯一的最佳方案。

2008 年普及组第二题


title: [NOIP2008 普及组] 传球游戏

description:
上体育课的时候，小蛮的老师经常带着同学们一起做游戏。这次，老师带着同学们一起做传球游戏。

游戏规则是这样的：$n$ 个同学站成一个圆圈，其中的一个同学手里拿着一个球，当老师吹哨子时开始传球，每个同学可以把球传给自己左右的两个同学中的一个（左右任意），当老师再次吹哨子时，传球停止，此时，拿着球没有传出去的那个同学就是败者，要给大家表演一个节目。

聪明的小蛮提出一个有趣的问题：有多少种不同的传球方法可以使得从小蛮手里开始传的球，传了 $m$ 次以后，又回到小蛮手里。两种传球方法被视作不同的方法，当且仅当这两种方法中，接到球的同学按接球顺序组成的序列是不同的。比如有三个同学 $1$ 号、$2$ 号、$3$ 号，并假设小蛮为 $1$ 号，球传了 $3$ 次回到小蛮手里的方式有 $1 \rightarrow 2 \rightarrow 3 \rightarrow 1$ 和 $1 \rightarrow 3 \rightarrow 2 \rightarrow 1$，共 $2$ 种。

inputFormat: 一行，有两个用空格隔开的整数 $n,m(3 \le n \le 30,1 \le m \le 30)$。

outputFormat: $1$ 个整数，表示符合题意的方法数。

hint:
### 数据范围及约定

- 对于 $40\%$ 的数据，满足：$3 \le n \le 30,1 \le m \le 20$；
- 对于 $100\%$ 的数据，满足：$3 \le n \le 30,1 \le m \le 30$。

2008普及组第三题


title: [NOIP2008 普及组] 立体图

description:
小渊是个聪明的孩子，他经常会给周围的小朋友们讲些自己认为有趣的内容。最近，他准备给小朋友们讲解立体图，请你帮他画出立体图。

小渊有一块面积为 $m \times n$ 的矩形区域，上面有 $m \times n$ 个边长为 $1$ 的格子，每个格子上堆了一些同样大小的积木（积木的长宽高都是 $1$），小渊想请你打印出这些格子的立体图。我们定义每个积木为如下格式，并且不会做任何翻转旋转，只会严格以这一种形式摆放：

$$
\def\arraystretch{1e-10}
\begin{aligned}
&\verb!  +---+!\\
&\verb! /   /|!\\
&\verb!+---+ |!\quad\textsf{高}\\
&\verb!|   | +!\\
&\verb!|   |/ !\quad\textsf{宽}\\
&\verb!+---+  !\\
& \quad\textsf{长}
\end{aligned}$$

每个顶点用 $1$ 个加号 `+` 表示，长用 $3$ 个 `-` 表示，宽用 $1$ 个 `/`，高用两个 `|` 表示。字符 `+`，`-`，`/`，`|` 的 ASCII 码分别为 $43$，$45$，$47$，$124$。字符 `.`（ASCII 码 $46$）需要作为背景输出，即立体图里的空白部分需要用 `.` 来代替。立体图的画法如下面的规则：

若两块积木左右相邻，图示为：

$$
\def\arraystretch{1e-10}
\begin{aligned}
\verb!..+---+---+!\\
\verb!./   /   /|!\\
\verb!+---+---+ |!\\
\verb!|   |   | +!\\
\verb!|   |   |/.!\\
\verb!+---+---+..!\\
\end{aligned}
$$

若两块积木上下相邻，图示为：

$$
\def\arraystretch{1e-10}
\begin{aligned}
\verb!..+---+!\\
\verb!./   /|!\\
\verb!+---+ |!\\
\verb!|   | +!\\
\verb!|   |/|!\\
\verb!+---+ |!\\
\verb!|   | +!\\
\verb!|   |/.!\\
\verb!+---+..!\\
\end{aligned}
$$

若两块积木前后相邻，图示为：

$$
\def\arraystretch{1e-10}
\begin{aligned}
\verb!....+---+!\\
\verb!.../   /|!\\
\verb!..+---+ |!\\
\verb!./   /| +!\\
\verb!+---+ |/.!\\
\verb!|   | +..!\\
\verb!|   |/...!\\
\verb!+---+....!\\
\end{aligned}
$$

立体图中，定义位于第 $(m,1)$ 的格子（即第 $m$ 行第 $1$ 列的格子）上面自底向上的第一块积木（即最下面的一块积木）的左下角顶点为整张图最左下角的点。

inputFormat:
第一行有用空格隔开的$2$个整数 $m$ 和 $n$，表示有 $m \times n$ 个格子 $(1 \le m,n \le 50)$。

接下来的 $m$ 行，是一个 $m \times n$ 的矩阵，每行有 $n$ 个用空格隔开的整数，其中第 $i$ 行第 $j$ 列上的整数表示第 $i$ 行第 $j$ 列的格子上摞有多少个积木（$1 \le $ 每个格子上的积木数 $ \le 100$）。

outputFormat: 输出包含题目要求的立体图，是一个 $K$ 行 $L$ 列的字符串矩阵，其中 $K$ 和 $L$ 表示最少需要 $K$ 行 $L$ 列才能按规定输出立体图。


title: [NOIP2006 普及组] 明明的随机数

description: 明明想在学校中请一些同学一起做一项问卷调查，为了实验的客观性，他先用计算机生成了 $N$ 个 $1$ 到 $1000$ 之间的随机整数 $(N\leq100)$，对于其中重复的数字，只保留一个，把其余相同的数去掉，不同的数对应着不同的学生的学号。然后再把这些数从小到大排序，按照排好的顺序去找同学做调查。请你协助明明完成“去重”与“排序”的工作。

inputFormat:
输入有两行，第 $1$ 行为 $1$ 个正整数，表示所生成的随机数的个数 $N$。

第 $2$ 行有 $N$ 个用空格隔开的正整数，为所产生的随机数。

outputFormat:
输出也是两行，第 $1$ 行为 $1$ 个正整数 $M$，表示不相同的随机数的个数。

第 $2$ 行为 $M$ 个用空格隔开的正整数，为从小到大排好序的不相同的随机数。

hint: NOIP 2006 普及组 第一题


title: [NOIP2006 普及组] 开心的金明

description:
金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间他自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过 $N$ 元钱就行”。今天一早金明就开始做预算，但是他想买的东西太多了，肯定会超过妈妈限定的 $N$ 元。于是，他把每件物品规定了一个重要度，分为 $5$ 等：用整数 $1-5$ 表示，第 $5$ 等最重要。他还从因特网上查到了每件物品的价格（都是整数元）。他希望在不超过 $N$ 元（可以等于 $N$ 元）的前提下，使每件物品的价格与重要度的乘积的总和最大。

设第$j$件物品的价格为 $v_j$，重要度为 $w_j$，共选中了 $k$ 件物品，编号依次为 $j_1,j_2,…,j_k$，则所求的总和为：

$$v_{j_1} \times w_{j_1}+v_{j_2} \times w_{j_2} …+v_{j_k} \times w_{j_k}$$

请你帮助金明设计一个满足要求的购物单。

inputFormat:
第一行，为 $2$ 个正整数，用一个空格隔开：$n,m$（$n<30000,m<25$）其中 $n$ 表示总钱数，$m$ 为希望购买物品的个数。

从第 $2$ 行到第 $m+1$ 行，第 $j$ 行给出了编号为 $j-1$ 的物品的基本数据，每行有 $2$ 个非负整数 $v,p$（其中 $v$ 表示该物品的价格 $(v \le 10000)$，$p$ 表示该物品的重要度（$1\le p\le5$）。

outputFormat: $1$ 个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的最大值（$<100000000$）。

hint: NOIP 2006 普及组 第二题


title: [NOIP2006 普及组] Jam 的计数法

description:
Jam 是个喜欢标新立异的科学怪人。他不使用阿拉伯数字计数，而是使用小写英文字母计数，他觉得这样做，会使世界更加丰富多彩。

在他的计数法中，每个数字的位数都是相同的（使用相同个数的字母），英文字母按原先的顺序，排在前面的字母小于排在它后面的字母。我们把这样的“数字”称为 Jam 数字。在 Jam 数字中，每个字母互不相同，而且从左到右是严格递增的。每次，Jam 还指定使用字母的范围，例如，从 $2\sim 10$，表示只能使用 ${b,c,d,e,f,g,h,i,j}$ 这些字母。如果再规定位数为 $5$，那么，紧接在 Jam 数字 $\texttt{bdfij}$ 之后的数字应该是 $\texttt{bdghi}$。（如果我们用 $U$、$V$ 依次表示 Jam 数字 $\texttt{bdfij}$ 与 $\texttt{bdghi}$，则 $U<V$，且不存在 Jam 数字 $P$，使 $U<P<V$）。

你的任务是：对于从文件读入的一个 Jam 数字，按顺序输出紧接在后面的 $5$ 个 Jam 数字，如果后面没有那么多 Jam 数字，那么有几个就输出几个。

inputFormat:
共 $2$ 行。

第 $1$ 行为 $3$ 个正整数 $s, t, w$，用一个空格隔开。

（其中 $s$ 为所使用的最小的字母的序号，$t$ 为所使用的最大的字母的序号。$w$ 为数字的位数，这 $3$ 个数满足：$1\le s<T\le 26,2\le w\le t-s$）

第 $2$ 行为具有 $w$ 个小写字母的字符串，为一个符合要求的 Jam 数字。

所给的数据都是正确的，不必验证。

outputFormat: 最多为 $5$ 行，为紧接在输入的 Jam 数字后面的 $5$ 个 Jam 数字，如果后面没有那么多 Jam 数字，那么有几个就输出几个。每行只输出一个 Jam 数字，是由 $w$ 个小写字母组成的字符串，不要有多余的空格。

hint: NOIP 2006 普及组 第三题


title: [NOIP2006 普及组] 数列

description:
给定一个正整数 $k$（$3\leq k\leq 15$），把所有 $k$ 的方幂及所有有限个互不相等的 $k$ 的方幂之和构成一个递增的序列，例如，当 $k = 3$ 时，这个序列是：

$1, 3, 4, 9, 10, 12, 13, \ldots$

（该序列实际上就是：$3^0,3^1,3^0+3^1,3^2,3^0+3^2,3^1+3^2,3^0+3^1+3^2,…$）

请你求出这个序列的第 $N$ 项的值，用 $10$ 进制数表示。

例如，对于 $k = 3$，$N = 100$，正确答案应该是 $981$。

inputFormat: 两个由空格隔开的正整数 $k, N$（$3\leq k\leq 15$，$10\leq N\leq 1000$）。

outputFormat: 一个正整数。整数前不要有空格和其他符号。

hint: NOIP 2006 普及组 第四题


title: [NOIP2006 提高组] 能量项链

description:
在 Mars 星球上，每个 Mars 人都随身佩带着一串能量项链。在项链上有 $N$ 颗能量珠。能量珠是一颗有头标记与尾标记的珠子，这些标记对应着某个正整数。并且，对于相邻的两颗珠子，前一颗珠子的尾标记一定等于后一颗珠子的头标记。因为只有这样，通过吸盘（吸盘是 Mars 人吸收能量的一种器官）的作用，这两颗珠子才能聚合成一颗珠子，同时释放出可以被吸盘吸收的能量。如果前一颗能量珠的头标记为 $m$，尾标记为 $r$，后一颗能量珠的头标记为 $r$，尾标记为 $n$，则聚合后释放的能量为 $m \times r \times n$（Mars 单位），新产生的珠子的头标记为 $m$，尾标记为 $n$。

需要时，Mars 人就用吸盘夹住相邻的两颗珠子，通过聚合得到能量，直到项链上只剩下一颗珠子为止。显然，不同的聚合顺序得到的总能量是不同的，请你设计一个聚合顺序，使一串项链释放出的总能量最大。

例如：设 $N=4$，$4$ 颗珠子的头标记与尾标记依次为 $(2,3)(3,5)(5,10)(10,2)$。我们用记号 $\oplus$ 表示两颗珠子的聚合操作，$(j \oplus k)$ 表示第 $j,k$ 两颗珠子聚合后所释放的能量。则第 $4$，$1$ 两颗珠子聚合后释放的能量为：

$(4 \oplus 1)=10 \times 2 \times 3=60$。

这一串项链可以得到最优值的一个聚合顺序所释放的总能量为：

$(((4 \oplus 1) \oplus 2) \oplus 3)=10 \times 2 \times 3+10 \times 3 \times 5+10 \times 5 \times 10=710$。

inputFormat:
第一行是一个正整数 $N$（$4 \le N \le 100$），表示项链上珠子的个数。第二行是 $N$ 个用空格隔开的正整数，所有的数均不超过 $1000$。第 $i$ 个数为第 $i$ 颗珠子的头标记（$1 \le i \le N$），当 $i<N$ 时，第 $i$ 颗珠子的尾标记应该等于第 $i+1$ 颗珠子的头标记。第 $N$ 颗珠子的尾标记应该等于第 $1$ 颗珠子的头标记。

至于珠子的顺序，你可以这样确定：将项链放到桌面上，不要出现交叉，随意指定第一颗珠子，然后按顺时针方向确定其他珠子的顺序。

outputFormat: 一个正整数 $E$（$E\le 2.1 \times 10^9$），为一个最优聚合顺序所释放的总能量。

hint: NOIP 2006 提高组 第一题


title: [NOIP2006 提高组] 金明的预算方案

description:
金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间金明自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过 $n$ 元钱就行”。今天一早，金明就开始做预算了，他把想买的物品分为两类：主件与附件，附件是从属于某个主件的，下表就是一些主件与附件的例子：

| 主件 | 附件 |
| :----------: | :----------: |
| 电脑 | 打印机，扫描仪 |
| 书柜 | 图书 |
| 书桌 | 台灯，文具 |
| 工作椅 | 无 |

如果要买归类为附件的物品，必须先买该附件所属的主件。每个主件可以有 $0$ 个、$1$ 个或 $2$ 个附件。每个附件对应一个主件，附件不再有从属于自己的附件。金明想买的东西很多，肯定会超过妈妈限定的 $n$ 元。于是，他把每件物品规定了一个重要度，分为 $5$ 等：用整数 $1 \sim 5$ 表示，第 $5$ 等最重要。他还从因特网上查到了每件物品的价格（都是 $10$ 元的整数倍）。他希望在不超过 $n$ 元的前提下，使每件物品的价格与重要度的乘积的总和最大。

设第 $j$ 件物品的价格为 $v_j$，重要度为 $w_j$，共选中了 $k$ 件物品，编号依次为 $j_1,j_2,\dots,j_k$，则所求的总和为：

$$v_{j_1} \times w_{j_1}+v_{j_2} \times w_{j_2}+ \dots +v_{j_k} \times w_{j_k}$$

请你帮助金明设计一个满足要求的购物单。

inputFormat:
第一行有两个整数，分别表示总钱数 $n$ 和希望购买的物品个数 $m$。

第 $2$ 到第 $(m + 1)$ 行，每行三个整数，第 $(i + 1)$ 行的整数 $v_i$，$p_i$，$q_i$ 分别表示第 $i$ 件物品的价格、重要度以及它对应的的主件。如果 $q_i=0$，表示该物品本身是主件。

outputFormat: 输出一行一个整数表示答案。

hint:
#### 数据规模与约定

对于全部的测试点，保证 $1 \leq n \leq 3.2 \times 10^4$，$1 \leq m \leq 60$，$0 \leq v_i \leq 10^4$，$1 \leq p_i \leq 5$，$0 \leq q_i \leq m$，答案不超过 $2 \times 10^5$。

NOIP 2006 提高组 第二题


title: [NOIP2006 提高组] 作业调度方案

description:
我们现在要利用 $m$ 台机器加工 $n$ 个工件，每个工件都有 $m$ 道工序，每道工序都在不同的指定的机器上完成。每个工件的每道工序都有指定的加工时间。

每个工件的每个工序称为一个操作，我们用记号 `j-k` 表示一个操作，其中 $j$ 为 $1$ 到 $n$ 中的某个数字，为工件号；$k$ 为 $1$ 到 $m$ 中的某个数字，为工序号，例如 `2-4` 表示第 $2$ 个工件第 $4$ 道工序的这个操作。在本题中，我们还给定对于各操作的一个安排顺序。

例如，当 $n=3,m=2$ 时，`1-1,1-2,2-1,3-1,3-2,2-2` 就是一个给定的安排顺序，即先安排第 $1$ 个工件的第 $1$ 个工序，再安排第 $1$ 个工件的第 $2$ 个工序，然后再安排第 $2$ 个工件的第 $1$ 个工序，等等。

一方面，每个操作的安排都要满足以下的两个约束条件。

1. 对同一个工件，每道工序必须在它前面的工序完成后才能开始；

2. 同一时刻每一台机器至多只能加工一个工件。

另一方面，在安排后面的操作时，不能改动前面已安排的操作的工作状态。

由于同一工件都是按工序的顺序安排的，因此，只按原顺序给出工件号，仍可得到同样的安排顺序，于是，在输入数据中，我们将这个安排顺序简写为 `1 1 2 3 3 2`。

还要注意，“安排顺序”只要求按照给定的顺序安排每个操作。不一定是各机器上的实际操作顺序。在具体实施时，有可能排在后面的某个操作比前面的某个操作先完成。

例如，取 $n=3,m=2$，已知数据如下（机器号/加工时间）：

工件号 |工序 1 | 工序 2
-|-|-
$1$  |  $1/3$  |  $2/2$
$2$  |  $1/2$  |  $2/5$
$3$  |  $2/2$  |  $1/4$

则对于安排顺序 `1 1 2 3 3 2`，下图中的两个实施方案都是正确的。但所需要的总时间分别是 $10$ 与 $12$。

方案 1，用时 $10$：

|      时间       |   1   |   2   |   3   |   4   |   5   |   6   |   7   |   8   |   9   |  10   |
| :-------------: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: |
| 机器 1 执行工序 | `1-1` | `1-1` | `1-1` | `2-1` | `2-1` | `3-2` | `3-2` | `3-2` | `3-2` |  无   |
| 机器 2 执行工序 | `3-1` | `3-1` |  无   | `1-2` | `1-2` | `2-2` | `2-2` | `2-2` | `2-2` | `2-2` |

方案 2，用时 $12$：

|      时间       |   1   |   2   |   3   |   4   |   5   |   6   |   7   |   8   |   9   |  10   |  11   |  12  |
| :-------------: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: |
| 机器 1 执行工序 | `1-1` | `1-1` | `1-1` | `2-1` | `2-1` |   无   |  无   | `3-2` | `3-2` | `3-2` | `3-2` |  无   |
| 机器 2 执行工序 | 无 | 无 |  无   | `1-2` | `1-2` | `3-1` | `3-1` | `2-2` | `2-2` | `2-2` | `2-2` | `2-2` |

当一个操作插入到某台机器的某个空档时（机器上最后的尚未安排操作的部分也可以看作一个空档），可以靠前插入，也可以靠后或居中插入。为了使问题简单一些，我们约定：在保证约束条件 $(1.)(2.)$ 的条件下，尽量靠前插入。并且，我们还约定，如果有多个空档可以插入，就在保证约束条件 $(1.)(2.)$ 的条件下，插入到最前面的一个空档。于是，在这些约定下，上例中的方案一是正确的，而方案二是不正确的。

显然，在这些约定下，对于给定的安排顺序，符合该安排顺序的实施方案是唯一的，请你计算出该方案完成全部任务所需的总时间。

inputFormat:
第 $1$ 行为两个正整数 $m$, $n$，用一个空格隔开，
其中 $m(<20)$ 表示机器数，$n(<20)$ 表示工件数。

第 $2$ 行：$m \times n$ 个用空格隔开的数，为给定的安排顺序。

接下来的 $2n$ 行，每行都是用空格隔开的 $m$ 个正整数，每个数不超过 $20$。

其中前 $n$ 行依次表示每个工件的每个工序所使用的机器号，第 $1$ 个数为第 $1$ 个工序的机器号，第 $2$ 个数为第 $2$ 个工序机器号，等等。

后 $n$ 行依次表示每个工件的每个工序的加工时间。

可以保证，以上各数据都是正确的，不必检验。

outputFormat: $1$ 个正整数，为最少的加工时间。

hint: NOIP 2006 提高组 第三题


title: [NOIP2006 提高组] 2^k进制数

description:
设 $r$ 是个 $2^k$ 进制数，并满足以下条件：

- $r$ 至少是个 $2$ 位的 $2^k$ 进制数。

- 作为 $2^k$ 进制数，除最后一位外，$r$ 的每一位严格小于它右边相邻的那一位。

- 将 $r$ 转换为二进制数 $q$ 后，则 $q$ 的总位数不超过 $w$。

在这里，正整数 $k,w$ 是事先给定的。

问：满足上述条件的不同的 $r$ 共有多少个？

我们再从另一角度作些解释：设 $S$ 是长度为 $w$ 的 $01$ 字符串（即字符串 $S$ 由 $w$ 个 $0$ 或 $1$ 组成），$S$ 对应于上述条件三中的 $q$。将 $S$ 从右起划分为若干个长度为 $k$ 的段，每段对应一位 $2^k$ 进制的数，如果 $S$ 至少可分成 $2$ 段，则 $S$ 所对应的二进制数又可以转换为上述的 $2^k$ 进制数 $r$。

例：设 $k=3,w=7$。则 $r$ 是个八进制数（ $2^3=8$ ）。由于 $w=7$，长度为 $7$ 的 $01$ 字符串按 $3$ 位一段分，可分为 $3$ 段（即 $1,3,3$，左边第一段只有一个二进制位），则满足条件的八进制数有：

$2$ 位数：
高位为 $1$：$6$ 个（即 $12,13,14,15,16,17$ ）,
高位为 $2$：$5$ 个，
…，
高位为 $6$：$1$ 个（即 $67$ ）。
共 $6+5+…+1=21$ 个。

$3$ 位数：
高位只能是 $1$，
第 $2$ 位为 $2$：$5$ 个（即 $123,124,125,126,127$ ），
第 $2$ 位为 $3$：$4$ 个，
…，
第 $2$ 位为 $6$：$1$ 个（即 $167$ ）。
共 $5+4+…+1=15$ 个。

所以，满足要求的 $r$ 共有 $36$ 个。

inputFormat: 一行两个正整数 $k,w$ 用一个空格隔开：

outputFormat:
一行一个个正整数，为所求的计算结果。
即满足条件的不同的 $r$ 的个数（用十进制数表示），要求不得有前导零，各数字之间不得插入数字以外的其他字符（例如空格、换行符、逗号等）。

（提示：作为结果的正整数可能很大，但不会超过 $200$ 位）

hint:
【数据范围】
$1\le k \le 9$
$1\le w \le 3\times 10^4$

NOIP 2006 提高组 第四题


title: [NOIP2009 普及组] 多项式输出

description:
一元 $n$ 次多项式可用如下的表达式表示：

$$f(x)=a_nx^n+a_{n-1}x^{n-1}+\cdots +a_1x+a_0,a_n\ne 0$$

其中，$a_ix^i$ 称为 $i$ 次项，$a_i$ 称为 $i$ 次项的系数。给出一个一元多项式各项的次数和系数，请按照如下规定的格式要求输出该多项式：

1. 多项式中自变量为 $x$，从左到右按照次数递减顺序给出多项式。

2. 多项式中只包含系数不为 $0$ 的项。

3. 如果多项式 $n$ 次项系数为正，则多项式开头不出 `+` 号，如果多项式 $n$ 次项系数为负，则多项式以 `-` 号开头。

4. 对于不是最高次的项，以 `+` 号或者 `-` 号连接此项与前一项，分别表示此项系数为正或者系数为负。紧跟一个正整数，表示此项系数的绝对值（如果一个高于 $0$ 次的项，其系数的绝对值为 $1$，则无需输出 $1$）。如果 $x$ 的指数大于 $1$，则接下来紧跟的指数部分的形式为“$x^b$”，其中 $b$ 为 $x$ 的指数；如果 $x$ 的指数为 $1$，则接下来紧跟的指数部分形式为 $x$；如果 $x$ 的指数为 $0$，则仅需输出系数即可。

5. 多项式中，多项式的开头、结尾不含多余的空格。

inputFormat:
输入共有 $2$ 行

第一行 $1$ 个整数，$n$，表示一元多项式的次数。

第二行有 $n+1$ 个整数，其中第 $i$ 个整数表示第 $n-i+1$ 次项的系数，每两个整数之间用空格隔开。

outputFormat: 输出共 $1$ 行，按题目所述格式输出多项式。

hint:
NOIP 2009 普及组 第一题

对于100%数据，$0 \le n \le 100$，$-100 \le $系数$ \le 100$

---

$\text{upd 2022.8.1}$：新增加一组 Hack 数据。


title: [NOIP2009 普及组] 分数线划定

description:
世博会志愿者的选拔工作正在 A 市如火如荼的进行。为了选拔最合适的人才，A 市对所有报名的选手进行了笔试，笔试分数达到面试分数线的选手方可进入面试。面试分数线根据计划录取人数的 $150\%$ 划定，即如果计划录取 $m$ 名志愿者，则面试分数线为排名第 $m \times 150\%$（向下取整）名的选手的分数，而最终进入面试的选手为笔试成绩不低于面试分数线的所有选手。

现在就请你编写程序划定面试分数线，并输出所有进入面试的选手的报名号和笔试成绩。

inputFormat:
第一行，两个整数 $n,m(5 \leq n \leq 5000,3 \leq m \leq n)$，中间用一个空格隔开，其中 $n$ 表示报名参加笔试的选手总数，$m$ 表示计划录取的志愿者人数。输入数据保证 $m \times 150\%$ 向下取整后小于等于 $n$。

第二行到第 $n+1$ 行，每行包括两个整数，中间用一个空格隔开，分别是选手的报名号 $k(1000 \leq k \leq 9999)$和该选手的笔试成绩 $s(1 \leq s \leq 100)$。数据保证选手的报名号各不相同。

outputFormat:
第一行，有 $2$ 个整数，用一个空格隔开，第一个整数表示面试分数线；第二个整数为进入面试的选手的实际人数。

从第二行开始，每行包含 $2$ 个整数，中间用一个空格隔开，分别表示进入面试的选手的报名号和笔试成绩，按照笔试成绩从高到低输出，如果成绩相同，则按报名号由小到大的顺序输出。

hint:
【样例说明】

$m \times 150\% = 3 \times150\% = 4.5$，向下取整后为 $4$。保证 $4$ 个人进入面试的分数线为 $88$，但因为 $88$ 有重分，所以所有成绩大于等于 $88$ 的选手都可以进入面试，故最终有 $5$ 个人进入面试。

NOIP 2009 普及组 第二题


title: [NOIP2009 普及组] 细胞分裂

description:
Hanks 博士是 BT（Bio-Tech，生物技术）领域的知名专家。现在，他正在为一个细胞实验做准备工作：培养细胞样本。

Hanks 博士手里现在有 $N$ 种细胞，编号从 $1 \sim N$，一个第 $i$ 种细胞经过 $1$ 秒钟可以分裂为 $S_i$ 个同种细胞（$S_i$ 为正整数）。现在他需要选取某种细胞的一个放进培养皿，让其自由分裂，进行培养。一段时间以后，再把培养皿中的所有细胞平均分入 $M$ 个试管，形成 $M$ 份样本，用于实验。Hanks 博士的试管数 $M$ 很大，普通的计算机的基本数据类型无法存储这样大的 $M$ 值，但万幸的是，$M$ 总可以表示为 $m_1$ 的 $m_2$ 次方，即 $M = m_1^{m_2}$，其中 $m_1,m_2$ 均为基本数据类型可以存储的正整数。

注意，整个实验过程中不允许分割单个细胞，比如某个时刻若培养皿中有 $4$ 个细胞，Hanks 博士可以把它们分入 $2$ 个试管，每试管内 $2$ 个，然后开始实验。但如果培养皿中有 $5$ 个细胞，博士就无法将它们均分入 $2$ 个试管。此时，博士就只能等待一段时间，让细胞们继续分裂，使得其个数可以均分，或是干脆改换另一种细胞培养。

为了能让实验尽早开始，Hanks 博士在选定一种细胞开始培养后，总是在得到的细胞“刚好可以平均分入 $M$ 个试管”时停止细胞培养并开始实验。现在博士希望知道，选择哪种细胞培养，可以使得实验的开始时间最早。

inputFormat:
第一行，有一个正整数 $N$，代表细胞种数。

第二行，有两个正整数 $m_1,m_2$，以一个空格隔开，即表示试管的总数 $M = m_1^{m_2}$。

第三行有 $N$ 个正整数，第 $i$ 个数 $S_i$ 表示第 $i$ 种细胞经过 $1$ 秒钟可以分裂成同种细胞的个数。

outputFormat:
一个整数，表示从开始培养细胞到实验能够开始所经过的最少时间（单位为秒）。

如果无论 Hanks 博士选择哪种细胞都不能满足要求，则输出整数 $-1$。

hint:
【输入输出样例 \#1 说明】

经过 $1$ 秒钟，细胞分裂成 $3$ 个，经过 $2$ 秒钟，细胞分裂成 $9$个，……，可以看出无论怎么分裂，细胞的个数都是奇数，因此永远不能分入 $2$ 个试管。

【输入输出样例 \#2 说明】

第 $1$ 种细胞最早在 $3$ 秒后才能均分入 $24$ 个试管，而第 $2$ 种最早在 $2$ 秒后就可以均分（每试管 $144 / {24}^1 = 6$ 个）。故实验最早可以在 $2$ 秒后开始。

【数据范围】

对于 $50 \%$ 的数据，有 $m_1^{m_2} \le 30000$。

对于所有的数据，有 $1 \le N \le 10000$，$1 \le m_1 \le 30000$，$1 \le m_2 \le 10000$，$1 \le S_i \le 2 \times {10}^9$。

NOIP 2009 普及组 第三题


title: [NOIP2009 普及组] 道路游戏

description:
小新正在玩一个简单的电脑游戏。

游戏中有一条环形马路，马路上有 $n$ 个机器人工厂，两个相邻机器人工厂之间由一小段马路连接。小新以某个机器人工厂为起点，按顺时针顺序依次将这 $n$ 个机器人工厂编号为 $1\sim n$，因为马路是环形的，所以第 $n$ 个机器人工厂和第 $1$ 个机器人工厂是由一段马路连接在一起的。小新将连接机器人工厂的这 $n$ 段马路也编号为 $1\sim n$，并规定第 $i$ 段马路连接第 $i$ 个机器人工厂和第 $i+1$ 个机器人工厂（$1\le i\le n-1$），第 $n$ 段马路连接第 $n$ 个机器人工厂和第 $1$ 个机器人工厂。

游戏过程中，每个单位时间内，每段马路上都会出现一些金币，金币的数量会随着时间发生变化，即不同单位时间内同一段马路上出现的金币数量可能是不同的。小新需要机器人的帮助才能收集到马路上的金币。所需的机器人必须在机器人工厂用一些金币来购买，机器人一旦被购买，便会沿着环形马路按顺时针方向一直行走，在每个单位时间内行走一次，即从当前所在的机器人工厂到达相邻的下一个机器人工厂，并将经过的马路上的所有金币收集给小新，例如，小新在 $i$（$1\le i\le n$）号机器人工厂购买了一个机器人，这个机器人会从 $i$ 号机器人工厂开始，顺时针在马路上行走，第一次行走会经过 $i$ 号马路，到达 $i+1$ 号机器人工厂（如果 $i=n$，机器人会到达第 $1$ 个机器人工厂），并将 $i$ 号马路上的所有金币收集给小新。游戏中，环形马路上不能同时存在 $2$ 个或者 $2$ 个以上的机器人，并且每个机器人最多能够在环形马路上行走 $p$ 次。小新购买机器人的同时，需要给这个机器人设定行走次数，行走次数可以为 $1\sim p$ 之间的任意整数。当马路上的机器人行走完规定的次数之后会自动消失，小新必须立刻在任意一个机器人工厂中购买一个新的机器人，并给新的机器人设定新的行走次数。

以下是游戏的一些补充说明：

1. 游戏从小新第一次购买机器人开始计时。
2. 购买机器人和设定机器人的行走次数是瞬间完成的，不需要花费时间。
3. 购买机器人和机器人行走是两个独立的过程，机器人行走时不能购买机器人，购买完机器人并且设定机器人行走次数之后机器人才能行走。
4. 在同一个机器人工厂购买机器人的花费是相同的，但是在不同机器人工厂购买机器人的花费不一定相同。
5. 购买机器人花费的金币，在游戏结束时再从小新收集的金币中扣除，所以在游戏过程中小新不用担心因金币不足，无法购买机器人而导致游戏无法进行。也因为如此，游戏结束后，收集的金币数量可能为负。

现在已知每段马路上每个单位时间内出现的金币数量和在每个机器人工厂购买机器人需要的花费，请你告诉小新，经过 $m$ 个单位时间后，扣除购买机器人的花费，小新最多能收集到多少金币。

inputFormat:
第一行 $3$ 个正整数 $n,m,p$，意义如题目所述。

接下来的 $n$ 行，每行有 $m$ 个正整数，每两个整数之间用一个空格隔开，其中第 $i$ 行描述了 $i$ 号马路上每个单位时间内出现的金币数量（$1\le $ 金币数量 $\le 100$），即第 $i$ 行的第 $j$（$1\le j\le m$）个数表示第 $j$ 个单位时间内 $i$ 号马路上出现的金币数量。

最后一行，有 $n$ 个整数，每两个整数之间用一个空格隔开，其中第 $i$ 个数表示在 $i$ 号机器人工厂购买机器人需要花费的金币数量（$1\le $ 金币数量 $\le 100$）。

outputFormat: 共一行，包含 $1$ 个整数，表示在 $m$ 个单位时间内，扣除购买机器人花费的金币之后，小新最多能收集到多少金币。


title: [NOIP2009 提高组] 潜伏者

description:
R 国和 S 国正陷入战火之中，双方都互派间谍，潜入对方内部，伺机行动。历尽艰险后，潜伏于 S 国的 R 国间谍小 C 终于摸清了 S 国军用密码的编码规则：

1. S 国军方内部欲发送的原信息经过加密后在网络上发送，原信息的内容与加密后所得的内容均由大写字母 $\texttt{A}\sim\texttt{Z}$ 构成（无空格等其他字符）；
2. S 国对于每个字母规定了对应的密字。加密的过程就是将原信息中的所有字母替换为其对应的密字；
3. 每个字母只对应一个唯一的密字，不同的字母对应不同的密字。密字可以和原字母相同。

例如，若规定 $\tt A$ 的密字为 $\tt A$，$\tt B$ 的密字为 $\tt C$（其他字母及密字略），则原信息 $\tt ABA$ 被加密为 $\tt ACA$。

现在，小 C 通过内线掌握了 S 国网络上发送的一条加密信息及其对应的原信息。小 C 希望能通过这条信息，破译 S 国的军用密码。小 C 的破译过程是这样的：扫描原信息，对于原信息中的字母 $x$（代表任一大写字母），找到其在加密信息中的对应大写字母 $y$，并认为在密码里 $y$ 是 $x$ 的密字。如此进行下去直到停止于如下的某个状态：

1. 所有信息扫描完毕，$\texttt{A}\sim\texttt{Z}$ 所有 $26$ 个字母在原信息中均出现过并获得了相应的密字；
2. 所有信息扫描完毕，但发现存在某个（或某些）字母在原信息中没有出现；
3. 扫描中发现掌握的信息里有明显的自相矛盾或错误（违反 S 国密码的编码规则）。

例：

如某条信息 $\tt XYZ$ 被翻译为 $\tt ABA$ 就违反了“不同字母对应不同密字”的规则。

在小 C 忙得头昏脑涨之际，R 国司令部又发来电报，要求他翻译另外一条从 S 国刚刚截取到的加密信息。现在请你帮助小 C：通过内线掌握的信息，尝试破译密码。然后利用破译的密码，翻译电报中的加密信息。

inputFormat:
共三行，每行为一个长度在 $1$ 到 $100$ 之间的字符串。

第一行，为小 C 掌握的一条加密信息；

第二行，为第一行的加密信息所对应的原信息；

第三行，为 R 国司令部要求小 C 翻译的加密信息。

输入数据保证所有字符串仅由大写字母 $\texttt{A}\sim\texttt{Z}$ 构成，且第一行长度与第二行相等。

outputFormat:
共一行。

若破译密码停止时出现 $2,3$ 两种情况，请你输出 $\tt Failed$；

否则请输出利用密码翻译电报中加密信息后得到的原信息。

hint:
【输入输出样例一说明】

原信息中的字母 $\tt A$ 和 $\tt B$ 对应相同的密字，输出 $\tt Failed$。

【输入输出样例二说明】

字母 $\tt Z$ 在原信息中没有出现，输出 $\tt Failed$。

NOIP2009 提高组第一题


title: [NOIP2009 提高组] Hankson 的趣味题

description:
Hanks 博士是 BT（Bio-Tech，生物技术) 领域的知名专家，他的儿子名叫 Hankson。现在，刚刚放学回家的 Hankson 正在思考一个有趣的问题。

今天在课堂上，老师讲解了如何求两个正整数 $c_1$ 和 $c_2$ 的最大公约数和最小公倍数。现在 Hankson 认为自己已经熟练地掌握了这些知识，他开始思考一个“求公约数”和“求公倍数”之类问题的“逆问题”，这个问题是这样的：已知正整数 $a_0,a_1,b_0,b_1$，设某未知正整数 $x$ 满足：

1. $x$ 和 $a_0$ 的最大公约数是 $a_1$；

2. $x$ 和 $b_0$ 的最小公倍数是 $b_1$。

Hankson 的“逆问题”就是求出满足条件的正整数 $x$。但稍加思索之后，他发现这样的 $x$ 并不唯一，甚至可能不存在。因此他转而开始考虑如何求解满足条件的 $x$ 的个数。请你帮助他编程求解这个问题。

inputFormat: 第一行为一个正整数 $n$，表示有 $n$ 组输入数据。接下来的$ n$ 行每行一组输入数据，为四个正整数 $a_0,a_1,b_0,b_1$，每两个整数之间用一个空格隔开。输入数据保证 $a_0$ 能被 $a_1$ 整除，$b_1$ 能被 $b_0$ 整除。

outputFormat:
共 $n$ 行。每组输入数据的输出结果占一行，为一个整数。

对于每组数据：若不存在这样的 $x$，请输出 $0$，若存在这样的 $x$，请输出满足条件的 $x$ 的个数；


title: [NOIP2009 提高组] 最优贸易

description:
$C$ 国有 $n$ 个大城市和 $m$ 条道路，每条道路连接这 $n$ 个城市中的某两个城市。任意两个城市之间最多只有一条道路直接相连。这 $m$ 条道路中有一部分为单向通行的道路，一部分为双向通行的道路，双向通行的道路在统计条数时也计为 $1$ 条。

$C$ 国幅员辽阔，各地的资源分布情况各不相同，这就导致了同一种商品在不同城市的价格不一定相同。但是，同一种商品在同一个城市的买入价和卖出价始终是相同的。

商人阿龙来到 $C$ 国旅游。当他得知同一种商品在不同城市的价格可能会不同这一信息之后，便决定在旅游的同时，利用商品在不同城市中的差价赚回一点旅费。设 $C$ 国 $n$ 个城市的标号从 $1\sim n$，阿龙决定从 $1$ 号城市出发，并最终在 $n$ 号城市结束自己的旅行。在旅游的过程中，任何城市可以重复经过多次，但不要求经过所有 $n$ 个城市。阿龙通过这样的贸易方式赚取旅费：他会选择一个经过的城市买入他最喜欢的商品――水晶球，并在之后经过的另一个城市卖出这个水晶球，用赚取的差价当做旅费。由于阿龙主要是来 $C$ 国旅游，他决定这个贸易只进行最多一次，当然，在赚不到差价的情况下他就无需进行贸易。

假设 $C$ 国有 $5$ 个大城市，城市的编号和道路连接情况如下图，单向箭头表示这条道路为单向通行，双向箭头表示这条道路为双向通行。

![](https://cdn.luogu.com.cn/upload/image_hosting/flre534z.png)

假设 $1\sim n$ 号城市的水晶球价格分别为 $4,3,5,6,1$。

阿龙可以选择如下一条线路：$1\to2\to3\to5$，并在 $2$ 号城市以 $3$ 的价格买入水晶球，在 $3$ 号城市以 $5$ 的价格卖出水晶球，赚取的旅费数为 $2$。

阿龙也可以选择如下一条线路：$1\to4\to5\to4\to5$，并在第 $1$ 次到达 $5$ 号城市时以 $1$ 的价格买入水晶球，在第 $2$ 次到达 $4$ 号城市时以 $6$ 的价格卖出水晶球，赚取的旅费数为 $5$。

现在给出 $n$ 个城市的水晶球价格，$m$ 条道路的信息（每条道路所连接的两个城市的编号以及该条道路的通行情况）。请你告诉阿龙，他最多能赚取多少旅费。

inputFormat:
第一行包含 $2$ 个正整数 $n$ 和 $m$，中间用一个空格隔开，分别表示城市的数目和道路的数目。

第二行 $n$ 个正整数，每两个整数之间用一个空格隔开，按标号顺序分别表示这 $n$ 个城市的商品价格。

接下来 $m$ 行，每行有 $3$ 个正整数 $x,y,z$，每两个整数之间用一个空格隔开。如果 $z=1$，表示这条道路是城市 $x$ 到城市 $y$ 之间的单向道路；如果 $z=2$，表示这条道路为城市 $x$ 和城市 $y$ 之间的双向道路。

outputFormat: 一个整数，表示最多能赚取的旅费。如果没有进行贸易，则输出 $0$。

hint:
【数据范围】

输入数据保证 $1$ 号城市可以到达 $n$ 号城市。

对于 $10\%$ 的数据，$1\leq n\leq 6$。

对于 $30\%$ 的数据，$1\leq n\leq 100$。

对于 $50\%$ 的数据，不存在一条旅游路线，可以从一个城市出发，再回到这个城市。

对于 $100\%$ 的数据，$1\leq n\leq 100000$，$1\leq m\leq 500000$，$1\leq  x,y\leq  n$，$1\leq  z\leq  2$，$1\leq $ 各城市的编号 $\leq  n$。

水晶球价格 $\leq 100$。

NOIP 2009 提高组 第三题


title: [NOIP2009 提高组] 靶形数独

background: **此为远古题，不保证存在可以通过任意符合要求的输入数据的程序**。

description:
小城和小华都是热爱数学的好学生，最近，他们不约而同地迷上了数独游戏，好胜的他们想用数独来一比高低。但普通的数独对他们来说都过于简单了，于是他们向 Z 博士请教，Z 博士拿出了他最近发明的“靶形数独”，作为这两个孩子比试的题目。

靶形数独的方格同普通数独一样，在 $9$ 格宽且 $9$ 格高的大九宫格中有 $9$ 个 $3$ 格宽且 $3$ 格高的小九宫格（用粗黑色线隔开的）。在这个大九宫格中，有一些数字是已知的，根据这些数字，利用逻辑推理，在其他的空格上填入 $1$ 到 $9$ 的数字。每个数字在每个小九宫格内不能重复出现，每个数字在每行、每列也不能重复出现。但靶形数独有一点和普通数独不同，即每一个方格都有一个分值，而且如同一个靶子一样，离中心越近则分值越高。（如图）

![](https://cdn.luogu.com.cn/upload/image_hosting/dhvuc32i.png)

上图具体的分值分布是：最里面一格（黄色区域）为 $10$ 分，黄色区域外面的一圈（红色区域）每个格子为 $9$ 分，再外面一圈（蓝色区域）每个格子为 $8$ 分，蓝色区域外面一圈（棕色区域）每个格子为 $7$ 分，最外面一圈（白色区域）每个格子为 $6$ 分，如上图所示。比赛的要求是：每个人必须完成一个给定的数独（每个给定数独可能有不同的填法），而且要争取更高的总分数。而这个总分数即每个方格上的分值和完成这个数独时填在相应格上的数字的乘积的总和

总分数即每个方格上的分值和完成这个数独时填在相应格上的数字的乘积的总和。如图，在以下的这个已经填完数字的靶形数独游戏中，总分数为 $2829$。游戏规定，将以总分数的高低决出胜负。

![](https://cdn.luogu.com.cn/upload/image_hosting/yx82mmnc.png)

由于求胜心切，小城找到了善于编程的你，让你帮他求出，对于给定的靶形数独，能够得到的最高分数。

inputFormat: 一共 $9$ 行。每行 $9$ 个整数（每个数都在 $0 \sim 9$ 的范围内），表示一个尚未填满的数独方格，未填的空格用“$0$”表示。每两个数字之间用一个空格隔开。

outputFormat: 输出共 $1$ 行。输出可以得到的靶形数独的最高分数。如果这个数独无解，则输出整数 $-1$。

hint:
#### 数据规模与约定

- 对于 $40\%$ 的数据，数独中非 $0$ 数的个数不少于 $30$；
- 对于 $80\%$ 的数据，数独中非 $0$ 数的个数不少于 $26$；
- 对于 $100\%$ 的数据，数独中非 $0$ 数的个数不少于 $24$。

NOIP 2009 提高组 第三题


title: [NOIP2012 普及组] 质因数分解

description: 已知正整数 $n$ 是两个不同的质数的乘积，试求出两者中较大的那个质数。

inputFormat: 输入一个正整数 $n$。

outputFormat: 输出一个正整数 $p$，即较大的那个质数。

hint:
$1 \le n\le 2\times 10^9$

NOIP 2012 普及组 第一题


title: [NOIP2012 普及组] 寻宝

description:
传说很遥远的藏宝楼顶层藏着诱人的宝藏。小明历尽千辛万苦终于找到传说中的这个藏宝楼，藏宝楼的门口竖着一个木板，上面写有几个大字：寻宝说明书。说明书的内容如下：

藏宝楼共有 $N+1$ 层，最上面一层是顶层，顶层有一个房间里面藏着宝藏。除了顶层外，藏宝楼另有 $N$ 层，每层 $M$ 个房间，这 $M$ 个房间围成一圈并按逆时针方向依次编号为 $0,…,M-1$。其中一些房间有通往上一层的楼梯，每层楼的楼梯设计可能不同。每个房间里有一个指示牌，指示牌上有一个数字$x$，表示从这个房间开始按逆时针方向选择第 $x$ 个有楼梯的房间（假定该房间的编号为 $k$），从该房间上楼，上楼后到达上一层的 $k$ 号房间。比如当前房间的指示牌上写着 $2$，则按逆时针方向开始尝试，找到第 $2$ 个有楼梯的房间，从该房间上楼。如果当前房间本身就有楼梯通向上层，该房间作为第一个有楼梯的房间。

寻宝说明书的最后用红色大号字体写着：“寻宝须知：帮助你找到每层上楼房间的指示牌上的数字（即每层第一个进入的房间内指示牌上的数字）总和为打开宝箱的密钥”。

请帮助小明算出这个打开宝箱的密钥。

inputFormat:
第一行有两个整数 $N$ 和 $M$，之间用一个空格隔开。$N$ 表示除了顶层外藏宝楼共 $N$ 层楼，$M$ 表示除顶层外每层楼有 $M$ 个房间。

接下来 $N \times M$ 行，每行两个整数，之间用一个空格隔开，每行描述一个房间内的情况，其中第 $(i-1) \times M+j$ 行表示第 $i$ 层 $j-1$ 号房间的情况（$i=1,2,…, N$；$j=1,2,…,M$）。第一个整数表示该房间是否有楼梯通往上一层（$0$ 表示没有，$1$ 表示有），第二个整数表示指示牌上的数字。注意，从$j$号房间的楼梯爬到上一层到达的房间一定也是 $j$ 号房间。

最后一行，一个整数，表示小明从藏宝楼底层的几号房间进入开始寻宝（注：房间编号从 $0$ 开始）。

outputFormat: 一个整数，表示打开宝箱的密钥，这个数可能会很大，请输出对 $20123$ 取模的结果即可。


title: [NOIP2012 普及组] 摆花

description:
小明的花店新开张，为了吸引顾客，他想在花店的门口摆上一排花，共 $m$ 盆。通过调查顾客的喜好，小明列出了顾客最喜欢的 $n$ 种花，从 $1$ 到 $n$ 标号。为了在门口展出更多种花，规定第 $i$ 种花不能超过 $a_i$ 盆，摆花时同一种花放在一起，且不同种类的花需按标号的从小到大的顺序依次摆列。

试编程计算，一共有多少种不同的摆花方案。

inputFormat:
第一行包含两个正整数 $n$ 和 $m$，中间用一个空格隔开。

第二行有 $n$ 个整数，每两个整数之间用一个空格隔开，依次表示 $a_1,a_2, \cdots ,a_n$。

outputFormat: 一个整数，表示有多少种方案。注意：因为方案数可能很多，请输出方案数对 $10^6+7$ 取模的结果。


title: [NOIP2012 普及组] 文化之旅

background:
本题**不保证**存在**可以通过满足本题数据范围的任意数据**做法。由于测试数据过水，可以通过此题的程序不一定完全正确（算法时间复杂度错误、或不保证正确性）。本题题目和数据仅供参考。本题不接受添加 hack 数据。

本题为错题。**不建议尝试或提交本题。**[关于此类题目的详细内容](https://www.luogu.com.cn/paste/isdgwj5l)

description:
有一位使者要游历各国，他每到一个国家，都能学到一种文化，但他不愿意学习任何一种文化超过一次（即如果他学习了某种文化，则他就不能到达其他有这种文化的国家）。不同的国家可能有相同的文化。不同文化的国家对其他文化的看法不同，有些文化会排斥外来文化（即如果他学习了某种文化，则他不能到达排斥这种文化的其他国家）。

现给定各个国家间的地理关系，各个国家的文化，每种文化对其他文化的看法，以及这位使者游历的起点和终点（在起点和终点也会学习当地的文化），国家间的道路距离，试求从起点到终点最少需走多少路。

inputFormat:
第一行为五个整数 $N,K,M,S,T$，每两个整数之间用一个空格隔开，依次代表国家个数（国家编号为$1$ 到 $N$），文化种数（文化编号为 $1$ 到 $K$），道路的条数，以及起点和终点的编号（保证 $S$ 不等于 $T$）；

第二行为 $N$个整数，每两个整数之间用一个空格隔开，其中第 $i$个数 $C_i$，表示国家 $i$的文化为 $C_i$。

接下来的 $K $行，每行 $K$ 个整数，每两个整数之间用一个空格隔开，记第$ i$ 行的第 j 个数为 $a_{ij}$，$a_{ij}= 1$ 表示文化 $i$ 排斥外来文化$ j$（$i$ 等于 $j$ 时表示排斥相同文化的外来人），$a_{ij}= 0$ 表示不排斥（注意 $i$ 排斥 $j$ 并不保证 $j$ 一定也排斥 $i$）。

接下来的 $M$ 行，每行三个整数 $u,v,d$，每两个整数之间用一个空格隔开，表示国家 $u$与国家 $v $有一条距离为$ d $的可双向通行的道路（保证$ u $不等于 $v$，两个国家之间可能有多条道路）。

outputFormat: 一个整数，表示使者从起点国家到达终点国家最少需要走的距离数（如果无解则输出$-1$）。

hint:
输入输出样例说明$1$

由于到国家 $2$ 必须要经过国家$ 1$，而国家$ 2 $的文明却排斥国家 $1$ 的文明，所以不可能到达国家 $2$。

输入输出样例说明$2$

路线为$ 1$ ->$ 2$

【数据范围】

对于 100%的数据，有$ 2≤N≤100$

$1≤K≤100$

$1≤M≤N^2$

$1≤k_i≤K$

$1≤u, v≤N$

$1≤d≤1000,S≠T,1≤S,T≤N$

NOIP 2012 普及组 第四题


title: [NOIP2012 提高组] Vigenère 密码

description:
16 世纪法国外交家 Blaise de Vigenère 设计了一种多表密码加密算法 Vigenère 密码。Vigenère 密码的加密解密算法简单易用，且破译难度比较高，曾在美国南北战争中为南军所广泛使用。

在密码学中，我们称需要加密的信息为明文，用 $M$ 表示；称加密后的信息为密文，用 $C$ 表示；而密钥是一种参数，是将明文转换为密文或将密文转换为明文的算法中输入的数据，记为 $k$。在 Vigenère 密码中，密钥 $k$ 是一个字母串，$k=k_1,k_2,…,k_n$。当明文 $M=m_1,m_2,…,m_n$ 时，得到的密文 $C=c_1,c_2,…,c_n$，其中 $c_i$=$m_i \operatorname{\circledR} k_i$，运算 $\circledR$ 的规则如下表所示：

$$\begin{array}{c|cccccccccccccccccccccccccc}
\circledR &\tt A \kern{-5pt} &\tt B \kern{-5pt} &\tt C \kern{-5pt} &\tt D \kern{-5pt} &\tt E \kern{-5pt} &\tt F \kern{-5pt} &\tt G \kern{-5pt} &\tt H \kern{-5pt} &\tt I \kern{-5pt} &\tt J \kern{-5pt} &\tt K \kern{-5pt} &\tt L \kern{-5pt} &\tt M \kern{-5pt} &\tt N \kern{-5pt} &\tt O \kern{-5pt} &\tt P \kern{-5pt} &\tt Q \kern{-5pt} &\tt R \kern{-5pt} &\tt S \kern{-5pt} &\tt T \kern{-5pt} &\tt U \kern{-5pt} &\tt V \kern{-5pt} &\tt W \kern{-5pt} &\tt X \kern{-5pt} &\tt Y \kern{-5pt} &\tt Z \kern{-5pt}  \\\hline
\tt A &\tt A \kern{-5pt} &\tt B \kern{-5pt} &\tt C \kern{-5pt} &\tt D \kern{-5pt} &\tt E \kern{-5pt} &\tt F \kern{-5pt} &\tt G \kern{-5pt} &\tt H \kern{-5pt} &\tt I \kern{-5pt} &\tt J \kern{-5pt} &\tt K \kern{-5pt} &\tt L \kern{-5pt} &\tt M \kern{-5pt} &\tt N \kern{-5pt} &\tt O \kern{-5pt} &\tt P \kern{-5pt} &\tt Q \kern{-5pt} &\tt R \kern{-5pt} &\tt S \kern{-5pt} &\tt T \kern{-5pt} &\tt U \kern{-5pt} &\tt V \kern{-5pt} &\tt W \kern{-5pt} &\tt X \kern{-5pt} &\tt Y \kern{-5pt} &\tt Z \kern{-5pt}  \\
\tt B &\tt B \kern{-5pt} &\tt C \kern{-5pt} &\tt D \kern{-5pt} &\tt E \kern{-5pt} &\tt F \kern{-5pt} &\tt G \kern{-5pt} &\tt H \kern{-5pt} &\tt I \kern{-5pt} &\tt J \kern{-5pt} &\tt K \kern{-5pt} &\tt L \kern{-5pt} &\tt M \kern{-5pt} &\tt N \kern{-5pt} &\tt O \kern{-5pt} &\tt P \kern{-5pt} &\tt Q \kern{-5pt} &\tt R \kern{-5pt} &\tt S \kern{-5pt} &\tt T \kern{-5pt} &\tt U \kern{-5pt} &\tt V \kern{-5pt} &\tt W \kern{-5pt} &\tt X \kern{-5pt} &\tt Y \kern{-5pt} &\tt Z \kern{-5pt} &\tt A \kern{-5pt}  \\
\tt C &\tt C \kern{-5pt} &\tt D \kern{-5pt} &\tt E \kern{-5pt} &\tt F \kern{-5pt} &\tt G \kern{-5pt} &\tt H \kern{-5pt} &\tt I \kern{-5pt} &\tt J \kern{-5pt} &\tt K \kern{-5pt} &\tt L \kern{-5pt} &\tt M \kern{-5pt} &\tt N \kern{-5pt} &\tt O \kern{-5pt} &\tt P \kern{-5pt} &\tt Q \kern{-5pt} &\tt R \kern{-5pt} &\tt S \kern{-5pt} &\tt T \kern{-5pt} &\tt U \kern{-5pt} &\tt V \kern{-5pt} &\tt W \kern{-5pt} &\tt X \kern{-5pt} &\tt Y \kern{-5pt} &\tt Z \kern{-5pt} &\tt A \kern{-5pt} &\tt B \kern{-5pt}  \\
\tt D &\tt D \kern{-5pt} &\tt E \kern{-5pt} &\tt F \kern{-5pt} &\tt G \kern{-5pt} &\tt H \kern{-5pt} &\tt I \kern{-5pt} &\tt J \kern{-5pt} &\tt K \kern{-5pt} &\tt L \kern{-5pt} &\tt M \kern{-5pt} &\tt N \kern{-5pt} &\tt O \kern{-5pt} &\tt P \kern{-5pt} &\tt Q \kern{-5pt} &\tt R \kern{-5pt} &\tt S \kern{-5pt} &\tt T \kern{-5pt} &\tt U \kern{-5pt} &\tt V \kern{-5pt} &\tt W \kern{-5pt} &\tt X \kern{-5pt} &\tt Y \kern{-5pt} &\tt Z \kern{-5pt} &\tt A \kern{-5pt} &\tt B \kern{-5pt} &\tt C \kern{-5pt}  \\
\tt E &\tt E \kern{-5pt} &\tt F \kern{-5pt} &\tt G \kern{-5pt} &\tt H \kern{-5pt} &\tt I \kern{-5pt} &\tt J \kern{-5pt} &\tt K \kern{-5pt} &\tt L \kern{-5pt} &\tt M \kern{-5pt} &\tt N \kern{-5pt} &\tt O \kern{-5pt} &\tt P \kern{-5pt} &\tt Q \kern{-5pt} &\tt R \kern{-5pt} &\tt S \kern{-5pt} &\tt T \kern{-5pt} &\tt U \kern{-5pt} &\tt V \kern{-5pt} &\tt W \kern{-5pt} &\tt X \kern{-5pt} &\tt Y \kern{-5pt} &\tt Z \kern{-5pt} &\tt A \kern{-5pt} &\tt B \kern{-5pt} &\tt C \kern{-5pt} &\tt D \kern{-5pt}  \\
\tt F &\tt F \kern{-5pt} &\tt G \kern{-5pt} &\tt H \kern{-5pt} &\tt I \kern{-5pt} &\tt J \kern{-5pt} &\tt K \kern{-5pt} &\tt L \kern{-5pt} &\tt M \kern{-5pt} &\tt N \kern{-5pt} &\tt O \kern{-5pt} &\tt P \kern{-5pt} &\tt Q \kern{-5pt} &\tt R \kern{-5pt} &\tt S \kern{-5pt} &\tt T \kern{-5pt} &\tt U \kern{-5pt} &\tt V \kern{-5pt} &\tt W \kern{-5pt} &\tt X \kern{-5pt} &\tt Y \kern{-5pt} &\tt Z \kern{-5pt} &\tt A \kern{-5pt} &\tt B \kern{-5pt} &\tt C \kern{-5pt} &\tt D \kern{-5pt} &\tt E \kern{-5pt}  \\
\tt G &\tt G \kern{-5pt} &\tt H \kern{-5pt} &\tt I \kern{-5pt} &\tt J \kern{-5pt} &\tt K \kern{-5pt} &\tt L \kern{-5pt} &\tt M \kern{-5pt} &\tt N \kern{-5pt} &\tt O \kern{-5pt} &\tt P \kern{-5pt} &\tt Q \kern{-5pt} &\tt R \kern{-5pt} &\tt S \kern{-5pt} &\tt T \kern{-5pt} &\tt U \kern{-5pt} &\tt V \kern{-5pt} &\tt W \kern{-5pt} &\tt X \kern{-5pt} &\tt Y \kern{-5pt} &\tt Z \kern{-5pt} &\tt A \kern{-5pt} &\tt B \kern{-5pt} &\tt C \kern{-5pt} &\tt D \kern{-5pt} &\tt E \kern{-5pt} &\tt F \kern{-5pt}  \\
\tt H &\tt H \kern{-5pt} &\tt I \kern{-5pt} &\tt J \kern{-5pt} &\tt K \kern{-5pt} &\tt L \kern{-5pt} &\tt M \kern{-5pt} &\tt N \kern{-5pt} &\tt O \kern{-5pt} &\tt P \kern{-5pt} &\tt Q \kern{-5pt} &\tt R \kern{-5pt} &\tt S \kern{-5pt} &\tt T \kern{-5pt} &\tt U \kern{-5pt} &\tt V \kern{-5pt} &\tt W \kern{-5pt} &\tt X \kern{-5pt} &\tt Y \kern{-5pt} &\tt Z \kern{-5pt} &\tt A \kern{-5pt} &\tt B \kern{-5pt} &\tt C \kern{-5pt} &\tt D \kern{-5pt} &\tt E \kern{-5pt} &\tt F \kern{-5pt} &\tt G \kern{-5pt}  \\
\tt I &\tt I \kern{-5pt} &\tt J \kern{-5pt} &\tt K \kern{-5pt} &\tt L \kern{-5pt} &\tt M \kern{-5pt} &\tt N \kern{-5pt} &\tt O \kern{-5pt} &\tt P \kern{-5pt} &\tt Q \kern{-5pt} &\tt R \kern{-5pt} &\tt S \kern{-5pt} &\tt T \kern{-5pt} &\tt U \kern{-5pt} &\tt V \kern{-5pt} &\tt W \kern{-5pt} &\tt X \kern{-5pt} &\tt Y \kern{-5pt} &\tt Z \kern{-5pt} &\tt A \kern{-5pt} &\tt B \kern{-5pt} &\tt C \kern{-5pt} &\tt D \kern{-5pt} &\tt E \kern{-5pt} &\tt F \kern{-5pt} &\tt G \kern{-5pt} &\tt H \kern{-5pt}  \\
\tt J &\tt J \kern{-5pt} &\tt K \kern{-5pt} &\tt L \kern{-5pt} &\tt M \kern{-5pt} &\tt N \kern{-5pt} &\tt O \kern{-5pt} &\tt P \kern{-5pt} &\tt Q \kern{-5pt} &\tt R \kern{-5pt} &\tt S \kern{-5pt} &\tt T \kern{-5pt} &\tt U \kern{-5pt} &\tt V \kern{-5pt} &\tt W \kern{-5pt} &\tt X \kern{-5pt} &\tt Y \kern{-5pt} &\tt Z \kern{-5pt} &\tt A \kern{-5pt} &\tt B \kern{-5pt} &\tt C \kern{-5pt} &\tt D \kern{-5pt} &\tt E \kern{-5pt} &\tt F \kern{-5pt} &\tt G \kern{-5pt} &\tt H \kern{-5pt} &\tt I \kern{-5pt}  \\
\tt K &\tt K \kern{-5pt} &\tt L \kern{-5pt} &\tt M \kern{-5pt} &\tt N \kern{-5pt} &\tt O \kern{-5pt} &\tt P \kern{-5pt} &\tt Q \kern{-5pt} &\tt R \kern{-5pt} &\tt S \kern{-5pt} &\tt T \kern{-5pt} &\tt U \kern{-5pt} &\tt V \kern{-5pt} &\tt W \kern{-5pt} &\tt X \kern{-5pt} &\tt Y \kern{-5pt} &\tt Z \kern{-5pt} &\tt A \kern{-5pt} &\tt B \kern{-5pt} &\tt C \kern{-5pt} &\tt D \kern{-5pt} &\tt E \kern{-5pt} &\tt F \kern{-5pt} &\tt G \kern{-5pt} &\tt H \kern{-5pt} &\tt I \kern{-5pt} &\tt J \kern{-5pt}  \\
\tt L &\tt L \kern{-5pt} &\tt M \kern{-5pt} &\tt N \kern{-5pt} &\tt O \kern{-5pt} &\tt P \kern{-5pt} &\tt Q \kern{-5pt} &\tt R \kern{-5pt} &\tt S \kern{-5pt} &\tt T \kern{-5pt} &\tt U \kern{-5pt} &\tt V \kern{-5pt} &\tt W \kern{-5pt} &\tt X \kern{-5pt} &\tt Y \kern{-5pt} &\tt Z \kern{-5pt} &\tt A \kern{-5pt} &\tt B \kern{-5pt} &\tt C \kern{-5pt} &\tt D \kern{-5pt} &\tt E \kern{-5pt} &\tt F \kern{-5pt} &\tt G \kern{-5pt} &\tt H \kern{-5pt} &\tt I \kern{-5pt} &\tt J \kern{-5pt} &\tt K \kern{-5pt}  \\
\tt M &\tt M \kern{-5pt} &\tt N \kern{-5pt} &\tt O \kern{-5pt} &\tt P \kern{-5pt} &\tt Q \kern{-5pt} &\tt R \kern{-5pt} &\tt S \kern{-5pt} &\tt T \kern{-5pt} &\tt U \kern{-5pt} &\tt V \kern{-5pt} &\tt W \kern{-5pt} &\tt X \kern{-5pt} &\tt Y \kern{-5pt} &\tt Z \kern{-5pt} &\tt A \kern{-5pt} &\tt B \kern{-5pt} &\tt C \kern{-5pt} &\tt D \kern{-5pt} &\tt E \kern{-5pt} &\tt F \kern{-5pt} &\tt G \kern{-5pt} &\tt H \kern{-5pt} &\tt I \kern{-5pt} &\tt J \kern{-5pt} &\tt K \kern{-5pt} &\tt L \kern{-5pt}  \\
\tt N &\tt N \kern{-5pt} &\tt O \kern{-5pt} &\tt P \kern{-5pt} &\tt Q \kern{-5pt} &\tt R \kern{-5pt} &\tt S \kern{-5pt} &\tt T \kern{-5pt} &\tt U \kern{-5pt} &\tt V \kern{-5pt} &\tt W \kern{-5pt} &\tt X \kern{-5pt} &\tt Y \kern{-5pt} &\tt Z \kern{-5pt} &\tt A \kern{-5pt} &\tt B \kern{-5pt} &\tt C \kern{-5pt} &\tt D \kern{-5pt} &\tt E \kern{-5pt} &\tt F \kern{-5pt} &\tt G \kern{-5pt} &\tt H \kern{-5pt} &\tt I \kern{-5pt} &\tt J \kern{-5pt} &\tt K \kern{-5pt} &\tt L \kern{-5pt} &\tt M \kern{-5pt}  \\
\tt O &\tt O \kern{-5pt} &\tt P \kern{-5pt} &\tt Q \kern{-5pt} &\tt R \kern{-5pt} &\tt S \kern{-5pt} &\tt T \kern{-5pt} &\tt U \kern{-5pt} &\tt V \kern{-5pt} &\tt W \kern{-5pt} &\tt X \kern{-5pt} &\tt Y \kern{-5pt} &\tt Z \kern{-5pt} &\tt A \kern{-5pt} &\tt B \kern{-5pt} &\tt C \kern{-5pt} &\tt D \kern{-5pt} &\tt E \kern{-5pt} &\tt F \kern{-5pt} &\tt G \kern{-5pt} &\tt H \kern{-5pt} &\tt I \kern{-5pt} &\tt J \kern{-5pt} &\tt K \kern{-5pt} &\tt L \kern{-5pt} &\tt M \kern{-5pt} &\tt N \kern{-5pt}  \\
\tt P &\tt P \kern{-5pt} &\tt Q \kern{-5pt} &\tt R \kern{-5pt} &\tt S \kern{-5pt} &\tt T \kern{-5pt} &\tt U \kern{-5pt} &\tt V \kern{-5pt} &\tt W \kern{-5pt} &\tt X \kern{-5pt} &\tt Y \kern{-5pt} &\tt Z \kern{-5pt} &\tt A \kern{-5pt} &\tt B \kern{-5pt} &\tt C \kern{-5pt} &\tt D \kern{-5pt} &\tt E \kern{-5pt} &\tt F \kern{-5pt} &\tt G \kern{-5pt} &\tt H \kern{-5pt} &\tt I \kern{-5pt} &\tt J \kern{-5pt} &\tt K \kern{-5pt} &\tt L \kern{-5pt} &\tt M \kern{-5pt} &\tt N \kern{-5pt} &\tt O \kern{-5pt}  \\
\tt Q &\tt Q \kern{-5pt} &\tt R \kern{-5pt} &\tt S \kern{-5pt} &\tt T \kern{-5pt} &\tt U \kern{-5pt} &\tt V \kern{-5pt} &\tt W \kern{-5pt} &\tt X \kern{-5pt} &\tt Y \kern{-5pt} &\tt Z \kern{-5pt} &\tt A \kern{-5pt} &\tt B \kern{-5pt} &\tt C \kern{-5pt} &\tt D \kern{-5pt} &\tt E \kern{-5pt} &\tt F \kern{-5pt} &\tt G \kern{-5pt} &\tt H \kern{-5pt} &\tt I \kern{-5pt} &\tt J \kern{-5pt} &\tt K \kern{-5pt} &\tt L \kern{-5pt} &\tt M \kern{-5pt} &\tt N \kern{-5pt} &\tt O \kern{-5pt} &\tt P \kern{-5pt}  \\
\tt R &\tt R \kern{-5pt} &\tt S \kern{-5pt} &\tt T \kern{-5pt} &\tt U \kern{-5pt} &\tt V \kern{-5pt} &\tt W \kern{-5pt} &\tt X \kern{-5pt} &\tt Y \kern{-5pt} &\tt Z \kern{-5pt} &\tt A \kern{-5pt} &\tt B \kern{-5pt} &\tt C \kern{-5pt} &\tt D \kern{-5pt} &\tt E \kern{-5pt} &\tt F \kern{-5pt} &\tt G \kern{-5pt} &\tt H \kern{-5pt} &\tt I \kern{-5pt} &\tt J \kern{-5pt} &\tt K \kern{-5pt} &\tt L \kern{-5pt} &\tt M \kern{-5pt} &\tt N \kern{-5pt} &\tt O \kern{-5pt} &\tt P \kern{-5pt} &\tt Q \kern{-5pt}  \\
\tt S &\tt S \kern{-5pt} &\tt T \kern{-5pt} &\tt U \kern{-5pt} &\tt V \kern{-5pt} &\tt W \kern{-5pt} &\tt X \kern{-5pt} &\tt Y \kern{-5pt} &\tt Z \kern{-5pt} &\tt A \kern{-5pt} &\tt B \kern{-5pt} &\tt C \kern{-5pt} &\tt D \kern{-5pt} &\tt E \kern{-5pt} &\tt F \kern{-5pt} &\tt G \kern{-5pt} &\tt H \kern{-5pt} &\tt I \kern{-5pt} &\tt J \kern{-5pt} &\tt K \kern{-5pt} &\tt L \kern{-5pt} &\tt M \kern{-5pt} &\tt N \kern{-5pt} &\tt O \kern{-5pt} &\tt P \kern{-5pt} &\tt Q \kern{-5pt} &\tt R \kern{-5pt}  \\
\tt T &\tt T \kern{-5pt} &\tt U \kern{-5pt} &\tt V \kern{-5pt} &\tt W \kern{-5pt} &\tt X \kern{-5pt} &\tt Y \kern{-5pt} &\tt Z \kern{-5pt} &\tt A \kern{-5pt} &\tt B \kern{-5pt} &\tt C \kern{-5pt} &\tt D \kern{-5pt} &\tt E \kern{-5pt} &\tt F \kern{-5pt} &\tt G \kern{-5pt} &\tt H \kern{-5pt} &\tt I \kern{-5pt} &\tt J \kern{-5pt} &\tt K \kern{-5pt} &\tt L \kern{-5pt} &\tt M \kern{-5pt} &\tt N \kern{-5pt} &\tt O \kern{-5pt} &\tt P \kern{-5pt} &\tt Q \kern{-5pt} &\tt R \kern{-5pt} &\tt S \kern{-5pt}  \\
\tt U &\tt U \kern{-5pt} &\tt V \kern{-5pt} &\tt W \kern{-5pt} &\tt X \kern{-5pt} &\tt Y \kern{-5pt} &\tt Z \kern{-5pt} &\tt A \kern{-5pt} &\tt B \kern{-5pt} &\tt C \kern{-5pt} &\tt D \kern{-5pt} &\tt E \kern{-5pt} &\tt F \kern{-5pt} &\tt G \kern{-5pt} &\tt H \kern{-5pt} &\tt I \kern{-5pt} &\tt J \kern{-5pt} &\tt K \kern{-5pt} &\tt L \kern{-5pt} &\tt M \kern{-5pt} &\tt N \kern{-5pt} &\tt O \kern{-5pt} &\tt P \kern{-5pt} &\tt Q \kern{-5pt} &\tt R \kern{-5pt} &\tt S \kern{-5pt} &\tt T \kern{-5pt}  \\
\tt V &\tt V \kern{-5pt} &\tt W \kern{-5pt} &\tt X \kern{-5pt} &\tt Y \kern{-5pt} &\tt Z \kern{-5pt} &\tt A \kern{-5pt} &\tt B \kern{-5pt} &\tt C \kern{-5pt} &\tt D \kern{-5pt} &\tt E \kern{-5pt} &\tt F \kern{-5pt} &\tt G \kern{-5pt} &\tt H \kern{-5pt} &\tt I \kern{-5pt} &\tt J \kern{-5pt} &\tt K \kern{-5pt} &\tt L \kern{-5pt} &\tt M \kern{-5pt} &\tt N \kern{-5pt} &\tt O \kern{-5pt} &\tt P \kern{-5pt} &\tt Q \kern{-5pt} &\tt R \kern{-5pt} &\tt S \kern{-5pt} &\tt T \kern{-5pt} &\tt U \kern{-5pt}  \\
\tt W &\tt W \kern{-5pt} &\tt X \kern{-5pt} &\tt Y \kern{-5pt} &\tt Z \kern{-5pt} &\tt A \kern{-5pt} &\tt B \kern{-5pt} &\tt C \kern{-5pt} &\tt D \kern{-5pt} &\tt E \kern{-5pt} &\tt F \kern{-5pt} &\tt G \kern{-5pt} &\tt H \kern{-5pt} &\tt I \kern{-5pt} &\tt J \kern{-5pt} &\tt K \kern{-5pt} &\tt L \kern{-5pt} &\tt M \kern{-5pt} &\tt N \kern{-5pt} &\tt O \kern{-5pt} &\tt P \kern{-5pt} &\tt Q \kern{-5pt} &\tt R \kern{-5pt} &\tt S \kern{-5pt} &\tt T \kern{-5pt} &\tt U \kern{-5pt} &\tt V \kern{-5pt}  \\
\tt X &\tt X \kern{-5pt} &\tt Y \kern{-5pt} &\tt Z \kern{-5pt} &\tt A \kern{-5pt} &\tt B \kern{-5pt} &\tt C \kern{-5pt} &\tt D \kern{-5pt} &\tt E \kern{-5pt} &\tt F \kern{-5pt} &\tt G \kern{-5pt} &\tt H \kern{-5pt} &\tt I \kern{-5pt} &\tt J \kern{-5pt} &\tt K \kern{-5pt} &\tt L \kern{-5pt} &\tt M \kern{-5pt} &\tt N \kern{-5pt} &\tt O \kern{-5pt} &\tt P \kern{-5pt} &\tt Q \kern{-5pt} &\tt R \kern{-5pt} &\tt S \kern{-5pt} &\tt T \kern{-5pt} &\tt U \kern{-5pt} &\tt V \kern{-5pt} &\tt W \kern{-5pt}  \\
\tt Y &\tt Y \kern{-5pt} &\tt Z \kern{-5pt} &\tt A \kern{-5pt} &\tt B \kern{-5pt} &\tt C \kern{-5pt} &\tt D \kern{-5pt} &\tt E \kern{-5pt} &\tt F \kern{-5pt} &\tt G \kern{-5pt} &\tt H \kern{-5pt} &\tt I \kern{-5pt} &\tt J \kern{-5pt} &\tt K \kern{-5pt} &\tt L \kern{-5pt} &\tt M \kern{-5pt} &\tt N \kern{-5pt} &\tt O \kern{-5pt} &\tt P \kern{-5pt} &\tt Q \kern{-5pt} &\tt R \kern{-5pt} &\tt S \kern{-5pt} &\tt T \kern{-5pt} &\tt U \kern{-5pt} &\tt V \kern{-5pt} &\tt W \kern{-5pt} &\tt X \kern{-5pt}  \\
\tt Z &\tt Z \kern{-5pt} &\tt A \kern{-5pt} &\tt B \kern{-5pt} &\tt C \kern{-5pt} &\tt D \kern{-5pt} &\tt E \kern{-5pt} &\tt F \kern{-5pt} &\tt G \kern{-5pt} &\tt H \kern{-5pt} &\tt I \kern{-5pt} &\tt J \kern{-5pt} &\tt K \kern{-5pt} &\tt L \kern{-5pt} &\tt M \kern{-5pt} &\tt N \kern{-5pt} &\tt O \kern{-5pt} &\tt P \kern{-5pt} &\tt Q \kern{-5pt} &\tt R \kern{-5pt} &\tt S \kern{-5pt} &\tt T \kern{-5pt} &\tt U \kern{-5pt} &\tt V \kern{-5pt} &\tt W \kern{-5pt} &\tt X \kern{-5pt} &\tt Y \kern{-5pt}  \\

\end{array}
$$

Vigenère 加密在操作时需要注意：

1. $\circledR$ 运算忽略参与运算的字母的大小写，并保持字母在明文 $M$ 中的大小写形式；
2. 当明文 $M$ 的长度大于密钥 $k$ 的长度时，将密钥 $k$ 重复使用。

例如，明文 $M=\texttt{Helloworld}$，密钥 $k=\texttt{abc}$ 时，密文 $C=\texttt{Hfnlpyosnd}$。

$$
\def{\arraystretch}{1.5}
\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|} \hline
\textsf{明文} & \tt H & \tt e & \tt l & \tt l & \tt o & \tt w & \tt o & \tt r & \tt l & \tt d \\  \hline
\textsf{密钥} & \tt a & \tt b & \tt c & \tt a & \tt b & \tt c & \tt a & \tt b & \tt c & \tt a \\  \hline
\textsf{密文} & \tt H & \tt f & \tt n & \tt l & \tt p & \tt y & \tt o & \tt s & \tt n & \tt d \\  \hline
\end{array}
$$

inputFormat:
共 2 行。

第一行为一个字符串，表示密钥 $k$，长度不超过 $100$，其中仅包含大小写字母。

第二行为一个字符串，表示经加密后的密文，长度不超过 $1000$，其中仅包含大小写字母。

outputFormat: 一个字符串，表示输入密钥和密文所对应的明文。

hint:
对于 $100\%$ 的数据，输入的密钥的长度不超过 $100$，输入的密文的长度不超过 $1000$，且都仅包含英文字母。

NOIP 2012 提高组 第一天 第一题


title: [NOIP2012 提高组] 国王游戏

description:
恰逢 H 国国庆，国王邀请 $n$ 位大臣来玩一个有奖游戏。首先，他让每个大臣在左、右手上面分别写下一个整数，国王自己也在左、右手上各写一个整数。然后，让这 $n$ 位大臣排成一排，国王站在队伍的最前面。排好队后，所有的大臣都会获得国王奖赏的若干金币，每位大臣获得的金币数分别是：排在该大臣前面的所有人的左手上的数的乘积除以他自己右手上的数，然后向下取整得到的结果。

国王不希望某一个大臣获得特别多的奖赏，所以他想请你帮他重新安排一下队伍的顺序，使得获得奖赏最多的大臣，所获奖赏尽可能的少。注意，国王的位置始终在队伍的最前面。

inputFormat:
第一行包含一个整数 $n$，表示大臣的人数。

第二行包含两个整数 $a$ 和 $b$，之间用一个空格隔开，分别表示国王左手和右手上的整数。

接下来 $n$ 行，每行包含两个整数 $a$ 和 $b$，之间用一个空格隔开，分别表示每个大臣左手和右手上的整数。

outputFormat: 一个整数，表示重新排列后的队伍中获奖赏最多的大臣所获得的金币数。

hint:
【输入输出样例说明】

按 $1$、$2$、$3$ 这样排列队伍，获得奖赏最多的大臣所获得金币数为 $2$；

按 $1$、$3$、$2$ 这样排列队伍，获得奖赏最多的大臣所获得金币数为 $2$；

按 $2$、$1$、$3$ 这样排列队伍，获得奖赏最多的大臣所获得金币数为 $2$；

按$ 2$、$3$、$1 $这样排列队伍，获得奖赏最多的大臣所获得金币数为 $9$；

按 $3$、$1$、$2 $这样排列队伍，获得奖赏最多的大臣所获得金币数为 $2$；

按$ 3$、$2$、$1$ 这样排列队伍，获得奖赏最多的大臣所获得金币数为 $9$。

因此，奖赏最多的大臣最少获得 $2$ 个金币，答案输出 $2$。

【数据范围】

对于 $20\%$ 的数据，有 $1≤ n≤ 10,0 < a,b < 8$；

对于 $40\%$ 的数据，有$ 1≤ n≤20,0 < a,b < 8$；

对于 $60\%$ 的数据，有 $1≤ n≤100$；

对于 $60\%$ 的数据，保证答案不超过 $10^9$；

对于 $100\%$ 的数据，有 $1 ≤ n ≤1,000,0 < a,b < 10000$。

NOIP 2012 提高组 第一天 第二题


title: [NOIP2012 提高组] 开车旅行

description:
小 $\text{A}$ 和小 $\text{B}$ 决定利用假期外出旅行，他们将想去的城市从 $1 $ 到 $n$ 编号，且编号较小的城市在编号较大的城市的西边，已知各个城市的海拔高度互不相同，记城市 $i$ 的海拔高度为$h_i$，城市 $i$ 和城市 $j$ 之间的距离 $d_{i,j}$ 恰好是这两个城市海拔高度之差的绝对值，即 $d_{i,j}=|h_i-h_j|$。

旅行过程中，小 $\text{A}$ 和小 $\text{B}$ 轮流开车，第一天小 $\text{A}$ 开车，之后每天轮换一次。他们计划选择一个城市 $s$ 作为起点，一直向东行驶，并且最多行驶 $x$ 公里就结束旅行。

小 $\text{A}$ 和小 $\text{B}$ 的驾驶风格不同，小 $\text{B}$ 总是沿着前进方向选择一个最近的城市作为目的地，而小 $\text{A}$ 总是沿着前进方向选择第二近的城市作为目的地（注意：本题中如果当前城市到两个城市的距离相同，则认为离海拔低的那个城市更近）。如果其中任何一人无法按照自己的原则选择目的城市，或者到达目的地会使行驶的总距离超出 $x$ 公里，他们就会结束旅行。

在启程之前，小 $\text{A}$ 想知道两个问题：

1、 对于一个给定的 $x=x_0$，从哪一个城市出发，小 $\text{A}$ 开车行驶的路程总数与小 $\text{B}$ 行驶的路程总数的比值最小（如果小 $\text{B}$ 的行驶路程为 $0$，此时的比值可视为无穷大，且两个无穷大视为相等）。如果从多个城市出发，小 $\text{A}$ 开车行驶的路程总数与小 $\text{B}$ 行驶的路程总数的比值都最小，则输出海拔最高的那个城市。

2、对任意给定的 $x=x_i$ 和出发城市 $s_i$，小 $\text{A}$ 开车行驶的路程总数以及小 $\text B$ 行驶的路程总数。

inputFormat:
第一行包含一个整数 $n$，表示城市的数目。

第二行有 $n$ 个整数，每两个整数之间用一个空格隔开，依次表示城市 $1$ 到城市 $n$ 的海拔高度，即 $h_1,h_2 ... h_n$，且每个 $h_i$ 都是互不相同的。

第三行包含一个整数 $x_0$。

第四行为一个整数 $m$，表示给定 $m$ 组 $s_i$ 和 $x_i$。

接下来的 $m$ 行，每行包含 $2$ 个整数 $s_i$ 和 $x_i$，表示从城市$s_i$ 出发，最多行驶 $x_i$ 公里。

outputFormat:
输出共 $m+1$ 行。

第一行包含一个整数 $s_0$，表示对于给定的 $x_0$，从编号为 $s_0$ 的城市出发，小 $\text A$ 开车行驶的路程总数与小 $\text B$ 行驶的路程总数的比值最小。

接下来的 $m$ 行，每行包含 $2$ 个整数，之间用一个空格隔开，依次表示在给定的 $s_i$ 和 $x_i$ 下小 $\text A$ 行驶的里程总数和小 $\text B$ 行驶的里程总数。

hint:
【样例1说明】

![](https://cdn.luogu.com.cn/upload/image_hosting/zgms0k7y.png)

各个城市的海拔高度以及两个城市间的距离如上图所示。

如果从城市 $1$ 出发，可以到达的城市为 $2,3,4$，这几个城市与城市 $1$ 的距离分别为 $1,1,2$，但是由于城市 $3$ 的海拔高度低于城市 $2$，所以我们认为城市 $3$ 离城市 $1$ 最近，城市 $2$ 离城市 $1$ 第二近，所以小A会走到城市 $2$。到达城市 $2$ 后，前面可以到达的城市为 $3,4$，这两个城市与城市 $2$  的距离分别为 $2,1$，所以城市 $4$ 离城市 $2$ 最近，因此小B会走到城市$4$。到达城市 $4$ 后，前面已没有可到达的城市，所以旅行结束。

如果从城市 $2$ 出发，可以到达的城市为 $3,4$，这两个城市与城市 $2$ 的距离分别为 $2,1$，由于城市 $3$ 离城市 $2$ 第二近，所以小 $\text A$ 会走到城市 $3$。到达城市 $3$ 后，前面尚未旅行的城市为 $4$，所以城市 $4$ 离城市 $3$ 最近，但是如果要到达城市 $4$，则总路程为 $2+3=5>3$，所以小 $\text B$ 会直接在城市 $3$ 结束旅行。

如果从城市 $3$ 出发，可以到达的城市为 $4$，由于没有离城市 $3$ 第二近的城市，因此旅行还未开始就结束了。

如果从城市 $4$ 出发，没有可以到达的城市，因此旅行还未开始就结束了。

【样例2说明】

当 $x=7$ 时，如果从城市 $1$ 出发，则路线为 $1 \to 2 \to 3 \to 8 \to 9$，小 $\text A$ 走的距离为 $1+2=3$，小 $\text B$ 走的距离为 $1+1=2$。（在城市 $1$ 时，距离小 $\text A$ 最近的城市是 $2$ 和 $6$，但是城市 $2$ 的海拔更高，视为与城市 $1$ 第二近的城市，所以小 $\text A$ 最终选择城市 $2$；走到$9$ 后，小 $\text A$ 只有城市 $10$ 可以走，没有第二选择可以选，所以没法做出选择，结束旅行）

如果从城市 $2$ 出发，则路线为 $2 \to 6 \to 7$，小 $\text A$ 和小 $\text B$ 走的距离分别为 $2,4$。

如果从城市 $3$ 出发，则路线为 $3 \to 8 \to 9$，小 $\text A$ 和小 $\text B$ 走的距离分别为$2,1$。

如果从城市 $4$ 出发，则路线为 $4 \to 6 \to 7$，小 $\text A$ 和小 $\text B$ 走的距离分别为 $2,4$。

如果从城市 $5$ 出发，则路线为 $5 \to 7 \to 8$，小 $\text A$ 和小 $\text B$ 走的距离分别为 $5,1$。

如果从城市 $6$ 出发，则路线为 $6 \to 8 \to 9$，小 $\text A$ 和小 $\text B$ 走的距离分别为$5,1$。

如果从城市 $7$ 出发，则路线为 $7 \to 9 \to 10$，小 $\text A$ 和小 $\text B$ 走的距离分别为$2,1$。

如果从城市 $8$ 出发，则路线为 $8 \to 10$，小 $\text A$ 和小 $\text B$ 走的距离分别为$2,0$。

如果从城市 $9$ 出发，则路线为 $9$，小 $\text A$ 和小 $\text B$ 走的距离分别为 $0,0$（旅行一开始就结束了）。

如果从城市 $10$ 出发，则路线为 $10$，小 $\text A$ 和小 $\text B$ 走的距离分别为$0,0$。

从城市 $2$ 或者城市 $4$ 出发小 $\text A$ 行驶的路程总数与小 $\text B$ 行驶的路程总数的比值都最小，但是城市 $2$ 的海拔更高，所以输出第一行为 $2$。

【数据范围与约定】

对于 $30\%$ 的数据，有$1\le n \le 20,1\le m\le 20$；
对于$40\%$ 的数据，有$1\le n \le 100,1\le m\le 100$；
对于 $50\%$ 的数据，有$1\le n \le 100,1\le m\le 1000$；
对于 $70\%$ 的数据，有$1\le n \le 1000,1\le m\le 10^4$；
对于 $100\%$ 的数据：$1\le n,m \le 10^5$，$-10^9 \le h_i≤10^9$，$1 \le s_i \le n$，$0 \le x_i \le 10^9$
数据保证 $h_i$ 互不相同。


title: [NOIP2012 提高组] 同余方程

description: 求关于 $ x$ 的同余方程 $ a x \equiv 1 \pmod {b}$ 的最小正整数解。

inputFormat: 一行，包含两个整数 $a,b$，用一个空格隔开。

outputFormat: 一个整数 $x_0$，即最小正整数解。输入数据保证一定有解。

tags: 扩展欧几里德算法,exgcd


title: [NOIP2012 提高组] 借教室

description:
在大学期间，经常需要租借教室。大到院系举办活动，小到学习小组自习讨论，都需要向学校申请借教室。教室的大小功能不同，借教室人的身份不同，借教室的手续也不一样。

面对海量租借教室的信息，我们自然希望编程解决这个问题。

我们需要处理接下来 $n$ 天的借教室信息，其中第 $i$ 天学校有 $r_i$ 个教室可供租借。共有 $m$ 份订单，每份订单用三个正整数描述，分别为 $d_j,s_j,t_j$，表示某租借者需要从第 $s_j$ 天到第 $t_j$ 天租借教室（包括第 $s_j$ 天和第 $t_j$ 天），每天需要租借 $d_j$ 个教室。

我们假定，租借者对教室的大小、地点没有要求。即对于每份订单，我们只需要每天提供 $d_j$ 个教室，而它们具体是哪些教室，每天是否是相同的教室则不用考虑。

借教室的原则是先到先得，也就是说我们要按照订单的先后顺序依次为每份订单分配教室。如果在分配的过程中遇到一份订单无法完全满足，则需要停止教室的分配，通知当前申请人修改订单。这里的无法满足指从第 $s_j$ 天到第 $t_j$ 天中有至少一天剩余的教室数量不足 $d_j$ 个。

现在我们需要知道，是否会有订单无法完全满足。如果有，需要通知哪一个申请人修改订单。

inputFormat:
第一行包含两个正整数 $n,m$，表示天数和订单的数量。

第二行包含 $n$ 个正整数，其中第 $i$ 个数为 $r_i$，表示第 $i$ 天可用于租借的教室数量。

接下来有 $m$ 行，每行包含三个正整数 $d_j,s_j,t_j$，表示租借的数量，租借开始、结束分别在第几天。

每行相邻的两个数之间均用一个空格隔开。天数与订单均用从 $1$ 开始的整数编号。

outputFormat:
如果所有订单均可满足，则输出只有一行，包含一个整数 $0$。否则（订单无法完全满足）

输出两行，第一行输出一个负整数 $-1$，第二行输出需要修改订单的申请人编号。

hint:
【输入输出样例说明】

第 $1 $份订单满足后，$4 $天剩余的教室数分别为 $0,3,2,3$。第 $2$ 份订单要求第 $2 $天到第 $4$ 天每天提供$ 3 $个教室，而第 $3$ 天剩余的教室数为$ 2$，因此无法满足。分配停止，通知第$2$ 个申请人修改订单。

【数据范围】

对于10%的数据，有$1≤ n,m≤ 10$；

对于30%的数据，有$1≤ n,m≤1000$；

对于 70%的数据，有$1 ≤ n,m ≤ 10^5$；

对于 100%的数据，有$1 ≤ n,m ≤ 10^6,0 ≤ r_i,d_j≤ 10^9,1 ≤ s_j≤ t_j≤ n$。

NOIP 2012 提高组 第二天 第二题

2022.2.20 新增一组 hack 数据


title: [NOIP2012 提高组] 疫情控制

description:
H 国有 $n $ 个城市，这 $n$ 个城市用 $ n-1 $ 条双向道路相互连通构成一棵树，$1 $ 号城市是首都，也是树中的根节点。

H 国的首都爆发了一种危害性极高的传染病。当局为了控制疫情，不让疫情扩散到边境城市（叶子节点所表示的城市），决定动用军队在一些城市建立检查点，使得从首都到边境城市的每一条路径上都至少有一个检查点，边境城市也可以建立检查点。但特别要注意的是，首都是不能建立检查点的。

现在，在 H 国的一些城市中已经驻扎有军队，且一个城市可以驻扎多个军队。一支军队可以在有道路连接的城市间移动，并在除首都以外的任意一个城市建立检查点，且只能在一个城市建立检查点。一支军队经过一条道路从一个城市移动到另一个城市所需要的时间等于道路的长度（单位：小时）。

请问最少需要多少个小时才能控制疫情。注意：不同的军队可以同时移动。

inputFormat:
第一行一个整数 $ n$，表示城市个数。

接下来的 $n-1$ 行，每行 $ 3 $ 个整数，$u,v,w$，每两个整数之间用一个空格隔开，表示从城市 $u $ 到城市 $ v$ 有一条长为 $w$ 的道路。数据保证输入的是一棵树，且根节点编号为 $1$。

接下来一行一个整数 $m$，表示军队个数。

接下来一行 $m $ 个整数，每两个整数之间用一个空格隔开，分别表示这 $m$ 个军队所驻扎的城市的编号。

outputFormat: 一个整数，表示控制疫情所需要的最少时间。如果无法控制疫情则输出 $-1$。

hint:
【输入输出样例说明】

第一支军队在 $2$ 号点设立检查点，第二支军队从 $2$ 号点移动到$ 3$ 号点设立检查点，所需时间为 $3$ 个小时。

【数据范围】

保证军队不会驻扎在首都。

- 对于 $20\%$ 的数据，$2 \le n\le 10$；
- 对于 $40\%$ 的数据，$2 \le n\le 50$，$0<w <10^5$；
- 对于 $60\%$ 的数据，$2 \le n\le 1000$，$0<w <10^6$；
- 对于 $80\%$ 的数据，$2 \le n\le 10^4$；
- 对于 $100\%$ 的数据，$2\le m\le n≤5\times 10^4$，$0<w <10^9$。

NOIP 2012 提高组 第二天 第三题


title: [NOIP2004 普及组] 不高兴的津津

description: 津津上初中了。妈妈认为津津应该更加用功学习，所以津津除了上学之外，还要参加妈妈为她报名的各科复习班。另外每周妈妈还会送她去学习朗诵、舞蹈和钢琴。但是津津如果一天上课超过八个小时就会不高兴，而且上得越久就会越不高兴。假设津津不会因为其它事不高兴，并且她的不高兴不会持续到第二天。请你帮忙检查一下津津下周的日程安排，看看下周她会不会不高兴；如果会的话，哪天最不高兴。

inputFormat: 输入包括 $7$ 行数据，分别表示周一到周日的日程安排。每行包括两个小于 $10$ 的非负整数，用空格隔开，分别表示津津在学校上课的时间和妈妈安排她上课的时间。

outputFormat: 一个数字。如果不会不高兴则输出 $0$，如果会则输出最不高兴的是周几（用 $1, 2, 3, 4, 5, 6, 7$ 分别表示周一，周二，周三，周四，周五，周六，周日）。如果有两天或两天以上不高兴的程度相当，则输出时间最靠前的一天。

hint:
NOIP2004 普及组第 1 题

- 2021-10-27：增加一组 hack 数据
- 2022-06-05：又增加一组 hack 数据


title: [NOIP2004 普及组] 花生采摘

description:
鲁宾逊先生有一只宠物猴，名叫多多。这天，他们两个正沿着乡间小路散步，突然发现路边的告示牌上贴着一张小小的纸条：“欢迎免费品尝我种的花生！――熊字”。

鲁宾逊先生和多多都很开心，因为花生正是他们的最爱。在告示牌背后，路边真的有一块花生田，花生植株整齐地排列成矩形网格（如图一）。有经验的多多一眼就能看出，每棵花生植株下的花生有多少。为了训练多多的算术，鲁宾逊先生说：“你先找出花生最多的植株，去采摘它的花生；然后再找出剩下的植株里花生最多的，去采摘它的花生；依此类推，不过你一定要在我限定的时间内回到路边。”

![](https://cdn.luogu.com.cn/upload/image_hosting/unwk7hd0.png)

我们假定多多在每个单位时间内，可以做下列四件事情中的一件：

1) 从路边跳到最靠近路边（即第一行）的某棵花生植株；
2) 从一棵植株跳到前后左右与之相邻的另一棵植株；
3) 采摘一棵植株下的花生；
4) 从最靠近路边（即第一行）的某棵花生植株跳回路边。

现在给定一块花生田的大小和花生的分布，请问在限定时间内，多多最多可以采到多少个花生？注意可能只有部分植株下面长有花生，假设这些植株下的花生个数各不相同。

例如在图2所示的花生田里，只有位于 $(2, 5), (3, 7), (4, 2), (5, 4)$ 的植株下长有花生，个数分别为 $13, 7, 15, 9$。沿着图示的路线，多多在 $21$ 个单位时间内，最多可以采到 $37$ 个花生。

**注意**：在采摘过程中不能回到路边。

inputFormat: 第一行包括三个整数，$M, N$和$K$，用空格隔开；表示花生田的大小为$M  \times N(1  \le M, N  \le 20)$，多多采花生的限定时间为$K(0  \le K  \le  1000)$个单位时间。接下来的$M$行，每行包括$N$个非负整数，也用空格隔开；第$i + 1$行的第$j$个整数$P_{ij}(0  \le P_{ij}  \le 500)$表示花生田里植株$(i, j)$下花生的数目，$0$表示该植株下没有花生。

outputFormat: 一个整数，即在限定时间内，多多最多可以采到花生的个数。


title: [NOIP2004 普及组] FBI 树

description:
我们可以把由 0 和 1 组成的字符串分为三类：全 0 串称为 B 串，全 1 串称为 I 串，既含 0 又含 1 的串则称为 F 串。

FBI 树是一种二叉树，它的结点类型也包括 F 结点，B 结点和 I 结点三种。由一个长度为 $2^N$ 的 01 串 $S$ 可以构造出一棵 FBI 树 $T$，递归的构造方法如下：

1. $T$ 的根结点为 $R$，其类型与串 $S$ 的类型相同；
2. 若串 $S$ 的长度大于 $1$，将串 $S$ 从中间分开，分为等长的左右子串 $S_1$ 和 $S_2$；由左子串 $S_1$ 构造 $R$ 的左子树 $T_1$，由右子串 $S_2$ 构造 $R$ 的右子树 $T_2$。

现在给定一个长度为 $2^N$ 的 01 串，请用上述构造方法构造出一棵 FBI 树，并输出它的后序遍历序列。

inputFormat:
第一行是一个整数 $N(0 \le N \le 10)$，

第二行是一个长度为 $2^N$ 的 01 串。

outputFormat: 一个字符串，即 FBI 树的后序遍历序列。

hint:
对于 $40\%$ 的数据，$N \le 2$；

对于全部的数据，$N \le 10$。

noip2004普及组第3题


title: [NOIP2004 普及组] 火星人

description:
人类终于登上了火星的土地并且见到了神秘的火星人。人类和火星人都无法理解对方的语言，但是我们的科学家发明了一种用数字交流的方法。这种交流方法是这样的，首先，火星人把一个非常大的数字告诉人类科学家，科学家破解这个数字的含义后，再把一个很小的数字加到这个大数上面，把结果告诉火星人，作为人类的回答。

火星人用一种非常简单的方式来表示数字――掰手指。火星人只有一只手，但这只手上有成千上万的手指，这些手指排成一列，分别编号为 $1,2,3,\cdots$。火星人的任意两根手指都能随意交换位置，他们就是通过这方法计数的。

一个火星人用一个人类的手演示了如何用手指计数。如果把五根手指――拇指、食指、中指、无名指和小指分别编号为 $1,2,3,4$ 和 $5$，当它们按正常顺序排列时，形成了 $5$ 位数 $12345$，当你交换无名指和小指的位置时，会形成 $5$ 位数 $12354$，当你把五个手指的顺序完全颠倒时，会形成 $54321$，在所有能够形成的 $120$ 个 $5$ 位数中，$12345$ 最小，它表示 $1$；$12354$ 第二小，它表示 $2$；$54321$ 最大，它表示 $120$。下表展示了只有 $3$ 根手指时能够形成的 $6$ 个 $3$ 位数和它们代表的数字：

| 三进制数 | 代表的数字 |
|:-:|:-:|
| $123$ | $1$ |
| $132$ | $2$ |
| $213$ | $3$ |
| $231$ | $4$ |
| $312$ | $5$ |
| $321$ | $6$ |

现在你有幸成为了第一个和火星人交流的地球人。一个火星人会让你看他的手指，科学家会告诉你要加上去的很小的数。你的任务是，把火星人用手指表示的数与科学家告诉你的数相加，并根据相加的结果改变火星人手指的排列顺序。输入数据保证这个结果不会超出火星人手指能表示的范围。

inputFormat:
共三行。
第一行一个正整数 $N$，表示火星人手指的数目（$1 \le N \le 10000$）。
第二行是一个正整数 $M$，表示要加上去的小整数（$1  \le  M  \le  100$）。
下一行是 $1$ 到 $N$ 这 $N$ 个整数的一个排列，用空格隔开，表示火星人手指的排列顺序。

outputFormat: $N$ 个整数，表示改变后的火星人手指的排列顺序。每两个相邻的数中间用一个空格分开，不能有多余的空格。


title: [NOIP2004 提高组] 津津的储蓄计划

description:
津津的零花钱一直都是自己管理。每个月的月初妈妈给津津 $300$ 元钱，津津会预算这个月的花销，并且总能做到实际花销和预算的相同。

为了让津津学习如何储蓄，妈妈提出，津津可以随时把整百的钱存在她那里，到了年末她会加上 $20\%$ 还给津津。因此津津制定了一个储蓄计划：每个月的月初，在得到妈妈给的零花钱后，如果她预计到这个月的月末手中还会有多于 $100$ 元或恰好 $100$ 元，她就会把整百的钱存在妈妈那里，剩余的钱留在自己手中。

例如 $11$月初津津手中还有 $83$ 元，妈妈给了津津 $300$ 元。津津预计$11$月的花销是 $180$ 元，那么她就会在妈妈那里存 $200$ 元，自己留下 $183$ 元。到了 $11$ 月月末，津津手中会剩下 $3$ 元钱。

津津发现这个储蓄计划的主要风险是，存在妈妈那里的钱在年末之前不能取出。有可能在某个月的月初，津津手中的钱加上这个月妈妈给的钱，不够这个月的原定预算。如果出现这种情况，津津将不得不在这个月省吃俭用，压缩预算。

现在请你根据 $2004$ 年 $1$ 月到 $12$ 月每个月津津的预算，判断会不会出现这种情况。如果不会，计算到 $2004$ 年年末，妈妈将津津平常存的钱加上 $20\%$ 还给津津之后，津津手中会有多少钱。

inputFormat: $12$ 行数据，每行包含一个小于 $350$ 的非负整数，分别表示 $1$ 月到 $12$ 月津津的预算。

outputFormat:
一个整数。如果储蓄计划实施过程中出现某个月钱不够用的情况，输出 $-X$，$X$ 表示出现这种情况的第一个月；否则输出到 $2004$ 年年末津津手中会有多少钱。

注意，洛谷不需要进行文件输入输出，而是标准输入输出。


title: [NOIP2004 提高组] 合并果子 / [USACO06NOV] Fence Repair G

description:
在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。

每一次合并，多多可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。可以看出，所有的果子经过 $n-1$ 次合并之后， 就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。

因为还要花大力气把这些果子搬回家，所以多多在合并果子时要尽可能地节省体力。假定每个果子重量都为 $1$ ，并且已知果子的种类 数和每种果子的数目，你的任务是设计出合并的次序方案，使多多耗费的体力最少，并输出这个最小的体力耗费值。

例如有 $3$ 种果子，数目依次为 $1$ ， $2$ ， $9$ 。可以先将 $1$ 、 $2$ 堆合并，新堆数目为 $3$ ，耗费体力为 $3$ 。接着，将新堆与原先的第三堆合并，又得到新的堆，数目为 $12$ ，耗费体力为 $12$ 。所以多多总共耗费体力 $=3+12=15$ 。可以证明 $15$ 为最小的体力耗费值。

inputFormat:
共两行。
第一行是一个整数 $n(1\leq n\leq 10000)$ ，表示果子的种类数。

第二行包含 $n$ 个整数，用空格分隔，第 $i$ 个整数 $a_i(1\leq a_i\leq 20000)$ 是第 $i$ 种果子的数目。

outputFormat: 一个整数，也就是最小的体力耗费值。输入数据保证这个值小于 $2^{31}$ 。

hint:
对于 $30\%$ 的数据，保证有 $n \le 1000$：

对于 $50\%$ 的数据，保证有 $n \le 5000$；

对于全部的数据，保证有 $n \le 10000$。


title: [NOIP2004 提高组] 合唱队形

description:
$n$ 位同学站成一排，音乐老师要请其中的 $n-k$ 位同学出列，使得剩下的 $k$ 位同学排成合唱队形。

合唱队形是指这样的一种队形：设 $k$ 位同学从左到右依次编号为 $1,2,$ … $,k$，他们的身高分别为 $t_1,t_2,$ … $,t_k$，则他们的身高满足 $t_1< \cdots <t_i>t_{i+1}>$ … $>t_k(1\le i\le k)$。

你的任务是，已知所有 $n$ 位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。

inputFormat:
共二行。

第一行是一个整数 $n$（$2\le n\le100$），表示同学的总数。

第二行有 $n$ 个整数，用空格分隔，第 $i$ 个整数 $t_i$（$130\le t_i\le230$）是第 $i$ 位同学的身高（厘米）。

outputFormat: 一个整数，最少需要几位同学出列。

hint:
对于 $50\%$ 的数据，保证有 $n \le 20$。

对于全部的数据，保证有 $n \le 100$。


title: [NOIP2004 提高组] 虫食算

description:
所谓虫食算，就是原先的算式中有一部分被虫子啃掉了，需要我们根据剩下的数字来判定被啃掉的数字。来看一个简单的例子：

$$\begin{aligned}
 \verb!43#9865#045! \\
+\qquad \verb!8468#6633! \\[-1em]\underline{\kern{8em}} \\
 \verb!44445509678! \\
\end{aligned}$$

其中 `#` 号代表被虫子啃掉的数字。根据算式，我们很容易判断：第一行的两个数字分别是 $5$ 和 $3$，第二行的数字是 $5$。

现在，我们对问题做两个限制：

首先，我们只考虑加法的虫食算。这里的加法是 $n$ 进制加法，算式中三个数都有 $n$ 位，允许有前导的 $0$。

其次，虫子把所有的数都啃光了，我们只知道哪些数字是相同的，我们将相同的数字用相同的字母表示，不同的数字用不同的字母表示。如果这个算式是 $n$ 进制的，我们就取英文字母表的前 $n$ 个大写字母来表示这个算式中的 $0$ 到 $n - 1$ 这 $n$ 个不同的数字：但是这 $n$ 个字母并不一定顺序地代表 $0$ 到 $n-1$。输入数据保证 $n$ 个字母分别至少出现一次。

$$\begin{aligned}
 \verb!BADC! \\
+\quad \verb!CBDA! \\[-1em]\underline{\kern{4em}} \\
 \verb!DCCC! \\
\end{aligned}$$

上面的算式是一个4进制的算式。很显然，我们只要让 $\verb!ABCD!$ 分别代表 $0123$，便可以让这个式子成立了。你的任务是，对于给定的 $n$ 进制加法算式，求出 $n$ 个不同的字母分别代表的数字，使得该加法算式成立。输入数据保证有且仅有一组解。

inputFormat:
输入的第一行是一个整数 $n$，代表进制数。

第二到第四行，每行有一个由大写字母组成的字符串，分别代表两个加数以及和。这 $3$ 个字符串左右两端都没有空格，从左到右依次代表从高位到低位，并且恰好有 $n$ 位。

outputFormat: 输出一行 $n$ 个用空格隔开的整数，分别代表 $A,B, \dots$ 代表的数字。

hint:
#### 数据规模与约定

- 对于 $30\%$ 的数据，保证 $n \le 10$；
- 对于 $50\%$ 的数据，保证 $n \le 15$；
- 对于 $100\%$ 的数据，保证 $1 \leq n \leq 26$。


title: [NOIP2007 普及组] 奖学金

background: NOIP2007 普及组 T1

description:
某小学最近得到了一笔赞助，打算拿出其中一部分为学习成绩优秀的前 $5$ 名学生发奖学金。期末，每个学生都有 $3$ 门课的成绩：语文、数学、英语。先按总分从高到低排序，如果两个同学总分相同，再按语文成绩从高到低排序，如果两个同学总分和语文成绩都相同，那么规定学号小的同学排在前面，这样，每个学生的排序是唯一确定的。

任务：先根据输入的 $3$ 门课的成绩计算总分，然后按上述规则排序，最后按排名顺序输出前五名名学生的学号和总分。

注意，在前 $5$ 名同学中，每个人的奖学金都不相同，因此，你必须严格按上述规则排序。例如，在某个正确答案中，如果前两行的输出数据（每行输出两个数：学号、总分) 是：

```plain
7 279
5 279
```

这两行数据的含义是：总分最高的两个同学的学号依次是 $7$ 号、$5$ 号。这两名同学的总分都是 $279$ (总分等于输入的语文、数学、英语三科成绩之和) ，但学号为 $7$ 的学生语文成绩更高一些。

如果你的前两名的输出数据是：

```plain
5 279
7 279
```

则按输出错误处理，不能得分。

inputFormat:
共 $n+1$ 行。

第 $1$ 行为一个正整数 $n \le 300$，表示该校参加评选的学生人数。

第 $2$ 到 $n+1$ 行，每行有 $3$ 个用空格隔开的数字，每个数字都在 $0$ 到 $100$ 之间。第 $j$ 行的 $3$ 个数字依次表示学号为 $j-1$ 的学生的语文、数学、英语的成绩。每个学生的学号按照输入顺序编号为 $1\sim n$（恰好是输入数据的行号减 $1$）。

保证所给的数据都是正确的，不必检验。

outputFormat: 共 $5$ 行，每行是两个用空格隔开的正整数，依次表示前 $5$ 名学生的学号和总分。


title: [NOIP2007 普及组] 纪念品分组

background: NOIP2007 普及组 T2

description:
元旦快到了，校学生会让乐乐负责新年晚会的纪念品发放工作。为使得参加晚会的同学所获得 的纪念品价值相对均衡，他要把购来的纪念品根据价格进行分组，但每组最多只能包括两件纪念品， 并且每组纪念品的价格之和不能超过一个给定的整数。为了保证在尽量短的时间内发完所有纪念品，乐乐希望分组的数目最少。

你的任务是写一个程序，找出所有分组方案中分组数最少的一种，输出最少的分组数目。

inputFormat:
共 $n+2$ 行：

第一行包括一个整数 $w$，为每组纪念品价格之和的上限。

第二行为一个整数 $n$，表示购来的纪念品的总件数 $G$。

第 $3\sim n+2$ 行每行包含一个正整数 $P_i$ 表示所对应纪念品的价格。

outputFormat: 一个整数，即最少的分组数目。


title: [NOIP2007 普及组] 守望者的逃离

background: NOIP2007 普及组 T3

description:
恶魔猎手尤迪安野心勃勃，他背叛了暗夜精灵，率领深藏在海底的娜迦族企图叛变。

守望者在与尤迪安的交锋中遭遇了围杀，被困在一个荒芜的大岛上。

为了杀死守望者，尤迪安开始对这个荒岛施咒，这座岛很快就会沉下去。到那时，岛上的所有人都会遇难。

守望者的跑步速度为 $17m/s$，以这样的速度是无法逃离荒岛的。庆幸的是守望者拥有闪烁法术，可在 $1s$ 内移动 $60m$，不过每次使用闪烁法术都会消耗魔法值 $10$ 点。守望者的魔法值恢复的速度为 $4$ 点每秒，只有处在原地休息状态时才能恢复。

现在已知守望者的魔法初值 $M$，他所在的初始位置与岛的出口之间的距离 $S$，岛沉没的时间 $T$。你的任务是写一个程序帮助守望者计算如何在最短的时间内逃离荒岛，若不能逃出，则输出守望者在剩下的时间内能走的最远距离。

注意：守望者跑步、闪烁或休息活动均以秒为单位，且每次活动的持续时间为整数秒。距离的单位为米。

inputFormat: 输入数据共一行三个非负整数，分别表示 $M$，$S$，$T$。

outputFormat:
输出数据共两行。

第一行一个字符串 $\texttt{Yes}$ 或 $\texttt{No}$，即守望者是否能逃离荒岛。

第二行包含一个整数。第一行为 $\texttt{Yes}$ 时表示守望者逃离荒岛的最短时间；第一行为 $\texttt{No}$ 时表示守望者能走的最远距离。


title: [NOIP2007 普及组] Hanoi 双塔问题

description:
给定 A、B、C 三根足够长的细柱，在 A 柱上放有 $2n$ 个中间有孔的圆盘，共有 $n$ 个不同的尺寸，每个尺寸都有两个相同的圆盘，注意这两个圆盘是不加区分的（下图为 $n=3$ 的情形）。

![](https://cdn.luogu.com.cn/upload/image_hosting/mq2iklbv.png)

现要将这些圆盘移到 C 柱上，在移动过程中可放在 B 柱上暂存。要求：

1. 每次只能移动一个圆盘；
2. A、B、C 三根细柱上的圆盘都要保持上小下大的顺序。

任务：设 $A_n$ 为 $2n$ 个圆盘完成上述任务所需的最少移动次数，对于输入的 $n$，输出 $A_n$。

inputFormat: 一个正整数 $n$，表示在 A 柱上放有 $2n$ 个圆盘。

outputFormat: 一个正整数, 为完成上述任务所需的最少移动次数 $A_n$。


title: [NOIP2007 提高组] 统计数字

description: 某次科研调查时得到了 $n$ 个自然数，每个数均不超过 $1.5 \times 10^9$。已知不相同的数不超过 $10^4$ 个，现在需要统计这些自然数各自出现的次数，并按照自然数从小到大的顺序输出统计结果。

inputFormat:
共 $n+1$ 行。

第一行是整数 $n$，表示自然数的个数；

第 $2$ 至 $n+1$ 每行一个自然数。

outputFormat:
共 $m$ 行（$m$ 为 $n$ 个自然数中不相同数的个数），按照自然数从小到大的顺序输出。

每行输出 $2$ 个整数，分别是自然数和该数出现的次数，其间用一个空格隔开。


title: [NOIP2007 提高组] 字符串的展开

description:
在初赛普及组的“阅读程序写结果”的问题中，我们曾给出一个字符串展开的例子：如果在输入的字符串中，含有类似于 `d-h` 或者 `4-8` 的字串，我们就把它当作一种简写，输出时，用连续递增的字母或数字串替代其中的减号，即，将上面两个子串分别输出为 `defgh` 和 `45678`。在本题中，我们通过增加一些参数的设置，使字符串的展开更为灵活。具体约定如下：

(1) 遇到下面的情况需要做字符串的展开：在输入的字符串中，出现了减号 `-` ，减号两侧同为小写字母或同为数字，且按照 `ASCII` 码的顺序，减号右边的字符严格大于左边的字符。

(2) 参数 $p_1$：展开方式。$p_1=1$ 时，对于字母子串，填充小写字母；$p_1=2$ 时，对于字母子串，填充大写字母。这两种情况下数字子串的填充方式相同。$p_1=3$ 时，不论是字母子串还是数字字串，都用与要填充的字母个数相同的星号 `*` 来填充。

(3) 参数 $p_2$：填充字符的重复个数。$p_2=k$ 表示同一个字符要连续填充 $k$ 个。例如，当 $p_2=3$ 时，子串`d-h` 应扩展为 `deeefffgggh`。减号两边的字符不变。

(4) 参数 $p_3$：是否改为逆序：$p_3=1$ 表示维持原来顺序，$p_3=2$ 表示采用逆序输出，注意这时候仍然不包括减号两端的字符。例如当 $p_1=1$、$p_2=2$、$p_3=2$ 时，子串 `d-h` 应扩展为 `dggffeeh`。

(5) 如果减号右边的字符恰好是左边字符的后继，只删除中间的减号，例如：`d-e` 应输出为 `de`，`3-4` 应输出为 `34`。如果减号右边的字符按照 `ASCII` 码的顺序小于或等于左边字符，输出时，要保留中间的减号，例如：`d-d` 应输出为 `d-d`，`3-1` 应输出为 `3-1`。

inputFormat:
共两行。

第 $1$ 行为用空格隔开的 $3$ 个正整数，依次表示参数 $p_1,p_2,p_3$。

第 $2$ 行为一行字符串，仅由数字、小写字母和减号 `-` 组成。行首和行末均无空格。

outputFormat: 共一行，为展开后的字符串。

hint:
$40\%$ 的数据满足：字符串长度不超过 $5$。

$100\%$ 的数据满足：$1  \le  p_1  \le  3,1  \le  p_2  \le  8,1  \le  p_3  \le  2$。字符串长度不超过 $100$。

NOIP 2007 提高第二题


title: [NOIP2007 提高组] 树网的核

description:
设 $T=(V,E,W)$ 是一个无圈且连通的无向图（也称为无根树），每条边都有正整数的权，我们称 $T$ 为树网（`treenetwork`），其中 $V$，$E$ 分别表示结点与边的集合，$W$ 表示各边长度的集合，并设 $T$ 有 $n$ 个结点。

路径：树网中任何两结点 $a$，$b$ 都存在唯一的一条简单路径，用 $d(a, b)$ 表示以 $a, b$ 为端点的路径的长度，它是该路径上各边长度之和。我们称
$d(a, b)$ 为 $a, b$ 两结点间的距离。

$D(v, P)=\min\{d(v, u)\}$, $u$ 为路径 $P$ 上的结点。

树网的直径：树网中最长的路径成为树网的直径。对于给定的树网 $T$，直径不一定是唯一的，但可以证明：各直径的中点（不一定恰好是某个结点，可能在某条边的内部）是唯一的，我们称该点为树网的中心。

偏心距 $\mathrm{ECC}(F)$：树网 $T$ 中距路径 $F$ 最远的结点到路径 $F$ 的距离，即

$$\mathrm{ECC}(F)=\max\{D(v, F),v \in V\}$$

任务：对于给定的树网 $T=(V, E, W)$ 和非负整数 $s$，求一个路径 $F$，他是某直径上的一段路径（该路径两端均为树网中的结点），其长度不超过 $s$（可以等于 $s$），使偏心距 $\mathrm{ECC}(F)$ 最小。我们称这个路径为树网 $T=(V, E, W)$ 的核（`Core`）。必要时，$F$ 可以退化为某个结点。一般来说，在上述定义下，核不一定只有一个，但最小偏心距是唯一的。

下面的图给出了树网的一个实例。图中，$A-B$ 与 $A-C$ 是两条直径，长度均为 $20$。点 $W$ 是树网的中心，$EF$ 边的长度为 $5$。如果指定 $s=11$，则树网的核为路径`DEFG`（也可以取为路径`DEF`），偏心距为 $8$。如果指定 $s=0$（或 $s=1$、$s=2$），则树网的核为结点 $F$，偏心距为 $12$。

![](https://cdn.luogu.com.cn/upload/image_hosting/oms5c6rq.png)

inputFormat:
共 $n$ 行。

第 $1$ 行，两个正整数 $n$ 和 $s$，中间用一个空格隔开。其中 $n$ 为树网结点的个数，$s$ 为树网的核的长度的上界。设结点编号以此为 $1,2\dots,n$。

从第 $2$ 行到第 $n$ 行，每行给出 $3$ 个用空格隔开的正整数 $u, v, w$，依次表示每一条边的两个端点编号和长度。例如，`2 4 7` 表示连接结点 $2$ 与 $4$ 的边的长度为 $7$。

outputFormat: 一个非负整数，为指定意义下的最小偏心距。

hint:
- 对于 $40\%$ 的数据，保证 $n \le 15$。
- 对于 $70\%$ 的数据，保证 $n \le 80$。
- 对于 $100\%$ 的数据，保证 $2\le n \le 300$，$0\le s\le10^3$，$1 \leq u, v \leq n$，$0 \leq w \leq 10^3$。

NOIP2007 提高组第四题


title: 高低位交换

description:
给出一个小于 $2^{32}$ 的非负整数。这个数可以用一个 $32$ 位的二进制数表示（不足 $32$ 位用 $0$ 补足）。我们称这个二进制数的前 $16$ 位为“高位”，后 $16$ 位为“低位”。将它的高低位交换，我们可以得到一个新的数。试问这个新的数是多少（用十进制表示）。

例如，数 $1314520$ 用二进制表示为 $0000\,0000\,0001\,0100\,0000\,1110\,1101\,1000$（添加了 $11$ 个前导 $0$ 补足为 $32$ 位），其中前 $16$ 位为高位，即 $0000\,0000\,0001\,0100$；后 $16$ 位为低位，即 $0000\,1110\,1101\,1000$。将它的高低位进行交换，我们得到了一个新的二进制数 $0000\,1110\,1101\,1000\,0000\,0000\,0001\,0100$。它即是十进制的 $249036820$。

inputFormat: 一个小于 $2^{32}$ 的非负整数

outputFormat: 将新的数输出


title: 单词方阵

description: 给一 $n \times n$ 的字母方阵，内可能蕴含多个 `yizhong` 单词。单词在方阵中是沿着同一方向连续摆放的。摆放可沿着 $8$ 个方向的任一方向，同一单词摆放时不再改变方向，单词与单词之间可以交叉，因此有可能共用字母。输出时，将不是单词的字母用 `*` 代替，以突出显示单词。

inputFormat:
第一行输入一个数 $n$。$(7 \le n \le 100)$。

第二行开始输入 $n \times n$ 的字母矩阵。

outputFormat: 突出显示单词的 $n \times n$ 矩阵。

samples:
7
aaaaaaa
aaaaaaa
aaaaaaa
aaaaaaa
aaaaaaa
aaaaaaa
aaaaaaa

samples:
8
qyizhong
gydthkjy
nwidghji
orbzsfgz
hhgrhwth
zzzzzozo
iwdfrgng
yyyygggg


title: A-B 数对

background:
出题是一件痛苦的事情！

相同的题目看多了也会有审美疲劳，于是我舍弃了大家所熟悉的 A+B Problem，改用 A-B 了哈哈！

description: 给出一串正整数数列以及一个正整数 $C$，要求计算出所有满足 $A - B = C$ 的数对的个数（不同位置的数字一样的数对算不同的数对）。

inputFormat:
输入共两行。

第一行，两个正整数 $N,C$。

第二行，$N$ 个正整数，作为要求处理的那串数。

outputFormat: 一行，表示该串正整数中包含的满足 $A - B = C$ 的数对的个数。