Sample Input Sample Output 3 30 1 3 10 4 6 20 2 5 25
题35。Pascal山脉
Problem 小卡卡顺着老者所指的方向,来到了Pascal神峰的顶峰。老者告诉小卡卡,Pascal山脉有很多座山, 都排在一条直线上,每座山都有不同的高度。Pascal山的山顶有一个神奇的洞穴,进入这个洞穴后,你将会到达这座山前方的另一座山,更加神奇的是,你到达的山一定比他所在的山高度要小。而Pascal圣地最大的宝藏就藏在某一座Pascal山上的洞穴中,这个洞穴的特点是它有一道石门封闭着。小卡卡很想知道进入每座山的洞穴后,他所到达的不同的山会有多少种可能。
Input 第一行一个整数n,表示山的个数.(1<=n<=20000) 第二行有n个整数，从前到后给出每座山的高度。另外两座山可以有相同的高度. (1<=每座山的高度<=maxlongint)
Output共一行n个整数，互相以一个空格分隔。.第i个整数表示他进入第i号山的洞穴后能够到达的不同的山的个数.
Sample Input Sample Output 5 0 1 2 3 4 1 2 3 4 5
题36。光荣的梦想
Problem 依次给出n个整数序列，每次只能交换相邻两个数，问最少需要交换几次才能使整个序列有序。
Input第一行为数列中数的个数n<= 10000,第二行为n个数。表示当前数列的状态。 Output输出一个整数，表示最少需要交换几次能达到升序状态。 Sample Input Sample Output 4 2 2 1 4 3
题37。象形文字hie.pas/hie.exe
【题目描述】光光回到家，完成了双休日的作业，就开始看书，光光对历史非常感兴趣，于是光光就开始看一本古印度的书。书上面印了很多的象形文字，为了叙述简便，我们把每一种形状的象形文字抽象成为一个1到70的数字，比如有这么一串文字：1 27 50 27 29,光光好像看出了什么,觉得如果添加上若干个文字之后，就能够成为一个回文的一句话。比如上面一句话最少需要添加两个字才能变为回文的一句话。添加方法分别为：
（1）方法1：1 29 27 50 27 29 1,或 （2）方法2：29 1 27 50 27 1 29
我们可以知道，给定一句话，通过添加若干个字符是可以成为一个回文句子的。因此，光光需要知道，他最少需要添加多少个文字，才能使这句话变成回文的?
【输入格式】输入文件hie.in包含以下内容：第一行:一个数字n，代表原句有n个字符。第二行:n个数字，代表这句话的内容。
【输出格式】输出文件hie.out包含一行，代表了最少添加文字的个数。 【样例输入】 【样例输出】 5 2 1 27 50 27 29 【数据规模】
30%的数据中，n<=200; 100%的数据中，n<=5000;
题42。[Sense of Beauty] http://acm.timus.ru/problem.aspx?space=1&num=1501 【问题描述】有两堆卡片，每堆卡片有n（4≤n≤1000）张，所有卡片中有n张是红色的，n张是蓝色的。现在要将卡片逐张取下，红的放在一起，蓝的放在一起，每堆卡片中只能取最上面的那张，且要求任意时刻，已取得的红色卡片数和蓝色卡片数相差不超过1张，问如何取，才能完成任务？ 【输入】第一行一个整数n，表示每堆卡片的张数。第二行有n个字符，表示第一堆的卡片颜色，第三行有n个字符，表示第二堆的卡片颜色。其中0代表红色，1代表蓝色，每行的第1个字符代表最上面的卡片颜色，第n个字符代表最下面的卡片颜色。
【输出】一行共2n个字符，表示一种取卡片的方案，如果有多种可行方案，只要输出任意一种即可。其中字符1代表取自第一堆，字符2代表取自第二堆。如果不存在可行方案，则输出一行“Impossible”。 【样例输入1】 4 0011 0110
【样例输出1】 22121112
【样例输入2】 4 1100 1100
【样例输出2】 Impossible
题43。[Fiscal operations] http://acm.timus.ru/problem.aspx?space=1&num=1511 【问题描述】有三个整数A、B、C，1≤A≤101000，1≤B≤101000，1≤C≤101000），如何改变A、B、
C的某些位，使得A+B=C？改变一个数的某位的代价，为该位改变前后数字的差的绝对值。最终的代价为所有位的代价之和。你不能使三个数中的任一个减少位数（使最高位变0），也不能增加位数（在最高位前增加若干位）。
【输入】第一行一个整数A（1≤A≤101000），第二行一个整数B（1≤B≤101000），第三行一个整数C（1≤C≤101000）。
【输出】一个整数，表示最小代价。如果无论怎样改变，A+B都不能等于C，则输出“-1”。 【样例输入】 123 554 345
【样例输出】 8
【样例说明】
可以将A变为121，代价2，将B变为324， 代价5，将C变为445，代价1，总代价为8。
题44。[K-inversions] http://acm.timus.ru/problem.aspx?space=1&num=1523 【问题描述】给出一个排列a1,a2,…,an（所有的ai均为1至n之间的互不相同的整数）。如果1≤i1
【输入】第一行二个正整数n和k，互相间以一个空格分隔。1≤n≤2000（原题中为20000）， 2≤k≤10。第二行有n个整数，表示给出的一个排列。
【输出】一个整数，表示长度为K的递减子序列数除以109后的余数。 【样例输入1】 3 2 3 1 2
【样例输出1】 2
【样例输入2】 5 3
5 4 3 2 1
【样例输出2】 10
题45。[Ents] http://acm.timus.ru/problem.aspx?space=1&num=1537 【问题描述】艾尔夫教会一只蚂蚁两个单词。以后，蚂蚁按照以下方法学习单词：
1)艾尔夫已经教过的蚂蚁会选没有掌握任何单词的一只老蚂蚁和一只年轻蚂蚁，让他们学会自己掌握的所有单词。
2)上一步学习过的蚂蚁中，艾尔夫教会老蚂蚁一个新单词，教会年轻蚂蚁的单词数等于它已经掌握的单词数。
3)艾尔夫教过的蚂蚁，不能再进一步学习新的单词。
蚂蚁的数量有足够多，请问有多少只蚂蚁掌握了K个单词？
【输入】第一行二个正整数K和P，互相间以一个空格分隔。K≤107， P≤109。 【输出】一个整数，表示掌握K个单词的蚂蚁数量除以P的余数。 【样例输入】 4 10
【样例输出】 2
题46。[Martian army] http://acm.timus.ru/problem.aspx?space=1&num=1472
【问题描述】有n个点，连成一棵树，每个节点处有一个权值，树根为1号点，权值为1，树叶处权值为0，其余点处的权值为一些未知的实数。除了树根外，所有点的父结点编号小于该点的编号。树中每条边有一个权值。比如，权值为Aij连接点I和点j，点I和点j处的权值分别为Bi和Bj，则在边ij处能得到一个乘积|Bi-Bj|*Aij（与边相连的两点处权值之差的绝对值，乘上边上的权值），求如何安排各点处的值，使所有边上乘积之和最小。 【输入】第一行一个整数n（2≤n≤100000）。第二行起至n行共n-1行，每行有二个整数。第i行的二个整数Ki和Ci，表示第i点的父结点为Ki点，i与Ki间的边上的权值为Ci。（1≤Ki 【输出】一个整数，表示求得的最小值（保留两位小数）。 【样例输入】 7 1 10 2 5 2 3 3 1 3 2 3 3 【样例输出】 8.00 题47。[E-mail] http://acm.timus.ru/problem.aspx?space=1&num=1577 【问题描述】已知两个由小写英文构成的字符串A和B，求长度最小的字符串C，使得A和B均为C的子串。 【输入】二行，每行一个字符串，表示原串A和B。 【输出】一个整数，表示长度最小的符合条件的字符串的个数，要求输出所求得值除以109 + 7后的值。 【样例输入1】 b ab 【样例输出1】 1 【样例输入2】 abcab cba 【样例输出2】 4 【提示】样例2的情况时，所求的最小字符串长度为4，共5个字符串，它们为abcaba或abcbab或 acbcab或 cabcab 题48。[Eating High] http://acm.timus.ru/problem.aspx?space=1&num=1570 【问题描述】你和你的朋友共m个人去餐厅吃饭，餐厅中共有n种食品，每种食品能填饱不同数量的肚子，当然每种食品的价格也是不同的。你想让你们所有人都吃饱，又想花费最少的钱。 【输入】第一行只有两个整数N和M。N表示食品数，M表示就餐人数。(1 ≤ N ≤ 100; 1 ≤ M ≤ 20) 以下N行描述N种食品。其中第k+1行有以两个空格分隔的数据Sk Pk Nk，它们分别表示第k种食品：名称为Sk（1至30个的小写英文字母），价格为Pk（1至10000之间），每个能填饱Nk个人的肚子（Nk在0.1至10.0之间，最多三位小数）。 【输出】第一行一个整数，表示最少的钱数。 第二行起的若干行表示最少钱数时的订单，每行表示订制的一种食品，包括食品名称和食品份数，互相间以一个空格分隔。相同的食品不能放在不同行输出，如果有多种方案，则输出食品数最多的一种方案即可。 【样例输入】 4 6 pizza 320 2.4 turkey 1050 3.5 lasagna 150 0.9 pasta 75 0.45 【样例输出】 865 pizza 2 lasagna 1 pasta 1 题49。[三素数数] http://acm.timus.ru/problem.aspx?space=1&num=1586 【问题描述】如果一个数的所有连续三位数字都是大于100的素数，则该数称为三素数数。比如113797是一个6位的三素数数。 【输入】一个整数n（3 ≤ n ≤ 10000），表示三素数数的位数。 【输出】一个整数，表示n位三素数的个数m，要求输出m除以109 + 9的余数。 题50。矿工配餐 IOI2007 Day2第1题 现有两个煤矿，每个煤矿都雇用一组矿工。采煤工作很辛苦，所以矿工们需要良好饮食。每当一辆食品车到达煤矿时，矿工们便会产出一定数量的煤。有三种类型的食品车：肉车，鱼车和面包车。 矿工们喜欢变化的食谱。如果提供的食品能够不断变化，他们的产煤量将会增加。每当一个新的食品车到达煤矿时，矿工们就会比较这种新的食品和前两次（或者少于两次，如果前面运送食品的次数不足两次）的食品，并且： 如果这几次食品车都是同一类型的食品，则矿工们产出一个单位的煤。 如果这几次食品车中有两种不同类型的食品，则矿工们产出两个单位的煤。 如果这几次食品车中有三种不同类型的食品，则矿工们产出三个单位的煤。 预先已知食品车的类型及其被配送的顺序。通过确定哪车食品送到哪个煤矿可以影响产煤量。食品车不能被拆分，每个食品车必须被全部送到一个或另一个煤矿。两个煤矿也并不要求接收相同数量的食品车（事实上，也允许将所有食品车都送到一个煤矿）。 任务 给出食品车的类型及其被配送的顺序，要求你写一个程序，确定哪个食品车应被送到煤矿1，哪个食品车应被送到煤矿2，以使得两个煤矿的产煤量的总和最大。 输入 输入的第一行包含一个整数N (1 ≤ N ≤ 100 000), 表示食品车的数目。 第二行包含一个由N个字符组成的字符串，按照配送顺序依次表示食品车配送的食品的类型。每个字符是以下三个大写字母之一：'M' (表示肉类), 'F' (表示鱼类) 或 'B' (表示面包)。 输出 输出一个整数，表示最大的总产煤量。 评分 在45分的测试数据中，食品车的数目至多为20。 提交时的反馈细节 在竞赛中，对于这个题目，你可以选择至多10次提交在部分正式测试数据上进行测评。测评结束后，可以从竞赛系统中得到关于测试结果的总结。 样例 Input input 6 16 MBMFFB MMBMBBBBMMMMMBMB output output 12 29 在左边的例子中，可以按照如下的顺序运送食品车：煤矿 1, 煤矿 1, 煤矿 2, 煤矿 2, 煤矿 1, 煤矿 2, 依次产生的产煤量为1, 2, 1, 2, 3 和 3 个单位，一共是12 个单位。还有其它运送方式也能产生上述最大总和的产煤量。 （王宏译，李文新校）