全國青少年軟件編程青少年軟件編程（C語言）等級考試試卷（六級）

青少年軟件編程（C語言）等級考試試卷（六級）生日相同2.0在一個(gè)有180人的大班級中，存在兩個(gè)人生日相同的概率非常大，現(xiàn)給出每個(gè)學(xué)生的名字，出生月日。試找出所有生日相同的學(xué)生。時(shí)間限制：1000內(nèi)存限制：65536輸入第一行為整數(shù)n，表示有n個(gè)學(xué)生，n≤180。此后每行包含一個(gè)字符串和兩個(gè)整數(shù)，分別表示學(xué)生的名字（名字第一個(gè)字母大寫，其余小寫，不含空格，且長度小于20）和出生月(1≤m≤12)日(1≤d≤31)。名字、月、日之間用一個(gè)空格分隔輸出每組生日相同的學(xué)生，輸出一行，其中前兩個(gè)數(shù)字表示月和日，后面跟著所有在當(dāng)天出生的學(xué)生的名字，數(shù)字、名字之間都用一個(gè)空格分隔。對所有的輸出，要求按日期從前到后的順序輸出。對生日相同的名字，按名字從短到長按序輸出，長度相同的按字典序輸出。如沒有生日相同的學(xué)生，輸出”None”樣例輸入6Avril32Candy45Tim32Sufia45Lagrange45Bill32樣例輸出32TimBillAvril45CandySufiaLagrange機(jī)器翻譯VariantF的電腦上安裝了一個(gè)機(jī)器翻譯軟件，他經(jīng)常用這個(gè)軟件來翻譯英語文章。這個(gè)翻譯軟件的原理很簡單，它只是從頭到尾，依次將每個(gè)英文單詞用對應(yīng)的中文含義來替換。對于每個(gè)英文單詞，軟件會(huì)先在內(nèi)存中查找這個(gè)單詞的中文含義，如果內(nèi)存中有，軟件就會(huì)用它進(jìn)行翻譯；如果內(nèi)存中沒有，軟件就會(huì)在外存中的詞典內(nèi)查找，查出單詞的中文含義然后翻譯，并將這個(gè)單詞和譯義放入內(nèi)存，以備后續(xù)的查找和翻譯。

假設(shè)內(nèi)存中有M個(gè)單元，每單元能存放一個(gè)單詞和譯義。每當(dāng)軟件將一個(gè)新單詞存入內(nèi)存前，如果當(dāng)前內(nèi)存中已存入的單詞數(shù)不超過M，軟件會(huì)將新單詞存入一個(gè)未使用的內(nèi)存單元；若內(nèi)存中已存入M個(gè)單詞，軟件會(huì)清空最早進(jìn)入內(nèi)存的那個(gè)單詞，騰出單元來，存放新單詞。

假設(shè)一篇英語文章的長度為N個(gè)單詞。給定這篇待譯文章，翻譯軟件需要去外存查找多少次詞典？假設(shè)在翻譯開始前，內(nèi)存中沒有任何單詞。時(shí)間限制：1000內(nèi)存限制：262144輸入第一行為兩個(gè)正整數(shù)M和N，代表內(nèi)存容量和文章的長度。第二行為N個(gè)非負(fù)整數(shù)，按照文章的順序，每個(gè)數(shù)（大小不超過1000000）代表一個(gè)英文單詞。文章中兩個(gè)單詞是同一個(gè)單詞，當(dāng)且僅當(dāng)它們對應(yīng)的非負(fù)整數(shù)相同。對于50%的數(shù)據(jù)，1<=N、M<=1000；對于100%的數(shù)據(jù)，1<=N、M<=1000000。輸出一個(gè)整數(shù)，為軟件需要查詞典的次數(shù)。樣例輸入371215441樣例輸出5提示整個(gè)查字典過程如下：每行表示一個(gè)單詞的翻譯，冒號前為本次翻譯后的內(nèi)存狀況:空：內(nèi)存初始狀態(tài)為空。1．1：查找單詞1并調(diào)入內(nèi)存。2．12：查找單詞2并調(diào)入內(nèi)存。3．12：在內(nèi)存中找到單詞1。4．125：查找單詞5并調(diào)入內(nèi)存。5．254：查找單詞4并調(diào)入內(nèi)存替代單詞1。6．254：在內(nèi)存中找到單詞4。7．541：查找單詞1并調(diào)入內(nèi)存替代單詞2。共計(jì)查了5次詞典。括號畫家Candela是一名漫畫家，她有一個(gè)奇特的愛好，就是在紙上畫括號。這一天，剛剛起床的Candela畫了一排括號序列，其中包含小括號()、中括號[]和大括號{}，總長度為N。這排隨意繪制的括號序列顯得雜亂無章，于是Candela定義了什么樣的括號序列是美觀的：

(1)

空的括號序列是美觀的；

(2)

若括號序列A是美觀的，則括號序列(A)、[A]、{A}也是美觀的；

(3)

若括號序列A、B都是美觀的，則括號序列AB也是美觀的；

例如[(){}]()是美觀的括號序列，而)({)[}](則不是。

現(xiàn)在Candela想知道她畫出的括號序列是不是美觀的。你能幫幫她嗎？時(shí)間限制：1000內(nèi)存限制：262144輸入一個(gè)括號序列，長度不超過10000。輸出如果它是美觀的，輸出Yes，否則輸出No。樣例輸入{}[(){}]()樣例輸出Yes中綴表達(dá)式的值人們熟悉的四則運(yùn)算表達(dá)式稱為中綴表達(dá)式，例如(23+34*45/(5+6+7))。在程序設(shè)計(jì)語言中，可以利用堆棧的方法把中綴表達(dá)式轉(zhuǎn)換成保值的后綴表達(dá)式（又稱逆波蘭表示法），并最終變?yōu)橛?jì)算機(jī)可以直接執(zhí)行的指令，得到表達(dá)式的值。給定一個(gè)中綴表達(dá)式，編寫程序，利用堆棧的方法，計(jì)算表達(dá)式的值。時(shí)間限制：200內(nèi)存限制：65536輸入第一行為測試數(shù)據(jù)的組數(shù)N接下來的N行，每行是一個(gè)中綴表達(dá)式。表達(dá)式中只含數(shù)字、四則運(yùn)算符和圓括號，操作數(shù)都是正整數(shù)，數(shù)和運(yùn)算符、括號之間沒有空格。中綴表達(dá)式的字符串長度不超過600。輸出對每一組測試數(shù)據(jù)輸出一行，為表達(dá)式的值樣例輸入33+5*8(3+5)*8(23+34*45/(5+