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

?

Problem 1? 合金

標(biāo)志： metal.*

試題描述：

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

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

?

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

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

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

輸出一個(gè)整數(shù)，表示最少需要的原材料種數(shù)。若無(wú)解，則輸出 -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.*

問(wèn)題描述：

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

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

?

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

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

?

輸入樣例：

9 4

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

?

輸出樣例：

6 7 9

?

?

?

Problem 3? 建筑搶修

標(biāo)志： repair.*

問(wèn)題描述：

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

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

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

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

?

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

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

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

?

樣例輸入：

4

100 200

200 1300

1000 1250

2000 3200

?

樣例輸出：

3

?

?

?

Problem 4? 文本生成器

標(biāo)志： generator.*

問(wèn)題描述：

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

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

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

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

?

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

這里所有單詞及文本的長(zhǎng)度不會(huì)超過(guò) 100 ，并且只可能包含英文大寫字母 A..Z.

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

?

樣例輸入：

2 2

A

B

?

樣例輸出：

100

?

?

Problem 5? 字符加密。

標(biāo)志： cipher.*

問(wèn)題描述：

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

JSOI07

SOI07J

OI07JS

I07JSO

07JSOI

7JSOI0

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

07JSOI

7JSOI0

I07JSO

JSOI07

OI07JS

SOI07J

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

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

?

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

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

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

?

樣例輸入：

JSOI07

?

樣例輸出：

I0O7SJ

?

?