| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 10470 | Puzzle of Hope |
|
| 10471 | A000213 |
|
| 10472 | NumbersOnDoughnuts |
|
| 10487 | 田忌賽馬 |
|
| 10491 | Amr and Pins |
|
| 10493 | Shoemaker's Problem |
|
Description
(文長，慎入)
時值西元2025年
人類補完計畫再次啟動
人類補完委員會為此需要招募全世界頂尖的人才
因此他們在網路上向全世界的工程師下了戰帖
覺得這個計畫相當中二的你
情不自禁地點開了人類補完計畫的人才招募網頁
打開網頁的瞬間
「你能在這些碎片之中拼湊出希望嗎?」斗大的標題映入眼簾
螢幕上接著出現了一個相當復古的拼圖遊戲
玩法很簡單，給你一張原始的矩形圖片，這張圖片被劃分成M列N行的區域(列是橫的row，行是直的column)
將最右下角的區域拿走之後，並將剩下M*N-1個區域重新排列，形成遊戲的初始狀態
玩家可以執行的操作就只有將緊鄰空格上下左右的圖片移動至空格的位置而已
透過一連串的操作，直到M*N-1個區域的排列與原始圖片相同時，玩家獲得勝利
(如果沒玩過或看不懂敘述，以下用圖片被劃分成2列2行的區域為例)
這個遊戲一開始難度不高
因為只是2列2行的劃分而已，對你來說根本毫無智商可言
秒殺進入第二關之後，接下來是4列4行的劃分，但對你來說也是一塊蛋糕
不費吹灰之力地 你來到了第九十九關(不小心玩上癮了)
在第九十九關開始之前，系統出現以下訊息
「天將降大任於斯人也，必先苦其心志，勞其筋骨，餓其體膚，空乏其身...」
「偉大的勇士啊！這是最後一道試煉了，突破人類的界限接近神的領域吧！」
看完如此OOXX的開場白之後，此時的你發現大事不妙了，因為這一關你必須用60吋大螢幕才能玩得起來
原始圖片竟然被裁切成576列1024行的區域，根本是整人遊戲
但是愈是困難的問題，就愈是引起你的興趣(這就是工程師之魂啊～～)
經過仔細分析與思考後，你發現只剩下作弊竄改遊戲資料與寫程式交由電腦解題這兩種選擇
當然，字典裡不存在作弊這個字眼的你，毫不猶豫地選擇了寫程式這個方案
但是又經過一番思索之後，你發現如果單純採取暴力搜索法，最差的情況下可能太陽系都毀滅了電腦還找不出答案
於是你開始上網找尋資料，不眠不休地翻閱各種期刊論文，嘗試著將演算法進行優化
不幸的是，三天三夜過去了仍絲毫不見任何進展
已經精疲力盡的你意識漸漸模糊，此時腦海中浮現了十年前的場景
「這不是我踏上不歸路的時候嗎？真是令人懷念啊，在競程基礎班的那段時光。」夢中你喃喃自語著
「還記得才第二次上課就上機到晚上11點，差點就把課退掉了，呵呵」
「咦？為什麼會花這麼多時間呢？」
「喔我想起來了，那一天的上機題目是有關逆序數對(Inversion Pair)」
「仔細一想，逆序數對...」
「...」
「有了！BINGO！！！」你突然從夢中驚醒，眼中閃爍著希望的光芒
「接下來就剩下證實假說了，根據我的推估，最後一關應該是無解的」
接著你以驚人的打字速度在半分鐘內寫好程式，並且建立576列1024行的圖片資訊當作程式的input
果真不出所料，最後一關實際上是無解的
為了表達不滿，你向委員會寄了一封電子郵件，內容主要是抨擊這個遊戲設計者的惡趣味
三天之後，補完眠你起了個大早，打開信箱發現了委員會給你的回信
「勇士啊！你能進入最後的關卡確實不錯，但是請證明你的論點，否則我們只能將你視為能力不足。」
原來是你之前寄信時只顧著批評遊戲設計者，而忘記把你在夢中想到的推論與實際上實作出來的程式碼作為夾帶檔案寄出
於是你又開始用驚人的打字速度記錄下在夢中想到關於本問題的輔助定理
==========
定義 - 序列
原始圖片可以用M列N行的整數矩陣表示(M>=2, N>=2)，由左至右、由上至下，從1開始遞增編號
因為之後需要把右下角的區域拿掉，我們令矩陣右下角的元素為0
對於拼圖在某個時間點的狀態，我們一樣可以用整數矩陣來表示，矩陣的每個元素就對應著原始圖片的區域編號
但為了以下定理討論方便，我們不用矩陣的形式，改用序列的形式表示，這個序列是由矩陣一列接著一列得出
※以下引理、定理所說的序列，都是從此定義出發
==========
引理1 - 若交換序列中任意兩元素的位置，則序列的逆序數對個數的奇偶性會改變
證明很簡單，不另外贅述
推論：每經過一次合法操作，序列的逆序數對個數的奇偶性改變
==========
引理2 - 要保持序列最後的元素0位置不變，必須經過偶數次合法的操作
證明很簡單，不另外贅述
==========
引理3 - 若序列A與序列B由相同元素組成且最後的元素都是0且逆序數對個數的奇偶性不一致，則不可能透過合法操作將A轉換成B
根據引理1、2，得證
==========
引理4 - 若序列A與序列B由相同元素組成且最後的元素都是0且逆序數對個數的奇偶性一致，則存在有限次合法操作的方法將A轉換成B
需要用到離散數學課程學到的"等價類(equivalence class)"的概念
我們先將可以透過合法操作互相轉換的序列A與序列B歸為同一個等價類
可以用窮舉的方法證明2*2矩陣得出的序列只有2個等價類
進一步地，可以推廣至M*N的矩陣(M>=2, N>=2)得出的序列也只有兩個等價類
搭配引理3，我們知道其中一個等價類是逆序數對個數為偶數的序列，另一個是逆序數對個數為奇數的序列
至此，引理4證明完畢
※由於證明過程稍嫌複雜，此處僅列出證明方向，有興趣深入探討者，請自行查閱相關文獻
==========
定理 - 若拼圖遊戲初始狀態的序列與原始圖片的序列，兩者逆序數對個數的奇偶性一致時，則拼圖遊戲有解。反之，奇偶性不一致時，則拼圖遊戲無解。
因為遊戲開始與遊戲結束時，序列的最後一個元素必定是0，根據引理3、4，定理成立
==========
至於程式碼的部分，因為你在補眠的時候，你的妹妹進來房間動過你的電腦，不小心被刪掉了
但是妹妹是無價之寶，所以你寧願犧牲自己的時間也不忍心怪罪於她
反正也不花你幾秒鐘，請你重新再打一次吧！
究竟人類補完計畫會如何發展呢？沒有AC，就沒有未來。
你的一小步，是人類的一大步！
Input
本題有多筆測資，請以EOF作為輸入終止條件
每筆測資的第一列是兩個整數M,N(2<=M<=1024,2<=N<=1024)，中間會以一個空白字元分隔
表示原始圖片被劃分成M列N行
接下來會有M列輸入，這M列之中除了最後一列只有(N-1)個數字以外，每列都有N個數字，數字間會以一個空白字元分隔
這(M*N-1)個數字代表遊戲初始狀態的整數矩陣(編號範圍由題目敘述的定義可得出)，值得注意的是矩陣右下角編號為0的空格區域並不會在輸入中出現
測資之間會一個換行字元('\n')隔開
測資保證不會有像是編號重複、編號不在正常範圍諸如此類不合理的情況出現
讀測資時請儘量用scanf，使用cin並不是沒有TLE的可能性，請特別留意
Output
對於每一筆測資請判斷該組拼圖是否為無解。
若無解則輸出"WTF? No solution?"，若有解則輸出"WTF? How to solve it?"
Sample Input Download
Sample Output Download
Tags
Discuss
Description
微積分老師覺得費氏數列不夠潮，在教到數列與級數的章節時，向同學提出了另一個更炫的函數
f(n)=f(n-1)+f(n-2)+f(n-3)，n為正整數(n>=3)，並且 f(0)=f(1)=f(2)=1
老師說只要你能夠求出數列的第123456789項，這學期就會把你微積分當掉，因為如此優秀的學生他下學期非教不可
身為老師的忠實愛慕者，無論班上同學的勸阻，你還是想要解開老師的問題，於是你開始用最拿手的C語言開始解題
Input
Output
f(N)對10000007取餘數的結果
Sample Input Download
Sample Output Download
Tags
Discuss
Description
巧虎是一隻超級喜歡吃甜甜圈的小老虎，
Input
有多組測資，每筆測資代表一個甜甜圈，
Output
每筆測資佔一行，請直接輸出所求之答案。
Sample Input Download
Sample Output Download
Tags
Discuss
Description
試題來源: NPSC2011高中組決賽 Problem F
齊使者如梁，孫臏以刑徒陰見，說齊使。齊使以為奇，竊載與之齊。齊將田忌善而客待之。
忌數與齊諸公子馳逐重射。孫子見其馬足不甚相遠，馬有上、中、下輩。
於是孫子謂田忌曰：「君第重射，臣能令君勝。」田忌信然之，與王及諸公子逐射千金。
及臨質，臏曰：「今以君之下駟與彼上駟，取君上駟與彼中駟，取君中駟與彼下駟。」
既馳三輩畢，而田忌一不勝而再勝，卒得王千金。於是忌進孫子於威王。威王問兵法，遂以為師。
—『史記。孫子吳起列傳第五』
千年以前，孫臏靠著過人的智謀，巧妙地調整比賽順序，讓三戰皆墨的田忌翻身成兩勝一敗的贏家，也為自己贏得尊敬和重用。
千年以後的今日，賽馬依然是熱門的活動，不過今天你要面對的是更困難的問題。
若兩匹馬速度一樣，則算平手。
在比賽之前，勤勞的你每天都會訓練你的每一匹馬；而你的對手自我感覺非常良好，因此不會訓練他的馬。
每一匹馬的素質不同，我們用 ai 來表示第 i 匹馬的速度，用 bi 來表示第 i 匹馬的成長率。
經過 m 天的訓練，你的第 i 匹馬在第 m + 1 天的速度就會是 ai + m · bi 。對手的第 j 匹馬在每一天的速度都是 cj 。
你有一個出場順序可以贏得 N 場比賽中的至少 K 場（不包含平手）。
Input
Output
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Amr loves Geometry. One day he came up with a very interesting problem.
Amr has a circle of radius r and center in point (x,y). He wants the circle center to be in new position (x',y').
In one step Amr can put a pin to the border of the circle in a certain point, then rotate the circle around that pin by any angle and finally remove the pin.
Help Amr to achieve his goal in minimum number of steps.
Input
Each line of input consists of 5 space-separated integers r, x, y, x', y' (1<=r<=105, -105<=x, y, x', y'<=105), circle radius, coordinates of original center of the circle and coordinates of destination center of the circle respectively.
Output
For each line output a single integer — minimum number of steps required to move the center of the circle to the destination point.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Shoemaker has N jobs (orders from customers) which he must make. Shoemaker can work on only
one job in each day. For each i-th job, it is known the integer Ti (1<=Ti<=1000), the time in days it
takes the shoemaker to fi nish the job. For each day of delay before starting to work for the i-th job,
shoemaker must pay a fi ne of Si (1<=Si<=10000) cents. Your task is to help the shoemaker, writing a
programm to fi nd the sequence of jobs with minimal total fine.
Input
The input begins with a single positive integer on a line by itself indicating the number
of the cases following, each of them as described below. This line is followed by a blank
line, and there is also a blank line between two consecutive inputs.
First line of input contains an integer N (0<=N<=1000). The next N lines each contain two
numbers: the time and fi ne of each task in order.
Output
For each test case, the output must follow the description below. The outputs of two
consecutive cases will be separated by a blank line.
You programm should print the sequence of jobs with minimal fi ne. Each job should be represented
by its number in input. All integers should be placed on only one output line and separated by one
space. If multiple solutions are possible, print the first lexicographically.