國際資訊奧林匹亞競賽

The 26th International Olympiad in Informatics

 Taipei, Taiwan, July 13-20, 2014

http://www.ioinformatics.org/index.shtml


International Olympiad in Informatics 2014
Day-1 tasks

rail

http://www.ioi2014.org/images/tasks/day1/rail/twn.pdf

台灣橫貫鐵路

在百年後的二十二世紀，
台灣建立了一組貫穿中央山脈的橫貫鐵路系統連接台灣的西岸與東岸。
這組鐵路共分成 m 個區域，
從西到東命名為區域0 、區域1 、區域2 、...、到區域 m-1。
每個區域的北邊是一個向西的單向鐵路，
而每個區域的南邊是一個向東的單向鐵路。
而在每個區域內部可能設有一個縱向單軌車站連接南北邊的橫向鐵路，
也可能在該區域中沒有設置車站。
...

---------------------------------------------------------------------------------------------------

國際資訊奧林匹亞競賽研習營初選

國立臺灣師範大學資訊工程系、資訊教育所 編製

中華民國一○二年三月二日 

2013
http://toi.csie.ntnu.edu.tw/file/20130308201157.pdf

1. 測驗時間為 180 分鐘。

2. 限用C/C++/PASCAL語言作答。

3. 共有 5 道試題，每題 20 分。

第一題：拼字問題

• 執行時間: 1 秒
• 
  
• 有一位李先生從英文報紙上剪下 n 個大寫字母，希望可以拼貼出一封由大寫字母與空白字元組成的賀年字串 L 寄給朋友。請問這 n 個字母能從 L 的第一個字排到第幾個字，請將能拼出的部分顯示出來。例如，賀年卡 L 的內容為 HAPPY NEW YEAR，而 n 個字母為 NAWPEHLP。則須顯示 HAPP。
• 
  
• 輸入說明
• 第一行輸入字串 L，L 由大寫字母與空白字元組成，0 < |L| <= 100。
• 第二行輸入 n 個連續大寫字母，其中 0 < n <= 100。
•  
• 輸出說明
•  顯示所能拼出的文字（單字跟單字間要有一個空白字元）。假設至少可拼出一個字母。
• 
  
• 範例一
• 輸入
•     HAPPY NEW YEAR
•     AWPEHLPY
• 輸出
•     HAPPY
• 
  
• 說明: 在比對的過程中發現 n = 8 個大寫字母中沒有 N 這個字，且在 N 之前的部分都有找到，因此輸出 HAPPY（Y 之後不需列印空白字元）。
• 
  
• 範例二
• 輸入
•     GOOD LUCK IN THE YEAR AHEAD
•     OMKLDLMONNG
• 輸出
•     GOOD L
• 說明: 在比對的過程中發現 n = 11 個大寫字母中沒有 U 這個字，而在 U 之前的部分都有找到，且因為 L 是屬於下一個單字 LUCK 的字母，因此輸出為 GOOD L，D 和 L 間必須有一個空白字元。

	'''
	ryOlmp2013_01.py
	呂仁園，2014/08/27
	----------------------------
	第一題：拼字問題
	執行時間: 1 秒
	有一位李先生從英文報紙上剪下 n 個大寫字母，
	希望可以拼貼出一封由大寫字母與空白字元組成的賀年字串 L 寄給朋友。
	請問這 n 個字母能從 L 的第一個字排到第幾個字，
	請將能拼出的部分顯示出來。
	例如，賀年卡 L 的內容為 HAPPY NEW YEAR，
	而 n 個字母為 NAWPEHLP。則須顯示 HAPP。
	輸入說明
	第一行輸入字串 L，L 由大寫字母與空白字元組成，0 < |L| <= 100。
	第二行輸入 n 個連續大寫字母，其中 0 < n <= 100。
	輸出說明
	顯示所能拼出的文字（單字跟單字間要有一個空白字元）。
	假設至少可拼出一個字母。
	範例一
	輸入
	HAPPY NEW YEAR
	AWPEHLPY
	輸出
	HAPPY
	說明: 在比對的過程中發現 n = 8 個大寫字母中沒有 N 這個字，
	且在 N 之前的部分都有找到，因此輸出 HAPPY（Y 之後不需列印空白字元）。
	範例二
	輸入
	GOOD LUCK IN THE YEAR AHEAD
	OMKLDLMONNG
	輸出
	GOOD L
	說明: 在比對的過程中發現 n = 11 個大寫字母中沒有 U 這個字，
	而在 U 之前的部分都有找到，
	且因為 L 是屬於下一個單字 LUCK 的字母，
	因此輸出為 GOOD L，D 和 L 間必須有一個空白字元。
	'''
	範例= [
	#原題目所給的測試
	{'L':'HAPPY NEW YEAR', # 賀卡字串
	'I':'AWPEHLPY', # 輸入字串
	'T':'HAPPY'}, # 【人工預計】的正確輸出字串
	{'L':'GOOD LUCK IN THE YEAR AHEAD',
	'I':'OMKLDLMONNG',
	'T':'GOOD L'},
	#我們自己的測試
	{'L':'SINCERELY RENYUAN LYU',
	'I':'NCERYENSIRELYXXAABUAUNL',
	'T':'SINCERELY RENYUAN L'},
	{'L':'恭賀 新喜',
	'I':'賀大家恭可不新',
	'T':'恭賀 新'},
	{'L':'呂仁園 敬賀',
	'I':'仁一二三進園敬呂',
	'T':'呂仁園 敬'}
	]
	#
	# 主要的演算法在此。
	#
	def 拼貼賀年字串(L, I):
	O= ''
	for x in L:
	if (x in I):
	O += x
	I= I.replace(x,'_',1)
	elif (x == ' '):
	O += x
	else:
	break
	O= O.strip()
	return O
	#
	# 把演算法在 範例中 測試一番，
	# 包括別人給的例子，以及自己創造的例子。
	#
	def 主測試():
	for e in 範例:
	L= e['L']
	I= e['I']
	O= 拼貼賀年字串(L,I)
	print('拼貼賀年字串= ',O)
	# 以下這行可測試程式的「邏輯」正確性
	assert (O==e['T']), (O,e)
	if __name__=='__main__':
	主測試()
	'''
	# 執行結果
	>>>
	拼貼賀年字串= HAPPY
	拼貼賀年字串= GOOD L
	拼貼賀年字串= SINCERELY RENYUAN L
	拼貼賀年字串= 恭賀 新
	拼貼賀年字串= 呂仁園 敬
	>>>
	'''

view raw ryOlmp2013_01.py hosted with ❤ by GitHub