总时间限制: 1000ms 内存限制: 65536kB

描述

在 N（1<=N<10,000 且 N 为奇数）个数中，找到中位数。

输入

第 1 行：N

第 2 至 N+1 行：每行是一个整数

输出

第一行：中位数

样例输入

总时间限制: 5000ms 内存限制: 65536kB

描述

给出 N 个范围在 [0, 65535] 的整数，编程支持以下的操作：

（1）修改操作：C d，所有的数都增加 d。如果超过 65535，把结果模 65536。 0 <= d <= 65535
（2）查询操作：Q i，统计在 N 个正整数中有多少个整数其对应的二进制形式的第 i 位二进制位为非 0。0 <= i <= 15。并且最低位 i 为 0。

最后，输出所有查询操作的统计值。

输入

输入的第一行为两个正整数 N,M, 其中 N 为操作的整数的个数，而 M 为具体有多少个操作。
输入的第二行为 N 个正整数，为进行操作的 N 个正整数。
下面有 M 行，分别表示 M 个操作。

N<=100000,M<=200000

输出

总时间限制: 3000ms 内存限制: 65536kB

描述

你旅游到了一个国外的城市。那里的人们说的外国语言你不能理解。不过幸运的是，你有一本词典可以帮助你。

输入

首先输入一个词典，词典中包含不超过 100000 个词条，每个词条占据一行。每一个词条包括一个英文单词和一个外语单词，两个单词之间用一个空格隔开。而且在词典中不会有某个外语单词出现超过两次。词典之后是一个空行，然后给出一个由外语单词组成的文档，文档不超过 100000 行，而且每行只包括一个外语单词。输入中出现单词只包括小写字母，而且长度不会超过 10。

输出

在输出中，你需要把输入文档翻译成英文，每行输出一个英文单词。如果某个外语单词不在词典中，就把这个单词翻译成 “eh”。

样例输入

1
2
3
4
5
6
7
8
9

dog ogday
cat atcay
pig igpay
froot ootfray
loops oopslay

atcay
ittenkay
oopslay

总时间限制: 1000ms 内存限制: 1024kB

描述

二叉搜索树在动态查表中有特别的用处，一个无序序列可以通过构造一棵二叉搜索树变成一个有序序列，构造树的过程即为对无序序列进行排序的过程。每次插入的新的结点都是二叉搜索树上新的叶子结点，在进行插入操作时，不必移动其它结点，只需改动某个结点的指针，由空变为非空即可。

这里，我们想探究二叉树的建立和序列输出。

输入

只有一行，包含若干个数字，中间用空格隔开。（数字可能会有重复）

输出

输出一行，对输入数字建立二叉搜索树后进行前序周游的结果。

样例输入

总时间限制: 1000ms 内存限制: 262144kB

描述

VariantF 的电脑上安装了一个机器翻译软件，他经常用这个软件来翻译英语文章。这个翻译软件的原理很简单，它只是从头到尾，依次将每个英文单词用对应的中文含义来替换。对于每个英文单词，软件会先在内存中查找这个单词的中文含义，如果内存中有，软件就会用它进行翻译；如果内存中没有，软件就会在外存中的词典内查找，查出单词的中文含义然后翻译，并将这个单词和译义放入内存，以备后续的查找和翻译。
假设内存中有 M 个单元，每单元能存放一个单词和译义。每当软件将一个新单词存入内存前，如果当前内存中已存入的单词数不超过 M，软件会将新单词存入一个未使用的内存单元；若内存中已存入 M 个单词，软件会清空最早进入内存的那个单词，腾出单元来，存放新单词。
假设一篇英语文章的长度为 N 个单词。给定这篇待译文章，翻译软件需要去外存查找多少次词典？假设在翻译开始前，内存中没有任何单词。

输入

第一行为两个正整数 M 和 N，代表内存容量和文章的长度。
第二行为 N 个非负整数，按照文章的顺序，每个数（大小不超过 1000000）代表一个英文单词。文章中两个单词是同一个单词，当且仅当它们对应的非负整数相同。
对于 50% 的数据，1<=N、M<=1000；
对于 100% 的数据，1<=N、M<=1000000。

输出

一个整数，为软件需要查词典的次数。

样例输入

1
2

3 7 
1 2 1 5 4 4 1 

总时间限制: 1000ms 内存限制: 65536kB

描述

判断一个由 a-z 这 26 个字符组成的字符串中哪个字符出现的次数最多

输入

第 1 行是测试数据的组数 n，每组测试数据占 1 行，是一个由 a-z 这 26 个字符组成的字符串
每组测试数据之间有一个空行，每行数据不超过 1000 个字符且非空

输出

n 行，每行输出对应一个输入。一行输出包括出现次数最多的字符和该字符出现的次数，中间是一个空格。
如果有多个字符出现的次数相同且最多，那么输出 ascii 码最小的那一个字符

样例输入

1
2
3
4

2
abbccc

adfadffasdf

总时间限制: 1000ms 内存限制: 65535kB

描述

栈和队列都是常用的线性结构，它们都提供两个操作：

Push：加入一个元素。

Pop：弹出一个元素。

不同的是，栈是” 先进后出”，而队列则是” 先进先出”。

给出一个线性结构的进出顺序，判定这个结构是栈还是队列。

输入

第一行输入一个整数 t，代表有 t 组测试数据
对于每组测试数据，第一行输入一个整数 n，代表操作的次数。
随后输入 n 行，每行包含两个整数 type val。
当 type = 1 时，表示该次操作为 push 操作，val 表示进入的数字。当 type=2 时，表示该次操作为 pop 操作，val 代表出来的数字。
3<=n<=2000

总时间限制: 1000ms 内存限制: 1000kB

描述

栈是一种重要的数据结构，它具有 push k 和 pop 操作。push k 是将数字 k 加入到栈中，pop 则是从栈中取一个数出来。

栈是后进先出的：把栈也看成横向的一个通道，则 push k 是将 k 放到栈的最右边，而 pop 也是从栈的最右边取出一个数。

假设栈当前从左至右含有 1 和 2 两个数，则执行 push 5 和 pop 操作示例图如下：

1
2
3

          push 5          pop

栈   1 2  ------->  1 2 5 ------>  1 2

现在，假设栈是空的。给定一系列 push k 和 pop 操作之后，输出栈中存储的数字。若栈已经空了，仍然接收到 pop 操作，

则输出 error。

输入

总时间限制: 1000ms 内存限制: 65536kB

描述

有两个字符串 str 和 substr，str 的字符个数不超过 10，substr 的字符个数为 3。（字符个数不包括字符串结尾处的’\0’。）将 substr 插入到 str 中 ASCII 码最大的那个字符后面，若有多个最大则只考虑第一个。

输入

输入包括若干行，每一行为一组测试数据，格式为
str substr

输出

对于每一组测试数据，输出插入之后的字符串。

样例输入

1
2

abcab eee
12343 555

总时间限制: 1000ms 内存限制: 5000kB

描述

我们经常遇到两多项式相加的情况，在这里，我们就需要用程序来模拟实现把两个多项式相加到一起。首先，我们会有两个多项式，每个多项式是独立的一行，每个多项式由系数、幂数这样的多个整数对来表示。

如多项式 2x20- x17+ 5x9- 7x7+ 16x5+ 10x4 + 22x2- 15

对应的表达式为：2 20 -1 17 5 9 - 7 7 16 5 10 4 22 2 -15 0。

为了标记每行多项式的结束，在表达式后面加上了一个幂数为负数的整数对。

同时输入表达式的幂数大小顺序是随机的。

我们需要做的就是把所给的两个多项式加起来。

输入