除了
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
?
?
posted on 2009-03-13 13:29
250 閱讀(775)
評論(0) 編輯 收藏 引用