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