2022 CCF 非專業(yè)級(jí)軟件能力認(rèn)證 CSP-J/S 2022 第二輪認(rèn)證 程小盟編程模擬賽 CSP-J/S 2022 第二輪認(rèn)證 入門組 時(shí)間：2022 年10 月5 日08:30 ～ 12:00 題目名稱 國(guó)際象棋 新年禮物 最強(qiáng)大腦 推銷員 題目類型 傳統(tǒng)型 傳統(tǒng)型 傳統(tǒng)型 傳統(tǒng)型 目錄 chess gifts escape salesman 可執(zhí)行文件名 chess gifts escape salesman 輸入文件名 chess.in gifts.in escape.in salesman.in 輸出文件名 chess.out gifts.out escape.out salesman.out 每個(gè)測(cè)試點(diǎn)時(shí)限 1.0 秒 1.0 秒 1.0 秒 1.0 秒 內(nèi)存限制 128 MiB 128 MiB 128 MiB 128 MiB 子任務(wù)數(shù)目 10 10 10 10 測(cè)試點(diǎn)是否等分 是 是 是 是 提交源程序文件名 對(duì)于 C++ 語(yǔ)言 chess.cpp gifts.cpp escape.cpp salesman.cpp 編譯選項(xiàng) 對(duì)于 C++ 語(yǔ)言 ‐O2 ‐lm 注意事項(xiàng)： 1. 文件名（程序名和輸入輸出文件名）必須使用英文小寫(xiě)。 2. C/C++ 中函數(shù) main() 的返回值類型必須是 int，程序正常結(jié)束時(shí)的返回值必 須是0。 3. 提交的程序代碼文件的放置位置請(qǐng)參考各省的具體要求。 4. 因違反以上三點(diǎn)而出現(xiàn)的錯(cuò)誤或問(wèn)題，申述時(shí)一律不予受理。 5. 若無(wú)特殊說(shuō)明，結(jié)果的比較方式為全文比較（過(guò)濾行末空格及文末回車）。 6. 程序可使用的?？臻g內(nèi)存限制與題目的內(nèi)存限制一致。 7. 全國(guó)統(tǒng)一評(píng)測(cè)時(shí)采用的機(jī)器配置為：Inter(R) Core(TM) i7-8700K CPU @3.70GHz， 內(nèi)存 32GB。上述時(shí)限以此配置為準(zhǔn)。 8. 只提供 Linux 格式附加樣例文件。 9. 評(píng)測(cè)在當(dāng)前最新公布的 NOI Linux 下進(jìn)行，各語(yǔ)言的編譯器版本以此為準(zhǔn)。 1 / 10 2022 CCF 非專業(yè)級(jí)軟件能力認(rèn)證 CSP-J/S 2022 第二輪認(rèn)證 2 / 10 國(guó)際象棋（chess） 【題目背景】 國(guó)際象棋（Chess），又稱西洋棋，是一種二人對(duì)弈的棋類游戲。棋盤為正方 形，由64個(gè)黑白（深色與淺色）相間的格子組成；棋子分黑白（深色與淺色） 兩方共32枚，每方各16枚。雖然漢語(yǔ)稱之為西洋棋或國(guó)際象棋，但是實(shí)際上它 起源于亞洲，后由阿拉伯人傳入歐洲，成為國(guó)際通行棋種，也是一項(xiàng)智力競(jìng)技 運(yùn)動(dòng)，曾被列為奧林匹克運(yùn)動(dòng)會(huì)正式比賽項(xiàng)目。 【題目描述】 國(guó)際象棋棋盤（如下圖所示），有8行8列，在棋盤上有黑白相間的方格，各種 不同的棋子有不同的行棋規(guī)則。 小賴皮不會(huì)下國(guó)際象棋，但他想到一種新的玩法。他自己畫(huà)了一個(gè)n*n的國(guó)際象 棋棋盤，在涂顏色的時(shí)候，他先把左下角涂上黑色，然后按照國(guó)際棋盤的樣子 黑白間隔地涂好顏色。然后他在棋盤的下方為每一列標(biāo)上序號(hào)，并在最下面一 排放上棋子（如圖中紅色圓圈所示），無(wú)論黑色和白色的格子都放。 棋子放好后就該走棋了，因?yàn)樾≠嚻ぬ嚻ち?，沒(méi)人跟他一起玩，所以他的這 種玩法正好適合他自己玩。 第1輪行棋：將所有1的倍數(shù)的列上放著的棋子都往前走一步； 第2輪行棋：將所有2的倍數(shù)的列上放著的棋子都往前走一步； 第3輪行棋：將所有3的倍數(shù)的列上放著的棋子都往前走一步； …… 2022 CCF 非專業(yè)級(jí)軟件能力認(rèn)證 CSP-J/S 2022 第二輪認(rèn)證 3 / 10 2 1 8 4 第n輪行棋：將所有n的倍數(shù)的列上放著的棋子都往前走一步。 n輪行棋結(jié)束之后，他會(huì)數(shù)一數(shù)這個(gè)時(shí)候一共有多少個(gè)棋子在白色的格子上（如 果棋子還在棋盤上的話），然后就去吃西瓜了。 【輸入格式】 從文件 chess.in 中讀入數(shù)據(jù)。輸 入只有一行，包括1個(gè)正整數(shù)n。 【輸出格式】 輸出到文件 chess.out 中。 輸出只有一行，為行棋結(jié)束之后在白色格子上的棋子個(gè)數(shù)。 【樣例 1 輸入】 【樣例 1 輸出】 【樣例 1 解釋】 第1輪行棋，第1、2列棋子向前走1步；第2輪行棋，第2列棋子向前走1歩。此 時(shí)，第1列的棋子停留在白色格子，第2列的棋子走出了棋盤，因此答案是1。 【樣例 2 輸入】 【樣例 2 輸出】 2022 CCF 非專業(yè)級(jí)軟件能力認(rèn)證 CSP-J/S 2022 第二輪認(rèn)證 4 / 10 【樣例 3】 見(jiàn)選手目錄下的 chess / chess 3.in 與 chess / chess 3.ans。 【數(shù)據(jù)范圍】 對(duì)于 30%的數(shù)據(jù)，2<=n<=10； 對(duì)于 80%的數(shù)據(jù)，2<=n<=5,000; 對(duì)于 100%的數(shù)據(jù)，2<=n<=1,000,000,000。 2022 CCF 非專業(yè)級(jí)軟件能力認(rèn)證 CSP-J/S 2022 第二輪認(rèn)證 5 / 10 新年禮物（gifts） 【題目背景】 過(guò)新年了，陳老師想給同學(xué)們買一些禮物寄給大家。 【題目描述】 因?yàn)榻衲闚OIP比賽大家成績(jī)都很好，為了獎(jiǎng)勵(lì)大家，在新年的時(shí)候陳老師想要從 網(wǎng)上買一些禮物寄給大家。陳老師調(diào)研了大家喜歡的禮物，并且一一上網(wǎng)查到了 商品的價(jià)格，統(tǒng)計(jì)出了一張表。 陳老師有n名學(xué)生，每名學(xué)生想要的禮物都有一個(gè)價(jià)格pi和郵費(fèi)si，也就是說(shuō)，購(gòu) 買這件禮物需要付pi+si元。陳老師只有b元的預(yù)算，他想給盡量多的同學(xué)購(gòu)買禮 物。陳老師在整理購(gòu)物車的時(shí)候發(fā)現(xiàn)，tb也給了他一個(gè)新年禮物，那就是一張優(yōu) 惠券。這張優(yōu)惠券能夠讓一個(gè)商品以半價(jià)購(gòu)買，既使用了優(yōu)惠券的商品需要付 pi/2+si元。 【輸入格式】 從文件 gifts.in 中讀入數(shù)據(jù)。 第1行有2個(gè)正整數(shù)，表示共有n名學(xué)生和b元錢。 第2到n+1行，每行有兩個(gè)正整數(shù)，分別代表這名同學(xué)想要的禮物的價(jià)格pi和郵 費(fèi)si，數(shù)據(jù)保證pi一定為偶數(shù)。 【輸出格式】 輸出到文件 gifts.out 中。 輸出一行一個(gè)整數(shù)，表示要陳老師能夠購(gòu)買的最多禮物數(shù)。 2022 CCF 非專業(yè)級(jí)軟件能力認(rèn)證 CSP-J/S 2022 第二輪認(rèn)證 6 / 10 5 24 4 2 2 0 8 1 6 3 12 5 4 【樣例 1 輸入】 【樣例 1 輸出】 【樣例 1 解釋】 共有5名學(xué)生，有24元的預(yù)算。如果給第1~4名同學(xué)購(gòu)買禮物，并且在購(gòu)買第三 名同學(xué)的禮物時(shí)使用優(yōu)惠券的話，總共會(huì)花(4+2)+(2+0)+(4+1)+(6+3) = 22 元，滿足預(yù)算。容易發(fā)現(xiàn)陳老師無(wú)法給全部5名同學(xué)都買禮物，因此答案為4。 需要注意的是，在給1~4名同學(xué)買禮物時(shí)，這張優(yōu)惠券如果在第1名同學(xué)或第4名 同學(xué)的禮物上使用，也可以滿足預(yù)算條件。 【樣例 2】 見(jiàn)選手目錄下的gifts / gifts 2.in 與 gifts / gifts 2.ans。 【樣例 3】 見(jiàn)選手目錄下的 gifts / gifts 3.in 與 gifts / gifts 3.ans。 【數(shù)據(jù)范圍】 對(duì)于20%的數(shù)據(jù)，1 ≤ n ≤ 10，1 ≤ b，pi，si ≤ 1000； 對(duì)于60%的數(shù)據(jù)，1 ≤ n ≤ 5000，1 ≤ b，pi，si ≤ 10 9； 對(duì)于100%的數(shù)據(jù)，1 ≤ n ≤ 200000，1 ≤ b，pi，si ≤ 10 9。 2022 CCF 非專業(yè)級(jí)軟件能力認(rèn)證 CSP-J/S 2022 第二輪認(rèn)證 7 / 10 【題目背景】 最強(qiáng)大腦（escape） 大聰明是一個(gè)學(xué)霸，參加過(guò)最強(qiáng)大腦，可以在1秒內(nèi)輕松計(jì)算100個(gè)10位數(shù)的加 法運(yùn)算。但小糊涂是個(gè)學(xué)渣，連最基本的加法進(jìn)位都算不對(duì)。 【題目描述】 小糊涂是大聰明最好的朋友，經(jīng)常一起出去玩。一天，小糊涂和大聰明來(lái)到游樂(lè) 場(chǎng)，在游樂(lè)場(chǎng)里有一個(gè)游戲，一人出題一人算。出題的人在一堆數(shù)當(dāng)中挑選一些出 來(lái)，算題的人如果能夠在1秒鐘之內(nèi)將這些數(shù)的和計(jì)算正確的話，兩個(gè)人就都能 夠得到獎(jiǎng)品。該項(xiàng)目還規(guī)定，出題人選出的數(shù)越多，計(jì)算正確后獲得的獎(jiǎng)品就越 好。 本來(lái)這個(gè)游戲很簡(jiǎn)單，只要小糊涂去出題，大聰明計(jì)算，他們一定能得到最好的 獎(jiǎng)品。老板看出了這一點(diǎn)，就讓大聰明去出題，讓小糊涂算。大聰明知道小糊涂在 計(jì)算時(shí)如果有進(jìn)位運(yùn)算的話，肯定會(huì)算錯(cuò)，于是他想到了一個(gè)辦法，要在老板給 出的數(shù)當(dāng)中選擇盡量多的數(shù)，而這些數(shù)在計(jì)算和的時(shí)候一定不能有進(jìn)位，這樣的 話小糊涂就不會(huì)算錯(cuò)了。 【輸入格式】 從文件 escape.in 中讀入數(shù)據(jù)。 第一行有1個(gè)正整數(shù)，表示老板給出的數(shù)字個(gè)數(shù)n。 第2行到第n+1行，每行一個(gè)正整數(shù)，代表老板給出的每一個(gè)數(shù)字ai。 【輸出格式】 輸出到文件 escape.out 中。 輸出一行一個(gè)整數(shù)，表示大聰明能夠選出的最多的數(shù)字是多少個(gè)。 2022 CCF 非專業(yè)級(jí)軟件能力認(rèn)證 CSP-J/S 2022 第二輪認(rèn)證 8 / 10 5 522 6 84 7311 19 3 【樣例 1 輸入】 【樣例 1 輸出】 【樣例 1 解釋】 老板一共給出了5個(gè)數(shù)字，分別是533、6、84、7311和19。如果選擇522、6和 7311的話，在求和運(yùn)算時(shí)就不會(huì)出現(xiàn)進(jìn)位。容易看出大于3個(gè)數(shù)字的組合都會(huì)產(chǎn) 生進(jìn)位，因此答案是3。 【樣例 2】 見(jiàn)選手目錄下的 escape / escape 2.in 與 t escape / escape 2.ans。 【數(shù)據(jù)范圍】 對(duì)于100%的數(shù)據(jù)，1 ≤ n ≤ 20， 1 ≤ ai ≤ 100,000,000。 2022 CCF 非專業(yè)級(jí)軟件能力認(rèn)證 CSP-J/S 2022 第二輪認(rèn)證 9 / 10 推銷員（salesman） 2022 CCF 非專業(yè)級(jí)軟件能力認(rèn)證 CSP-J/S 2022 第二輪認(rèn)證 10 / 10