全國(guó)青少年軟件編程青少年軟件編程（C語(yǔ)言）等級(jí)考試試卷（六級(jí)）

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

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

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

(1)

空的括號(hào)序列是美觀的；

(2)

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

(3)

若括號(hào)序列A、B都是美觀的，則括號(hào)序列AB也是美觀的；

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

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