除了 Problem 3, 《建筑抢修》的时限为 2s 之外，所有试题的时限均为 1s

 

Problem 1  合金

标志： metal.*

试题描述：

某公司加工一种由铁、铝、锡组成的合金。他们的工作很简单。首先进口一些铁铝锡合金原材料，不同种类的原材料中铁铝锡的比重不同。然后，将每种原材料取出一定量，经过融解、混合，得到新的合金。新的合金的铁铝锡比重为用户所需要的比重。

现在，用户给出了 n 种他们需要的合金，以及每种合金中铁铝锡的比重。公司希望能够订购最少种类的原材料，并且是用这些原材料可以加工出用户需要的所有种类的合金。

 

输入文件的第一行是两个整数 m 和 n ， (m, n <= 500) ，分别表示原材料种数和用户需要的合金种数。

第 2 到 m+1 行，每行三个实数 a, b, c, (a, b, c >= 0 且 a+b+c = 1) ，分别表示铁铝锡在一种原材料中所占的比重。

第 m+2 到 m+n+1 行，每行三个实数 a, b, c, (a, b, c >= 0 且 a+b+c = 1) ，分别表示铁铝锡在一种用户需要的合金中所占的比重。

输出一个整数，表示最少需要的原材料种数。若无解，则输出 -1 。

输入样例：

3 2

0.25 0.25 0.5

0 0.5 0.5

1 0 0

0.7 0.1 0.2

0.85 0.05 0.1

 

输出样例：

2

 

 

 

Problem 2  麻将

标志： mahjong.*

问题描述：

麻将是中国传统的娱乐工具之一。麻将牌的牌可以分为字牌（共有东南西北中发白七种）和序数牌（分为条子饼子万字三种花色，每种花色各有一到九的九种牌），每种牌各四张。在麻将中，通常情况下一组和了的牌（即完成的牌）由十四张牌组成。十四张牌中的两张组成对子（即完全相同的两张牌），剩余的十二张组成三张一组的四组，每一组需为顺子（即同花色且序数相连的序数牌，例如条子三四五），或者是刻字（即完全相同的三张牌）。一组听牌的牌是指一组十三张牌，且再加上某一张牌就可以组成和牌。那一张加上的牌可以成为等待牌。

在这里，我们考虑一种特殊的麻将。在这种特殊的麻将里，没有字牌，花色也只有一种。但是，序数不被限制在一到九的范围内，而是在 1 到 n 的范围内。同时，也没有每一种牌四张的限制。一组和了的牌由 3m +2 张牌组成，其中两张组成对子，其余 3m 张组成三张一组的 m 组，每组需为顺子或刻字。先给出一组 3m +1 张的牌，要求判断该组牌是否为听牌（即还差一张就可以和牌）。如果是的话，输出所有可能的等待牌。

 

输入文件包含两行。第一行包含两个由空格隔开的整数 n, m (9 <= n <= 400, 4 <= m <= 1000) ，第二行包含 3m +1 个由空格隔开的整数，每隔数均在范围 1 到 n 内。这些数代表要求判断听牌的牌的序数。

输出为一行。如果该组牌为听牌，则输出所有的可能的等待牌的序数，数字之间用一个空格隔开。所有的序数须按从小到大的顺序输出。如果该组牌不是听牌，则输出 ”NO”.

 

输入样例：

9 4

1 1 2 2 3 3 5 5 5 7 8 8 8

 

输出样例：

6 7 9

 

 

 

Problem 3  建筑抢修

标志： repair.*

问题描述：

小刚在玩 JSOI 提供的一个称之为“建筑抢修”的电脑游戏。

经过了一场激烈的战斗， T 部落消灭了所有 z 部落的入侵者。但是 T 部落的基地里已经有 N 个建筑设施受到了严重的损伤，如果不尽快修复的话，这些建筑设施将会完全毁坏。

现在的情况是： T 部落基地里只有一个修理工人。虽然它能瞬间到达任何一个建筑，但是修复每个建筑都需要一定的时间。同时，修理工人修理完一个建筑才能修理下一个建筑，不能同时修理多个建筑。如果某个建筑在一段时间之内没有完全修理完毕，这个建筑就报废了。

你的任务是帮小刚合理的制定一个修理顺序，以抢修尽可能多的建筑。

 

输入文件第一行是一个整数 N ，接下来 N 行每行两个整数 T1, T2 描述一个建筑：修理这个建筑需要 T1 秒，如果在 T2 秒之内还没有修理完成，这个建筑就报废了。

输出文件只有一行，是一个整数 S ，表示最多可以抢修 S 个建筑。

N < 150,000;  T1 < T2 < maxlongint

 

样例输入：

4

100 200

200 1300

1000 1250

2000 3200

 

样例输出：

3

 

 

 

Problem 4  文本生成器

标志： generator.*

问题描述：

JSOI 交给队员 ZYX 一个任务：编制一个称之为文本生成器的电脑软件。

该软件的使用者是一些低幼人群，他们现在使用的是 GW 文本生成器 V6 版。该软件可以随机生成一些文章——总是生成一篇长度固定且完全随机的文章。也就是说，生成的文章中每个字节都是完全随机的。

如果一篇文章中至少包含使用者们了解的一个单词，那么我们说这篇文章是可读的（我们称文章 a 包含单词 b ，当且仅当单词 b 是文章 a 的子串）。但是，即使按照这样的标准，使用者现在使用的 GW 文本生成器所生成的文章也是几乎完全不可读的。

ZYX 需要指出 GW 文本生成器 v6 生成的所有文本中可读文本的数量，以便能够成功获得 v7 更新版。你能帮助他吗？

 

输入文件第一行包含两个正整数，分别是使用者了解的单词总数 N (N <= 60) ， GW 文本生成器 v6 生成文本固定长度 M ；以下 N 行，每一行包含一个使用者了解的单词。

这里所有单词及文本的长度不会超过 100 ，并且只可能包含英文大写字母 A..Z.

输出文件只有一行，是一个整数，表示可能的文章总数。只需要知道结果模 10007 的值。

 

样例输入：

2 2

A

B

 

样例输出：

100

 

 

Problem 5  字符加密。

标志： cipher.*

问题描述：

喜欢钻研问题的 JS 同学，最近又迷上了对加密方法的思考。一天，他突然想出了一种他认为是终极的加密办法：把需要加密的信息排成一圈，显然，他们有很多种不同的读法，例如：

JSOI07

SOI07J

OI07JS

I07JSO

07JSOI

7JSOI0

把他们按照字符串的大小排序：

07JSOI

7JSOI0

I07JSO

JSOI07

OI07JS

SOI07J

读出最后一列字符： I0O7SJ ，就是加密后的字符串。

但是，如果想加密的字符串实在太长，你能写一个程序完成这个任务吗？

 

输入文件包含一行，欲加密的字符串。注意字符串的内容不一定是字母，数字，也可以是符号等。

输出文件只有一行，是加密后的字符串。

对于 40% 的数据， N <= 10,000; 对于 100% 的数据， N <= 100,000 ，其中 N 是与加密字符串的长度。

 

样例输入：

JSOI07

 

样例输出：

I0O7SJ