T1

80分算法

写了一个最水的贪心(毫无正确性)，每次取最大得数给 Bob，取完后其他的给 Alice，用 max_element 很短就能实现…

数位dp模板，记忆化搜索，dp[pos][pre][status]。
以不要62【hdu】为例

两个n次多项式相加最直接的方法所需时间为O(n)，但是相乘最直接的方法所需时间为O(n²)。
快速傅里叶变换（Fast Fourier Transform，FFT）是一种可在 O(n log n)时间内完成的离散傅里叶变换（Discrete Fourier transform，DFT）算法，在 OI 中的主要应用之一是加速多项式乘法的计算。

这一次 3 道题都与 gcd 有关的测试,也是醉了……

T1

此题 5 分钟以内想出标算,然后 zz 地写挂,而且还能 TLE 掉…只拿了50…… 然而据 lcr 所说,此题最难!!!
思路与 gcd 相同,只是每次取 $\lfloor \frac m n \rfloor * n$ 个 $n$,然后令 $n_1 = m % n, m_1 = n$ 递归获迭代下去即可…

T1

这本来是一道水题,八个方向暴力枚举,判断一下边界就行(其实不判断边界也行),谨以此题爆 $0$ 警示自己不能再把 $n,m$ 看反……
另外此题有许多同学在 linux 下 WA,*注意 windows 下的换行符为 \r\n *,不要只 getchar() 一次,注意单独处理…

OI模板总结

数学模板

快速幂

分析

如果没有加法就是普通的可持久化trie了,加法真是烦!此题可以按位进行贪心,肯定从高位开始,每次判断这一位异或完能不能是1,即查询一段区间是否有某个范围的数,可以用主席树…

SPFA【SLF优化】

SLF

Small Label First 策略，设要加入的节点是j，队首元素为i，若dis[j] < dis[i]，则将j插入队首，否则插入队尾，可能会被卡到指数级复杂度。

pb_ds库

pb_ds??
平板电视??
pb_ds是G++编译器默认附带的一个扩展库,全称是Policy-Based Data Structures(官方传送门)…
pb_ds库里含有许多数据结构,如HashTable,trie,rb_tree,priority_queue…

题目描述

给定一个一定存在从起点到终点的路径的四联通迷宫。已知 Tar 左右方向移动的时间为 1 ，上下移动的时间为未知实数 v 。求当 Tar 从起点到终点的最短移动时间为已知实数 L 时，未知实数 v 是多少。

题目描述

在一个忍者的帮派里，一些忍者们被选中派遣给顾客，然后依据自己的工作获取报偿。
在这个帮派里，有一名忍者被称之为 Master。除了 Master 以外，每名忍者都有且仅有一个上级。为保密，同时增强忍者们的领导力，所有与他们工作相关的指令总是由上级发送给他的直接下属，而不允许通过其他的方式发送。

题目描述

在计算机科学应用中，我们经常要用到集合的运算，集合的运算操作有很多，下面是我们给出的集合基本运算定义：
（1）“∪”运算：设 S，T 是 2 个集合，那么 S∪T 是由 S 和 T 的元素组成的集合。
（2）“-”运算：设 S，T 是 2 个集合，那么 S-T 是由 S 中非 T 中的元素组成的集合。
（3）“∩”运算：设 S，T 是 2 个集合，那么 S∩T 是由既是 S 又是 T 的元素组成的集合。

加边

题目描述

给出一个 N×M 的矩阵，在这个矩阵上的每一个点都有一个高度值 h 。矩阵中相邻两点是连通的，而且只能从高度高的点到达高度低的点，高度相同的点之间可以相互到达。
现在要求在图中连若干双向边，使图中任意一点 u 出发都可以到达任意的其它点 v ，问至少需要连接多少条双向边？

输入格式

第一行是两个整数：（1 \leq N,M \leq 300），其中, N，M分别表示矩阵的行数和列数。
从第二行开始，描述的是一个 N 行 M 列的矩阵，矩阵每个位置上的数字表示该位置的高度 h（1 \leq h \leq 1,000,000）。

输出格式

输出一个整数，即至少需要连接的边的数量。

最佳路线

题目描述

N 个景区，任意两个景区之间有一条或多条双向的路来连接，现在 Mr.Zeng 想找一条旅游路线，这个路线从 A 点出发并且最后回到 A 点，假设经过的路线为 V1，V2，….VK，V1，那么必须满足 K>2，就是说至除了出发点以外至少要经过 2 个其他不同的景区，而且不能重复经过同一个景区。不存在这样的景区 X：从 X 出发不到达其他景区马上回到 X。现在 Mr.Zeng 需要你帮他找一条这样的路线，并且长度越小越好。

输入格式

第一行包含两个正整数：景区个数 N（N<=100），另一个是道路的数目 M（M<10000）。
接下来 M 行每行描述一条路，每一行有三个正整数 A，B，C，其中 A 和 B 分别表示这条路连接的两个景区的编号，C 表示这条路的长度（不超过500的正整数）。

输出格式

如果这条观光路线是不存在的话就显示“No solution.”(有句号)；
如果这条观光路线存在就输出经过的最小长度。

计算数字

题目描述

当连续写下从十进制整数 1 开始到某个整数 N 之间的所有整数时，能得到如下的数字序列：
12345678910111213141516171819202122 \cdots \cdots
编写一个程序，计算这个序列中的数字个数。

输入格式

输入的第一行且是唯一的一行包含：一个整数 N，1 \leq N \leq 100,000,000。

输出格式

输出的第一行且是唯一的一行应包含：由给定的整数所产生的序列的数字个数。

查找

题目描述

中考成绩出来了，许多考生想知道自己成绩排名情况，于是考试委员会找到了你，让你帮助完成一个成绩查找程序，考生只要输入成绩，即可知道其排名及同名次的人有多少。

输入格式

第一行一个正整数 n（1<=n<=1500），表示一共有 n 个考生；
第二行一个正整数 k（1<=k<=n），表示一共有 k 个待查分数；
第三行 n 个数是以空格隔开的从大到小排列的 n 个学生成绩；
第四行 k 个数是待查的成绩。

输出格式

共输出 k 行，每行三个数，分别用一个空格隔开：第一个数为待查成绩所对应的名次；第二个数为同名次的人数；第三个数为分数高于该成绩的人数。
若查找不到，本行只输出一个单词“fail!”（fail后面加一个惊叹号，引号不输出）。

破译密码

题目描述

抗日战争中，中方截获日方的信息由 n（n \leq 30000）个非负整数组成，其中每个数字都在 int 范围内。因为是日军的高端秘密，所以一时不能破获。最原始的想法就是对这 n 个数进行从小到大排序，对排序后的数按顺序依次从 1～n 进行编号，然后请你输出编号为 i 的数。

解密

题目描述

为了保密，QW 星球使用了特殊的指令，指令以字符的形式发出，并且应用了加密策略。现在，他们的加密规则被我们熟悉，原来规则如此有趣：将所有 a～z 或 A～Z 字母变成它的后继，例如“A”变成“B”，“a”变成“b”,“Z”变成“A”，“z”变成“a”，其他非字母的字符保持不变。现在请你破译接收到的一串指令。

选票统计

题目描述

国际运动协会组织了一个评选n佳运动员的活动。对 n 个运动员从 1 到 n 进行编号，然后评委们开始投票，最后根据不同的得票数，颁发不同的奖项。
现在组织者想知道投票后，这n个运动员分别获得的票数，请你帮他完成统计工作。

字符个数

题目描述

输入一串字符，以“?”结束。分别统计其中字母的个数,数字个数和其它符号的个数。
其中字母个数是指大,小写字母的总数，及 A—— Z 和 a —— z；
其中数字指从 0—— 9 范围的数字。
三个统计数字在一行，分别用一个空格隔开，“？”不参与统计。

老旧的机器

题目描述

伟大的工程师阿克蒙德买了一台机器，为了维持这台机器的正常运作，他每年必须花费一定的费用来维修这台机器。但是随着这台机器的使用，机器会损坏更快以至于每年用来维修这台机器的费用都是上一年的 1.5 倍。已知第一年仅需花费 1 元。现在阿克蒙德想知道，如果他想用 n 年，他总共需要花费多少钱来维修这台机器。

灯笼

题目描述

2012 年国庆节的时候，成都人民公园的树上挂了 N 个灯笼来村托节日气氛。现在国庆节结束了，需要将树上的灯笼都取下来。公园将这个任务安排给石室中学的小航。但是小航身高有限，当他不能直接用手取到灯笼的时候，他可以踩到一个 30 厘米高的凳子上试一试。
现在已知每个灯笼到地面的高度，以及小航把手伸直的时候能够达到的最大高度，请帮小航算一下他能够取到灯笼的数目。假设他碰到灯笼，灯笼就可以取下来。

最佳运动员

题目描述

国际运动协会组织了一个评选最佳运动员的活动，评选方式很特殊，只能由网名投票选举，各国的网民可以任选自己喜爱的运动员，得票最高者当选。现在组织者想知道当选者的票数，请你帮他完成。

移动机器人

题目描述

在一个平面直角坐标系上，一个机器人处于某格点（X0,Y0）处，格点的横纵坐标均为整数。有一个遥控器可以让机器人实现9种可能的运动方式，它们依次是：
（1）向左走一个单位；
（2）向右走一个单位；
（3）向上走一个单位；
（4）向下走一个单位；
（5）走到格点（X₀,Y₀）关于X轴的对称点；
（6）走到格点（X₀,Y₀）关于Y轴的对称点；
（7）走到格点（X₀,Y₀）关于原点的对称点；
（8）以格点（X₀,Y₀）与原点的连线为轴，逆时针旋转90度；
（9）以格点（X₀,Y₀）与原点的连线为轴，顺时针旋转90度；
其中，以横坐标X值增大为向右，纵坐标Y值增大为向上。

现在已知机器人的初始位置（X₀,Y₀）以及遥控器此次发出指令的编号 i（i为正整数，并且1 \leq i \leq 9），请你求出机器人执行指令后所到的新位置坐标（X,Y）。

三角形面积

题目描述

如果知道三角形的三边长a ,b ,c ，我们就可以求出该三角形周长的一半 ，进一步使用公式：
计算出该三角形的面积。这个求面积的公式就是著名的海伦公式。
给你三个正实数，如果这三个实数分别作为边长能构成一个三角形，则请你求出这个三角形的面积并输出；如果不能构成三角形，请输出“No.” ，注意引号不能输出。

数字分离

题目描述

给定一个有6位数字的正整数，请你把它每位数字分离出来并求和。

输入格式

输入文件只有一个6位数字的正整数。

输出格式

输出文件有一个正整数，即分离出来每位数字之和。

单词

题目背景

TJOI2013 DAY1 T3

题目描述

小张最近在忙毕业论文设计，所以一直在读论文。一篇论文是由许多单词组成的。
但小张发现一个单词会在论文中出现很多次，他想知道每个单词分别在论文中出现多少次。

输入格式

第一行一个整数 N (N \leq 200)，表示有 N 个单词。接下来 N 行每行一个单词。每个单词都由小写字母（’a’～’z’）组成。
所有单词构成论文（一行一个单词）。

输出格式

输出 N 个整数，第 i 行的数字表示第 i 个单词在文章中出现了多少次。

IO优化模板

为什么要优化IO?请见上一道题志愿者选拔
被此题卡疯的我,写了一个大量优化的IO模板。

普通IO优化

我相信多数同学都是用getchar()+*10,就是下面这个代码:

1
2
3
4
5
6
7

inline void get(int &x) {
    static int t;
    while (!((x = getchar()) >= '0' && x <= '9'))
        ;
    x -= '0';
    while ((t = getchar()) >= '0' && t <= '9') x = x * 10 + t - '0';
}

但*10,getchar(),和-‘0’,是还可以继续优化的。

志愿者选拔

题目描述

西博会马上就要开幕了，电子科技大学组织了一次志愿者选拔活动。
参加志愿者选拔的同学们排队接受面试官们的面试。参加面试的同学们按照先来先面试并且先结束的原则接受面试官们的考查。
面试中每个人的英语口语能力是主要考查对象之一。
作为主面试官的John想知道当前正在接受面试的同学队伍中口语能力值最高的是多少。于是他请你帮忙编写一个程序来计算。

位运算优化

大家都知道OI中TLE是经常碰到的,位运算是优化性能的利器。

swap

1
2
3
4
5

inline void swap(int &a, int &b){
    a ^= b;  
    b ^= a;  
    a ^= b; 
}

简单题

题目背景

CQOI2006 T1

题目描述

有一个 n 个元素的数组，每个元素初始均为 0 。有 m 条指令，要么让其中一段连续序列数字反转——0 变 1，1 变 0（操作1），要么询问某个元素的值（操作2）。例如当 n=20 时，10 条指令如下：

系列操作Ⅱ

题目描述

给出数列 $a_1, a_2,\cdots,a_n(0 \leq a_i \leq 10 ^ 9)$，有关序列的两种操作。

1. $a_l, a_{ l + 1 }, \cdots, a_r(1 \leq l \leq r \leq n)$ 加上 $x(-10 ^ 3 \leq x \leq 10 ^ 3)$
2. 求 $a_i(1 \leq i \leq n)$

输入格式

第一行包含两个数 $n(1 \leq n \leq 10 ^ 5)$ 和 $m(1 \leq m \leq 10 ^ 5)$，表示序列的长度和操作次数。

接下来的一行有 $n$ 个数，以空格隔开，表示 $a_1, a_2, \cdots, a_n$。

接下来的 $m$ 行，每行为有以下两种格式之一：

0 1 r x ，表示 $a_l, a_{l+1},\cdots,a_r$ 加上 $x$。

1 i ，求 $a_i$。

输出格式

对于每次询问，输出单独一行表示答案。

系列操作Ⅰ

题目描述

给出序列 $a_1,a_2, \cdots ,a_n(0 \leq a_i \leq 10^9)$，有关于序列的两种操作：

1. $a_i(1 \leq i \leq n)$ 加上 $x(-10^3 \leq x \leq 10^3)$
2. 求 $max { a_l, a_{l+1}, \cdots ,a_r } (1 \leq l \leq r \leq n)$

输入格式

第一行包含两个数 $n(1 \leq n \leq 10^5)$ 和 $m(1 \leq m \leq 10^5)$,表示序列长度和操作次数。
接下来一行 $n$ 个数，以空格隔开，表示 $a_1, a_2, \cdots, a_n$。
接下来 $m$ 行，每行为以下两种格式之一。

0 i x，表示 $a_i$ 加上 $x$。

1 l r，求 $max{ a_l,a_{l+1}, \cdots, a_r }$。

输出格式

对于每次询问，输出单独一行表示答案。

太空飞行计划

题目描述

W 教授正在为国家航天中心计划一系列的太空飞行。每次太空飞行可进行一系列商业性实验而获取利润。现已确定了一个可供选择的实验集合 E={E1，E2， $\cdots$ ，Em}，和进行这些实验需要使用的全部仪器的集合 I={I1， I2， $\cdots $In}。 实验 Ej 需要用到的仪器是 I 的子集 Rj∈I。配置仪器 Ik 的费用为 Ck 美元。实验 Ej 的赞助商已同意为该实验结果支付 Pj 美元。W 教授的任务是找出一个有效算法， 确定在一次太空飞行中要进行哪些实验并因此而配置哪些仪器才能使太空飞行的净收益最大。这里净收益是指进行实验所获得的全部收入与配置仪器的全部费用的差额。
对于给定的实验和仪器配置情况，编程找出净收益最大的试验计划，输出最大收益值。

没有上司的晚会

题目背景

poj2342

题目描述

Ural 大学有N 个职员，编号为 1~N。他们有从属关系，也就是说他们的关系就像一棵以校长为根的树，父结点就是子结点的直接上司。每个职员有一个快乐指数。现在有个周年庆宴会，要求与会职员的快乐指数最大。但是，没有职员愿和直接上司一起与会。

输入格式

第一行一个整数 N (1<=N<=6000)。
接下来 N 行，第i+1行表示i 号职员的快乐指数Ri(-128<=Ri<=127) 。
接下来 N-1 行，每行输入一对整数 L 和 K。表示 K 是 L 的直接上司
最后一行输入0 0。

输出格式

输出最大的快乐指数。

麻烦的聚餐

题目描述

为了避免餐厅过分拥挤，FJ要求奶牛们分3批就餐。每天晚饭前，奶牛们都会在餐厅前排队入内，按FJ的设想，所有第3批就餐的奶牛排在队尾，队伍的前端由设定为第1批就餐的奶牛占据，中间的位置就归第2批就餐的奶牛了。由于奶牛们不理解FJ的安排，晚饭前的排队成了一个大麻烦。
第i头奶牛有一张标明她用餐批次 D_i(1 <= D_i <= 3) 的卡片。虽然所有 N (1 <= N <= 30,000) 头奶牛排成了很整齐的队伍，但谁都看得出来，卡片上的号码是完全杂乱无章的。 在若干次混乱的重新排队后，FJ找到了一种简单些的方法：奶牛们不动，他沿着队伍从头到尾走一遍，把那些他认为排错队的奶牛卡片上的编号改掉，最终得到一个他想要的每个组中的奶牛都站在一起的队列，例如 111222333 或者 333222111。哦，你也发现了，FJ不反对一条前后颠倒的队列，那样他可以让所有奶牛向后转，然后按正常顺序进入餐厅。
你也晓得，FJ是个很懒的人。他想知道，如果他想达到目的，那么他最少得改多少头奶牛卡片上的编号。所有奶牛在FJ改卡片编号的时候，都不会挪位置。

流星雨

题目描述

茜听说了一个骇人听闻的消息，一场流星雨即将袭击整个农场，由于流星体积过大，它们无法在撞击到地面前燃烧殆尽，届时将会对它撞到的一切东西造成毁灭性的打击。很自然地，贝茜开始担心自己的安全问题。以FJ牧场中最聪明的奶牛的名誉起誓，她一定要在被流星砸到前，到达一个安全的地方（也就是说，一块不会被任何流星砸到的土地）。如果将牧场放入一个直角坐标系中，贝茜现在的位置是原点，并且，贝茜不能踏上一块被流星砸过的土地。
根据预报，一共有 M 颗流星（1 <= M <= 50,000）会坠落在农场上，其中第 i 颗流星会在时刻 T_i （0 <= T_i <= 1,000）砸在坐标为（X_i, Y_i）（0 <= X_i <= 500；0 <= Y_i <= 500）的格子里。流星的力量会将它所在的格子，以及周围 4 个相邻的格子都化为焦土，当然贝茜也无法再在这些格子上行走。
贝茜在时刻 0 开始行动，它只能在第一象限中，平行于坐标轴行动，每 1 个时刻中，她能移动到相邻的（一般是 4 个）格子中的任意一个，当然目标格子要没有被烧焦才行。如果一个格子在时刻 t 被流星撞击或烧焦，那么贝茜只能在 t 之前的时刻在这个格子里出现。请你计算一下，贝茜最少需要多少时间才能到达一个安全的格子。

连线游戏

题目描述

Farmer John 最近发明了一个游戏，来考验自命不凡的贝茜。游戏开始的时候，FJ会给贝茜一块画着 $N(2 \leq N \leq 200)$ 个不重合的点的木板，其中第 $i$ 个点的横,纵坐标分别为 $X_i$ 和 $Y_i (-1000 \leq X_i, Y_i \leq 1000)$。

贝茜可以选两个点画一条过它们的直线，当且仅当平面上不存在与画出直线平行的直线。游戏结束时贝茜的得分，就是她画出的直线的总条数。为了在游戏中胜出，贝茜找到了你，希望你帮她计算一下最大可能得分。

输入格式

第 $1$ 行: 输入 $1$ 个正整数：$N$

第 $2 \cdots N+1$ 行: 第 $i+1$ 行用 $2$ 个用空格隔开的整数 $X_i, Y_i$，描述了点 $i$ 的坐标。

输出格式

输出 $1$ 个整数，表示贝茜的最大得分，即她能画出的互不平行的直线数。

Network of Schools

题目背景

poj1236

题目描述

大致意思: $N(2 < N < 100)$ 各学校之间有单向的网络，每个学校得到一套软件后，可以通过单向网络向周边的学校传输。

问题：初始至少需要向多少个学校发放软件，使得网络内所有的学校最终都能得到软件。至少需要添加几条传输线路(边)，使任意向一个学校发放软件后，经过若干次传送，网络内所有的学校最终都能得到软件。

车厢调度

题目描述

有一个火车站，铁路如图所示，每辆火车从 A 驶入，再从 B 方向驶出，同时它的车厢可以重新组合。假设从 A 方向驶来的火车有 n 节（n<=1000），分别按照顺序编号为 1，2，3， \cdots ，n 。假定在进入车站前，每节车厢之间都不是连着的，并且它们可以自行移动到 B 处的铁轨上。另外假定车站 C 可以停放任意多节车厢。但是一旦进入车站 C，它就不能再回到 A 方向的铁轨上了，并且一旦当它进入 B 方向的铁轨，它就不能再回到车站 C。

负责车厢调度的工作人员需要知道能否使它以 a1,a2, \cdots ,an 的顺序从 B 方向驶出，请来判断能否得到指定的车厢顺序。

表达式括号匹配

题目描述

假设一个表达式有英文字母（小写）,运算符（+，—，*，/）和左右小（圆）括号构成，以“@”作为表达式的结束符。

请编写一个程序检查表达式中的左右圆括号是否匹配，若匹配，则返回“YES”；否则返回“NO”。假设表达式长度小于 255，左圆括号少于 20 个。

输入格式

输入一行，一个表达式。

输出格式

如果括号匹配，输出“YES”,否则输出“NO”。

统计难题

题目背景

HDU 1251

题目描述

Ignatius 最近遇到一个难题，老师交给他很多单词(只有小写字母组成，不会有重复的单词出现)，现在老师要他统计出以某个字符串为前缀的单词数量(单词本身也是自己的前缀)。

输入格式

输入数据的第一部分是一张单词表（不超过 $10^4$ 个单词），每行一个单词，单词的长度不超过 10，它们代表的是老师交给 Ignatius 统计的单词，一个空行代表单词表的结束。第二部分是一连串的提问，每行一个提问，每个提问都是一个字符串（不超过 $10^4$ 个提问串）。
注意:本题只有一组测试数据，处理到文件结束。

Phone List

题目背景

HDU 1671

题目描述

给出一份电话号码列表，如果不存在有一个号码是另一个号码的前缀，我们就说这份电话号码列表是合法的。让我们看看如下号码列表：

1. Emergency 911
2. Alice 97625999
3. Bob 91125426

在这组号码中，我们不能拨通 Bob 的电话，因为当你按下 Bob 电话号码的前 $3$ 个数字 911 时，电话局会把你的拨号连接到 Emergency 的线路。

所以这组号码是不合法的。

SPFA

SPFA（Shortest Path Faster Algorithm）（队列优化）算法是求单源最短路径的一种算法，它还有一个重要的功能是判负环（在差分约束系统中会得以体现），在Bellman-ford算法的基础上加上一个队列优化，减少了冗余的松弛操作，是一种高效的最短路算法。

Dijkstra

迪杰斯特拉算法是由荷兰计算机科学家狄克斯特拉于1959 年提出的，因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法，解决的是有向图中最短路径问题。迪杰斯特拉算法主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。

分析

二分答案题,先按绳子的长度进行升序排列,然后for循环二分100次就够了,避免while造成死循环,在 $O(n)$ 内枚举进行判断,所以时间复杂度为 $O(n \log n)$。
注意:一定要用double,float精度太低,否则直接wrong answer

最长子串

题目描述

给出一个全部由小写字母构成的字符串，要求从该串中找出满足下面条件的最长子串：

条件1：子串是连续的；

条件2：子串的长度是偶数；

条件3：沿子串的中心切开，对左右两部分的串按顺序进行比较，要求不同的字符对数 $N$ 不超过题目给出的一个限定值 $D$。
比如：abcaec 的 $N$ 值为 $1$。因为平分的两部分 abc 和 aec 比较，只有 $1$ 对字符不同：即 b 和 e，而其余字符都相同。

Aggressive cows

题目背景

POJ2456

题目描述

农夫约翰搭了一间有 N 间牛舍的小屋。牛舍排在一条线上，第 i 号牛舍在 $X_i$ 的位置。但是他的 M 头牛对小屋很不高兴，因此经常互相攻击。约翰为了防止牛之间互相伤害，因此决定把每头牛都放在离其他牛尽可能远的牛舍。也就是要最大化最近的两头牛之间的距离。

输入格式

输入第一行: 两个正整数 N 和 M。
接下来 N 行，每行一个整数 $X_i$。

输出格式

一个整数，即最近的两头牛之间的最大距离。

选数问题

题目描述

在给定的 $N$ 个数中选出 $R \times C$ 个数，然后填入 $R \times C$ 的矩阵中，每一行的 $D(i)$ 定义为本行最大值与最小值的差，然后要令所有行中 $D(i)$ 的最大值 $F$ 尽量小，其中 $1 \leq i \leq R$。请你求出满足条件的 $F$。

输入格式

第一行是三个整数：$N, R, C$，其中, $1 \leq R,C \leq 10^4$，$R \times C \leq N \leq 5 \times 10^5$。
第二行是 $N$ 个整数 $P_i$，$0 < P_i \leq 10^9$

输出格式

输出一个整数，即满足条件的最小的 $F$。

传递消息

题目背景

POJ 1125

题目描述

股票经纪人以对传闻的准确判断而闻名。你已签定一个合同，就是研究一种方法，在股票经纪人中间传播假情报，以便雇主在股票市场中赢得先机。为了得到最大效益，你必须尽可能快地散布传闻。

不幸的是，股票经纪人只信任来自他们“可靠来源”的消息。这意味着，在散播传闻时，你必须考虑他们所接触的人际关系。某个股票经纪人需要花一些时间把传闻传递给他的每一位同事。你的任务是写一个程序，确定从哪个证券经纪人开始散播传闻最快，以及传闻传递到整个证券界时所需要最少时间。这个时间是指最后一个人收到传闻的时间。
每个股票经纪人从1开始编号，一直到股票经纪人的总数。