除了 Problem 3, 《建筑搶修》的時限為 2s 之外，所有試題的時限均為 1s

?

Problem 1? 合金

標(biāo)志： metal.*

試題描述：

某公司加工一種由鐵、鋁、錫組成的合金。他們的工作很簡單。首先進(jìn)口一些鐵鋁錫合金原材料，不同種類的原材料中鐵鋁錫的比重不同。然后，將每種原材料取出一定量，經(jīng)過融解、混合，得到新的合金。新的合金的鐵鋁錫比重為用戶所需要的比重。

現(xiàn)在，用戶給出了 n 種他們需要的合金，以及每種合金中鐵鋁錫的比重。公司希望能夠訂購最少種類的原材料，并且是用這些原材料可以加工出用戶需要的所有種類的合金。

?

輸入文件的第一行是兩個整數(shù) m 和 n ， (m, n <= 500) ，分別表示原材料種數(shù)和用戶需要的合金種數(shù)。

第 2 到 m+1 行，每行三個實數(shù) a, b, c, (a, b, c >= 0 且 a+b+c = 1) ，分別表示鐵鋁錫在一種原材料中所占的比重。

第 m+2 到 m+n+1 行，每行三個實數(shù) a, b, c, (a, b, c >= 0 且 a+b+c = 1) ，分別表示鐵鋁錫在一種用戶需要的合金中所占的比重。

輸出一個整數(shù)，表示最少需要的原材料種數(shù)。若無解，則輸出 -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? 麻將

標(biāo)志： mahjong.*

問題描述：

麻將是中國傳統(tǒng)的娛樂工具之一。麻將牌的牌可以分為字牌（共有東南西北中發(fā)白七種）和序數(shù)牌（分為條子餅子萬字三種花色，每種花色各有一到九的九種牌），每種牌各四張。在麻將中，通常情況下一組和了的牌（即完成的牌）由十四張牌組成。十四張牌中的兩張組成對子（即完全相同的兩張牌），剩余的十二張組成三張一組的四組，每一組需為順子（即同花色且序數(shù)相連的序數(shù)牌，例如條子三四五），或者是刻字（即完全相同的三張牌）。一組聽牌的牌是指一組十三張牌，且再加上某一張牌就可以組成和牌。那一張加上的牌可以成為等待牌。

在這里，我們考慮一種特殊的麻將。在這種特殊的麻將里，沒有字牌，花色也只有一種。但是，序數(shù)不被限制在一到九的范圍內(nèi)，而是在 1 到 n 的范圍內(nèi)。同時，也沒有每一種牌四張的限制。一組和了的牌由 3m +2 張牌組成，其中兩張組成對子，其余 3m 張組成三張一組的 m 組，每組需為順子或刻字。先給出一組 3m +1 張的牌，要求判斷該組牌是否為聽牌（即還差一張就可以和牌）。如果是的話，輸出所有可能的等待牌。

?

輸入文件包含兩行。第一行包含兩個由空格隔開的整數(shù) n, m (9 <= n <= 400, 4 <= m <= 1000) ，第二行包含 3m +1 個由空格隔開的整數(shù)，每隔數(shù)均在范圍 1 到 n 內(nèi)。這些數(shù)代表要求判斷聽牌的牌的序數(shù)。

輸出為一行。如果該組牌為聽牌，則輸出所有的可能的等待牌的序數(shù)，數(shù)字之間用一個空格隔開。所有的序數(shù)須按從小到大的順序輸出。如果該組牌不是聽牌，則輸出 ”NO”.

?

輸入樣例：

9 4

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

?

輸出樣例：

6 7 9

?

?

?

Problem 3? 建筑搶修

標(biāo)志： repair.*

問題描述：

小剛在玩 JSOI 提供的一個稱之為“建筑搶修”的電腦游戲。

經(jīng)過了一場激烈的戰(zhàn)斗， T 部落消滅了所有 z 部落的入侵者。但是 T 部落的基地里已經(jīng)有 N 個建筑設(shè)施受到了嚴(yán)重的損傷，如果不盡快修復(fù)的話，這些建筑設(shè)施將會完全毀壞。

現(xiàn)在的情況是： T 部落基地里只有一個修理工人。雖然它能瞬間到達(dá)任何一個建筑，但是修復(fù)每個建筑都需要一定的時間。同時，修理工人修理完一個建筑才能修理下一個建筑，不能同時修理多個建筑。如果某個建筑在一段時間之內(nèi)沒有完全修理完畢，這個建筑就報廢了。

你的任務(wù)是幫小剛合理的制定一個修理順序，以搶修盡可能多的建筑。

?

輸入文件第一行是一個整數(shù) N ，接下來 N 行每行兩個整數(shù) T1, T2 描述一個建筑：修理這個建筑需要 T1 秒，如果在 T2 秒之內(nèi)還沒有修理完成，這個建筑就報廢了。

輸出文件只有一行，是一個整數(shù) S ，表示最多可以搶修 S 個建筑。

N < 150,000;? T1 < T2 < maxlongint

?

樣例輸入：

4

100 200

200 1300

1000 1250

2000 3200

?

樣例輸出：

3

?

?

?

Problem 4? 文本生成器

標(biāo)志： generator.*

問題描述：

JSOI 交給隊員 ZYX 一個任務(wù)：編制一個稱之為文本生成器的電腦軟件。

該軟件的使用者是一些低幼人群，他們現(xiàn)在使用的是 GW 文本生成器 V6 版。該軟件可以隨機(jī)生成一些文章——總是生成一篇長度固定且完全隨機(jī)的文章。也就是說，生成的文章中每個字節(jié)都是完全隨機(jī)的。

如果一篇文章中至少包含使用者們了解的一個單詞，那么我們說這篇文章是可讀的（我們稱文章 a 包含單詞 b ，當(dāng)且僅當(dāng)單詞 b 是文章 a 的子串）。但是，即使按照這樣的標(biāo)準(zhǔn)，使用者現(xiàn)在使用的 GW 文本生成器所生成的文章也是幾乎完全不可讀的。

ZYX 需要指出 GW 文本生成器 v6 生成的所有文本中可讀文本的數(shù)量，以便能夠成功獲得 v7 更新版。你能幫助他嗎？

?

輸入文件第一行包含兩個正整數(shù)，分別是使用者了解的單詞總數(shù) N (N <= 60) ， GW 文本生成器 v6 生成文本固定長度 M ；以下 N 行，每一行包含一個使用者了解的單詞。

這里所有單詞及文本的長度不會超過 100 ，并且只可能包含英文大寫字母 A..Z.

輸出文件只有一行，是一個整數(shù)，表示可能的文章總數(shù)。只需要知道結(jié)果模 10007 的值。

?

樣例輸入：

2 2

A

B

?

樣例輸出：

100

?

?

Problem 5? 字符加密。

標(biāo)志： cipher.*

問題描述：

喜歡鉆研問題的 JS 同學(xué)，最近又迷上了對加密方法的思考。一天，他突然想出了一種他認(rèn)為是終極的加密辦法：把需要加密的信息排成一圈，顯然，他們有很多種不同的讀法，例如：

JSOI07

SOI07J

OI07JS

I07JSO

07JSOI

7JSOI0

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

07JSOI

7JSOI0

I07JSO

JSOI07

OI07JS

SOI07J

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

但是，如果想加密的字符串實在太長，你能寫一個程序完成這個任務(wù)嗎？

?

輸入文件包含一行，欲加密的字符串。注意字符串的內(nèi)容不一定是字母，數(shù)字，也可以是符號等。

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

對于 40% 的數(shù)據(jù)， N <= 10,000; 對于 100% 的數(shù)據(jù)， N <= 100,000 ，其中 N 是與加密字符串的長度。

?

樣例輸入：

JSOI07

?

樣例輸出：

I0O7SJ

?

?