回分類題庫
h047: E.幼稚的災難
關鍵字: NPSC 2008 高中組初賽

測資點 : 2 | Time Limit : 10000 ms | Memory Limit : 128000 KB
Accepted : 16 Times / 14 Users | Submit : 24 Times / 16 Users | Accepted rate : 88%
題目加入時間 : 2011-11-10 10:44

Content: 简体中文

幼稚國的計算機中心最近發生了一個大麻煩...

起因是有一個幼稚鬼在電腦中心灌起了熱門的線上遊戲 World of Warcraft - Wrath of the Lich King(以下簡稱WotLK),大家就開始在計算機中心裡面打起了電動。因為 WotLK 實在是太好玩了,於是這群幼稚鬼幾乎每天都不停的玩,一天 25 小時裡面大部分的時間幾乎都在電腦主機面前。而由於 WotLK 實在太好玩了,這群幼稚鬼甚至組成了一個幼稚鬼公會,在英明的幼稚會長睿智的領導下,帶領這群幼稚鬼們日益茁壯。

在 WotLK 裡面,有一個遊戲要素 : 團隊 RAID,RAID 通常由公會內的 25 人組成,由 Raid Leader (RL)帶領下,率眾攻入地下城副本,在大家的齊心協力與幼稚的 RL 英明的領導下,擊敗地下城最後的頭目,順便洗劫地下城頭目的寶物(疑?)。

每次出 Raid 的時候總是會發生很多幼稚的事情,有過獵人耍帥拿刀衝到第一線拼命砍,有牧師拿個火焰魔仗丟火球裝成法師,更可憐的是有個法師自從某次輸給那位牧師之後受到衝擊太大,現在只會製作魔法麵包當廚師....

很不幸的是,公會裡面恰好有 26 個幼稚鬼,並不是每個幼稚鬼都可以參加 RAID,所以不管怎樣都得會有一個幼稚鬼沒辦法跟著一起出團,於是英明的 RL 幾乎每個星期都在為要讓哪些幼稚鬼可以一起出團而傷透了腦筋。英明的 RL 於是把幼稚公會內的所有幼稚鬼從 1 到 25 都編上了編號(不含 RL,因為他是英明的 RL),先從 2 開始,讓所有編號是 2 的倍數的幼稚鬼先全部加入 Raid,再讓所有編號是 3 的倍數的幼稚鬼加入,接著再讓編號是 4 的倍數的幼稚鬼加入,以此類推,直到隊伍裡面有 25 個人為止,剩下最後一位沒加入的幼稚鬼只好站在地下城門口幫大家做麵包。

看到這裡,編號 1 號的幼稚鬼發現不對了,大叫說:『不對吧!這樣不就每次都是我要站在門口!!!!!』

這真的是太幼稚了............

由於這群幼稚鬼每天都在計算機中心裡面吵吵鬧鬧,計算機中心的幼稚管理員不高興了,於是在網路上請了一群會最寫程式的人幫忙寫了一隻病毒,想要讓計算機中心裡面的電腦再也打不了電動。

所以幼稚國的計算機中心最近發生了一個大麻煩...他們中毒了( ̄▽ ̄#)﹏﹏

這個病毒的傳染力遠遠超出了計算機中心幼稚管理員的想像,他每秒都會不斷的在每一台電腦之間移動,並且每次從一台主機跳到另外一台主機上的時候,都會更改程式內部的識別碼,所以計算機中心的幼稚管理員不知道如何去抓到這支病毒。

現在,計算機中心幼稚管理員再次把這個問題放到了網路上面,想請這群最會寫程式的人來幫他想辦法,計算出病毒到底藏身再哪一台電腦。

Input:

第一行有一個數字 k , 1 <= k <= 10 代表共有 k 筆測資,

每筆測資第一行有四個整數 N , M , D , T,

1 <= N<= 60000 代表計算機中心共有N 台主機,編號從 0 ~ N-1
0 <= M < N 代表這隻病毒第零秒時藏在編號 M 的主機中
0 <= D <=100000 代表這隻病毒第零秒時的識別碼
0 <= T <= 2,000,000,000 代表最後的時間

假設病毒在第 t 秒的時候在編號為 m 的主機,識別碼是 d,
則第 t+1 秒的時候病毒會跳到編號 (d mod N)的電腦,
並把識別碼改為 (d + 2m + (d mod N))

Output:

每筆測資輸出一行,每行有兩個整數 M、P,
代表 T 秒過後病毒在編號 M 的電腦識別碼是 D,
P = D mod N

Sample Input:help

若題目沒有特別說明,則應該以多測資的方式讀取,若不知如何讀取請參考 a001 的範例程式。
3
5 1 2 10
8322 1787 21690 956606923
36293 30135 2735 422800487

Sample Output :

2 0
5874 6100
4942 28648

Hint :

Author :

NPSC 2008 高中組初賽 (管理員:sagit)

  Solve it!   Status Forum