除了 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

?

?