NOI 2004 练习
辉辉的一天
【题目描述】
辉辉、姗姗和佳佳是好朋友，他们一起参加了在湖南长沙长郡中学举办的第二十一届全国青少年信息学奥林匹克竞赛（NOI2004）。他们很早就来到了长沙，可是报名还没有开始。怎么办呢？他们决定分头出去玩一天，晚上回到宿舍以后给大家说说自己这一天做了什么有意义的事情。
你一定想不到辉辉干嘛去了——他睡了一天。他想：“比赛前几天老是写程序到深夜，头晕晕的……没关系，好好睡一觉，然后我会精神抖擞。醒了之后，我要做有意义的事情。”这一睡可不得了，辉辉从早上a点b分c秒一直睡到了下午d点e分f秒。他睡了多少秒钟呢？
【输入文件】
输入文件huihui.in仅包含六个非负整数a, b, c, d, e, f(1<=a, d<=11, 0<=b, c, e, f<=59)。例如，a=6, b=5, c=4, d=3, e=2, f=1表示辉辉从06:05:04睡到15:02:01。
【输出文件】
输出文件huihui.out仅包含一个整数s，即辉辉睡觉的总秒数。
【样例输入】
6 5 4 3 2 1
【样例输出】
32217
第十届全国青少年信息学奥林匹克联赛复赛试题
（ 提高组 三小时完成 ）
津津的储蓄计划
(save.pas/dpr/c/cpp)
【问题描述】
津津的零花钱一直都是自己管理。每个月的月初妈妈给津津300元钱，津津会预算这个月的花销，并且总能做到实际花销和预算的相同。
为了让津津学习如何储蓄，妈妈提出，津津可以随时把整百的钱存在她那里，到了年末她会加上20%还给津津。因此津津制定了一个储蓄计划：每个月的月初，在得到妈妈给的零花钱后，如果她预计到这个月的月末手中还会有多于100元或恰好100元，她就会把整百的钱存在妈妈那里，剩余的钱留在自己手中。
例如11月初津津手中还有83元，妈妈给了津津300元。津津预计11月的花销是180元，那么她就会在妈妈那里存200元，自己留下183元。到了11月月末，津津手中会剩下3元钱。
津津发现这个储蓄计划的主要风险是，存在妈妈那里的钱在年末之前不能取出。有可能在某个月的月初，津津手中的钱加上这个月妈妈给的钱，不够这个月的原定预算。如果出现这种情况，津津将不得不在这个月省吃俭用，压缩预算。
现在请你根据2004年1月到12月每个月津津的预算，判断会不会出现这种情况。如果不会，计算到2004年年末，妈妈将津津平常存的钱加上20%还给津津之后，津津手中会有多少钱。
【输入文件】
输入文件save.in包括12行数据，每行包含一个小于350的非负整数，分别表示1月到12月津津的预算。
【输出文件】
输出文件save.out包括一行，这一行只包含一个整数。如果储蓄计划实施过程中出现某个月钱不够用的情况，输出-X，X表示出现这种情况的第一个月；否则输出到2004年年末津津手中会有多少钱。
【样例输入1】
290
230
280
200
300
170
340
50
90
80
200
60
【样例输出1】
-7
【样例输入2】
290
230
280
200
300
170
330
50
90
80
200
60
【样例输出2】
1580
NOI 2002 DAY0
观察家小明
【问题描述】
小明虽然只有三岁，但是很喜欢数数。有一天，他在一张纸上写了一列两两不同的数。“这些不是一列一般的数，它们是有一定规律的。”小明认真的说。
“经过仔细的观察，你就会发现这些数里隐藏了很多三重逆序数对。所谓三重逆序数对就是指在这列数a1,a2,a3. . .an中，对i<j<k，有ai>aj>ak，那么数对(ai,aj,ak)就称为三重逆序数对。”小明说完后，硬拉着你帮他数一数，他写的数里究竟有多少三重逆序数对。
【输入文件】
输入文件triple.in的第一行包含一个整数N(1<=N<=100)，即小明写的数的个数。以下N行每行包含一个整数，代表小明所写的一列正整数，不大于30000。
【输出文件】
输出文件triple.out仅包含一个整数M，即小明所写的数中，三重逆序数对的组数。
【样例输入】
6
6
1
2
5
3
4
【样例输出】
2
NOI2002 第一天
银河英雄传说
【问题描述】
公元五八○一年，地球居民迁移至金牛座α第二行星，在那里发表银河联邦创立宣言，同年改元为宇宙历元年，并开始向银河系深处拓展。
宇宙历七九九年，银河系的两大军事集团在巴米利恩星域爆发战争。泰山压顶集团派宇宙舰队司令莱因哈特率领十万余艘战舰出征，气吞山河集团点名将杨威利组织麾下三万艘战舰迎敌。
杨威利擅长排兵布阵，巧妙运用各种战术屡次以少胜多，难免恣生骄气。在这次决战中，他将巴米利恩星域战场划分成30000列，每列依次编号为1, 2, …, 30000。之后，他把自己的战舰也依次编号为1, 2, …, 30000，让第i号战舰处于第i列(i = 1, 2, …, 30000)，形成“一字长蛇阵”，诱敌深入。这是初始阵形。当进犯之敌到达时，杨威利会多次发布合并指令，将大部分战舰集中在某几列上，实施密集攻击。合并指令为M i j，含义为让第i号战舰所在的整个战舰队列，作为一个整体（头在前尾在后）接至第j号战舰所在的战舰队列的尾部。显然战舰队列是由处于同一列的一个或多个战舰组成的。合并指令的执行结果会使队列增大。
然而，老谋深算的莱因哈特早已在战略上取得了主动。在交战中，他可以通过庞大的情报网络随时监听杨威利的舰队调动指令。
在杨威利发布指令调动舰队的同时，莱因哈特为了及时了解当前杨威利的战舰分布情况，也会发出一些询问指令：C i j。该指令意思是，询问电脑，杨威利的第i号战舰与第j号战舰当前是否在同一列中，如果在同一列中，那么它们之间布置有多少战舰。
作为一个资深的高级程序设计员，你被要求编写程序分析杨威利的指令，以及回答莱因哈特的询问。
最终的决战已经展开，银河的历史又翻过了一页……
【输入文件】
输入文件galaxy.in的第一行有一个整数T（1<=T<=500,000），表示总共有T条指令。
以下有T行，每行有一条指令。指令有两种格式：
1. M i j ：i和j是两个整数（1<=i , j<=30000），表示指令涉及的战舰编号。该指令是莱因哈特窃听到的杨威利发布的舰队调动指令，并且保证第i号战舰与第j号战舰不在同一列。
2. C i j ：i和j是两个整数（1<=i , j<=30000），表示指令涉及的战舰编号。该指令是莱因哈特发布的询问指令。
【输出文件】
输出文件为galaxy.out。你的程序应当依次对输入的每一条指令进行分析和处理：
如果是杨威利发布的舰队调动指令，则表示舰队排列发生了变化，你的程序要注意到这一点，但是不要输出任何信息；
如果是莱因哈特发布的询问指令，你的程序要输出一行，仅包含一个整数，表示在同一列上，第i号战舰与第j号战舰之间布置的战舰数目。如果第i号战舰与第j号战舰当前不在同一列上，则输出-1。
【样例输入】
4
M 2 3
C 1 2
M 2 4
C 4 2
【样例输出】
-1
1
【样例说明】
战舰位置图：表格中阿拉伯数字表示战舰编号
第一列 第二列 第三列 第四列 ……
初始时 1 2 3 4 ……
M 2 3 1 3
2 4 ……
C 1 2 1号战舰与2号战舰不在同一列，因此输出-1
M 2 4 1 4
3
2 ……
C 4 2 4号战舰与2号战舰之间仅布置了一艘战舰，编号为3，输出1
2003 NOI DAY1
木棒游戏
【问题描述】
这是一个很古老的游戏。用木棒在桌上拼出一个不成立的等式，移动且只移动一根木棒使得等式成立。现在轮到你了。
【任务】
从文件读入一个式子（该式子肯定是一个不成立的等式）。
如果移动一根木棒可以使等式成立，则输出新的等式，否则输出No。
【说明和限制】
1．式子中的数可能是正数或负数，运算符号只会出现加号和减号，并且有且仅有一个等号，不会出现括号、乘号或除号，也不会有++,--,+-或-+出现。
2．式子中不会出现8个或8个以上的连续数字（数的绝对值小于等于9999999）。
3．你只能移动用来构成数字的木棒，不能移动构成运算符（+、-、=）的木棒，所以加号、减号、等号是不会改变的。移动前后，木棒构成的数字必须严格与图2中的0~9相符。
4．从文件读入的式子中的数不会以0开头，但允许修改后等式中的数以数字0开头。
【输入数据】
从文件game.in中读入一行字符串。该串中包括一个以“#”字符结尾的式子（ASCII码35)，式子中没有空格或其他分隔符。输入数据严格符合逻辑。字符串的长度小于等于1000。
注意：“#”字符后面可能会有一些与题目无关的字符。
【输出数据】
将输出结果存入文件game.out，输出仅一行。
如果有解，则输出正确的等式，格式与输入的格式相同（以“#”结尾，中间不能有分隔符，也不要加入多余字符）。此时输入数据保证解是唯一的。
如果无解，则输出“No”（N大写，o小写）。
【输入样例1】
1+1=3#
【输出样例1】
1+1=2#
【输入样例2】
1+1=3+5#
【输出样例2】
No
【输入样例3】
11+77=34#
【输出样例3】
17+17=34#
文本编辑器
【问题描述】
很久很久以前，DOS3.x的程序员们开始对EDLIN感到厌倦。于是，人们开始纷纷改用自己写的文本编辑器……
多年之后，出于偶然的机会，小明找到了当时的一个编辑软件。进行了一些简单的测试后，小明惊奇地发现：那个软件每秒能够进行上万次编辑操作（当然，你不能手工进行这样的测试）！于是，小明废寝忘食地想做一个同样的东西出来。你能帮助他吗？
为了明确任务目标，小明对“文本编辑器”做了一个抽象的定义：
文本：由0个或多个字符构成的序列。这些字符的ASCII码在闭区间[32, 126]内，也就是说，这些字符均为可见字符或空格。
光标：在一段文本中用于指示位置的标记，可以位于文本的第一个字符之前，文本的最后一个字符之后或文本的某两个相邻字符之间。
文本编辑器：为一个可以对一段文本和该文本中的一个光标进行如下六条操作的程序。如果这段文本为空，我们就说这个文本编辑器是空的。
操作名称 输入文件中的格式 功能
MOVE(k) Move k 将光标移动到第k个字符之后，如果k=0，将光标移到文本第一个字符之前
INSERT(n, s) Insert n¿
S 在光标后插入长度为n的字符串s，光标位置不变，n ³ 1
DELETE(n) Delete n 删除光标后的n个字符，光标位置不变，n ³ 1
GET(n) Get n 输出光标后的n个字符，光标位置不变，n ³ 1
PREV() Prev 光标前移一个字符
NEXT() Next 光标后移一个字符
比如从一个空的文本编辑器开始，依次执行操作INSERT(13, “Balanced□tree”)，MOVE(2)，DELETE(5)，NEXT()，INSERT(7, “□editor”)，MOVE(0)，GET(15)后，会输出“Bad□editor□tree”，如下表所示：
操作 操作前的文本 操作后的结果
INSERT(13, “Balanced□tree”) |
（只有光标，文本为空） |Balanced□tree
MOVE(2) |Balanced□tree Ba|lanced□tree
DELETE(5) Ba|lanced□tree Ba|d□tree
NEXT() Ba|d□tree Bad|□tree
INSERT(7, “□editor”)， Bad|□tree Bad|□editor□tree
MOVE(0) Bad|□editor□tree |Bad□editor□tree
GET(15) |Bad□editor□tree 输出“Bad□editor□tree”
上表中，“|”表示光标，“□”表示空格。
你的任务是：
建立一个空的文本编辑器。
从输入文件中读入一些操作指令并执行。
对所有执行过的GET操作，将指定的内容写入输出文件。
【输入文件】
输入文件editor.in的第一行是指令条数t，以下是需要执行的t个操作。其中：
为了使输入文件便于阅读，Insert操作的字符串中可能会插入一些回车符，请忽略掉它们（如果难以理解这句话，可以参考样例）。
除了回车符之外，输入文件的所有字符的ASCII码都在闭区间[32, 126]内。且行尾没有空格。
这里我们有如下假定：
MOVE操作不超过50000个，INSERT和DELETE操作的总个数不超过4000，PREV和NEXT操作的总个数不超过200000。
所有INSERT插入的字符数之和不超过2M（1M=1024*1024），正确的输出文件长度不超过3M字节。
DELETE操作和GET操作执行时光标后必然有足够的字符。MOVE、PREV、NEXT操作不会把光标移动到非法位置。
输入文件没有错误。
对C++选手的提示：经测试，对最大的测试数据使用fstream进行输入有可能会比使用stdio慢约1秒，因此建议在可以的情况下使用后者。
【输出文件】
输出文件editor.out的每行依次对应输入文件中每条GET指令的输出。
【样例输入】
15
Insert 26
abcdefghijklmnop
qrstuv wxy
Move 15
Delete 11
Move 5
Insert 1
^
Next
Insert 1
_
Next
Next
Insert 4
.\/.
Get 4
Prev
Insert 1
^
Move 0
Get 22
【样例输出】
.\/.
abcde^_^f.\/.ghijklmno
NOI 2004 day 1
郁闷的出纳员
【问题描述】
OIER公司是一家大型专业化软件公司，有着数以万计的员工。作为一名出纳员，我的任务之一便是统计每位员工的工资。这本来是一份不错的工作，但是令人郁闷的是，我们的老板反复无常，经常调整员工的工资。如果他心情好，就可能把每位员工的工资加上一个相同的量。反之，如果心情不好，就可能把他们的工资扣除一个相同的量。我真不知道除了调工资他还做什么其它事情。
工资的频繁调整很让员工反感，尤其是集体扣除工资的时候，一旦某位员工发现自己的工资已经低于了合同规定的工资下界，他就会立刻气愤地离开公司，并且再也不会回来了。每位员工的工资下界都是统一规定的。每当一个人离开公司，我就要从电脑中把他的工资档案删去，同样，每当公司招聘了一位新员工，我就得为他新建一个工资档案。
老板经常到我这边来询问工资情况，他并不问具体某位员工的工资情况，而是问现在工资第k多的员工拿多少工资。每当这时，我就不得不对数万个员工进行一次漫长的排序，然后告诉他答案。
好了，现在你已经对我的工作了解不少了。正如你猜的那样，我想请你编一个工资统计程序。怎么样，不是很困难吧？
【输入文件】
第一行有两个非负整数n和min。n表示下面有多少条命令，min表示工资下界。
接下来的n行，每行表示一条命令。命令可以是以下四种之一：
名称 格式 作用
I命令 I_k 新建一个工资档案，初始工资为k。如果某员工的初始工资低于工资下界，他将立刻离开公司。
A命令 A_k 把每位员工的工资加上k
S命令 S_k 把每位员工的工资扣除k
F命令 F_k 查询第k多的工资
_（下划线）表示一个空格，I命令、A命令、S命令中的k是一个非负整数，F命令中的k是一个正整数。
在初始时，可以认为公司里一个员工也没有。
【输出文件】
输出文件的行数为F命令的条数加一。
对于每条F命令，你的程序要输出一行，仅包含一个整数，为当前工资第k多的员工所拿的工资数，如果k大于目前员工的数目，则输出-1。
输出文件的最后一行包含一个整数，为离开公司的员工的总数。
【样例输入】
9 10
I 60
I 70
S 50
F 2
I 30
S 15
A 5
F 1
F 2
【样例输出】
10
20
-1
2
【约定】
I命令的条数不超过100000
A命令和S命令的总条数不超过100
F命令的条数不超过100000
每次工资调整的调整量不超过1000
新员工的工资不超过100000
【评分方法】
对于每个测试点，如果你输出文件的行数不正确，或者输出文件中含有非法字符，得分为0。
否则你的得分按如下方法计算：如果对于所有的F命令，你都输出了正确的答案，并且最后输出的离开公司的人数也是正确的，你将得到10分；如果你只对所有的F命令输出了正确答案，得6分；如果只有离开公司的人数是正确的，得4分；否则得0分。
