Description

CUDA（Compute Unified Device Architecture，統一計算架構[1]）是由NVIDIA所推出的一種整合技術，是該公司對於GPGPU的正式名稱。透過這個技術，使用者可利用NVIDIA的GeForce 8以後的GPU和較新的Quadro GPU進行計算。亦是首次可以利用GPU作為C-編譯器的開發環境。NVIDIA行銷的時候[2]，往往將編譯器與架構混合推廣，造成混亂。實際上，CUDA可以相容OpenCL或者自家的C-編譯器。無論是CUDA C-語言或是OpenCL，指令最終都會被驅動程式轉換成PTX代碼，交由顯示核心計算。

以GeForce 8800 GTX為例，其核心擁有128個內處理器。利用CUDA技術，就可以將那些內處理器串通起來，成為執行緒處理器去解決資料密集的計算。而各個內處理器能夠交換、同步和共享資料。利用NVIDIA的C-編譯器，通過驅動程式，就能利用這些功能。亦能成為流處理器，讓應用程式利用進行運算。 GeForce 8800 GTX顯示卡的運算能力可達到520GFlops，如果建設SLI系統，就可以達到1TFlops。[4]

但程式設計師在利用CUDA技術時，須分開三種不同的記憶體，要面對繁複的執行緒層次，編譯器亦無法自動完成多數任務，以上問題就提高了開發難度。而將來的G100會採用第二代的CUDA技術，提高效率，降低開發難度。 目前，已有軟體廠商利用CUDA技術，研發了一個Adobe Premiere Pro的外掛模組。通過外掛模組，使用者就可以利用顯示核心去加速H.264/MPEG-4 AVC的編碼速度。速度是單純利用CPU作軟體加速的7倍左右。 在NVIDIA收購AGEIA後，NVIDIA取得相關的物理加速技術，即是PhysX物理引擎。配合CUDA技術，顯示卡可以模擬成一顆PhysX物理加速晶片[5]。目前，全系列的GeForce 8顯示核心都支援CUDA。而NVIDIA亦不會再推出任何的物理加速卡，顯示卡將會取代相關產品。 為了將CUDA推向民用，NVIDIA會舉行一系列的編程比賽，要求參賽者開發程式，充分利用CUDA的計算潛能。但是，要將GPGPU普及化，還要看微軟能否在Windows作業系統中，提供相關的編程介面。[6] 2008年8月，NVIDIA推出CUDA 2.0[7]。2010年3月22日，NVIDIA推出CUDA 3.0，僅支援Fermi及之後的架構[8]。

CUDA是一種由NVIDIA提出的並由其製造的圖形處理單元（GPUs）實現的一種平行計算平臺及程式設計模型。CUDA給程式開發人員提供了直接存取CUDA GPUs中的虛擬指令集和平行計算元件的記憶體。 使用CUDA技術，GPUs可以用來進行通用處理（不僅僅是圖形）；這種方法被稱為GPGPU。與CPUs不同的是，GPUs有著側重以較慢速度執行大量併發執行緒的並行流架構，而非快速執行單一執行緒。 軟體發展者可以通過CUDA加速庫，編譯器指令（如OpenACC）以及符合工業標準的程式設計語言（如C,C++和Fortran）擴展對CUDA平臺進行操作。C/C++程式師可以使用「CUDA C/C++」，使用「NVCC」——NVIDIA基於LLVM的C/C++編譯器進行編譯；Fortran程式師可以使用「CUDA Fortran」，使用PGI公司的PGI CUDA Fortran編譯器進行編譯。 除了庫、編譯器指令、CUDA C/C++和CUDA Fortran，CUDA平臺還支援其它計算介面，如Khronos Group的OpenCL，Microsoft的DirectCompute，以及C++AMP。其協力廠商封裝也可用於Python，Perl，Fortran，Java，Ruby，Lua，Haskell，MATLAB，IDL及Mathematica的原生支援。 在電腦遊戲行業中，GPUs不僅用於進行圖形渲染，而且用於遊戲物理運算（物理效果如碎片、煙、火、流體），比如PhysX和Bullet。在計算生物學與密碼學等領域的非圖形應用上，CUDA的加速效果達到了可以用數量級來表示的程度。 CUDA同時提供低級API與高級API。最初的CUDA軟體發展包（SDK）於2007年2月15日公佈，支援Microsoft Windows和Linux。而後在第二版中加入了對Mac OS X的支援，取代了2008年2月14日發佈的測試版。所有G8x系列及以後的NVIDIA GPUs皆支援CUDA技術，包括GeForce，Quadro和Tesla系列。CUDA與大多數標準作業系統相容。Nvidia聲明：根據二進位相容性，基於G8x系列開發的程式無需修改即可在未來所有的Nvidia顯示卡上運行。[9]
限制：

CUDA不支援完整的C語言標準。它在C++編譯器上運行主機代碼時，會使一些在C中合法（但在C++中不合法）的代碼無法編譯。 不支援紋理渲染（CUDA 3.2及以後版本通過在CUDA陣列中引入「表面寫操作」——底層的不透明資料結構——來進行處理） 受系統主線的頻寬和延遲的影響，主機與裝置記憶體之間資料複製可能會導致效能下降（通過過GPU的DMA引擎處理，非同步記憶體傳輸可在一定範圍內緩解此現象） 當執行緒總數為數千時，執行緒應按至少32個一組來運行才能獲得最佳效果。如果每組中的32個進程使用相同的執行路徑，則程式分支不會顯著影響效果；在處理本質上不同的任務時，SIMD執行模型將成為一個瓶頸（如在光線追蹤演算法中遍歷一個空間分割的資料結構） 與OpenCL不同，只有Nvidia的GPUs支援CUDA技術 由於編譯器需要使用優化技術來利用有限的資源，即使合法的C/C++有時候也會被標記並中止編譯 CUDA（計算能力1.x）使用一個不包含遞迴、函式指標的C語言子集，外加一些簡單的擴展。而單個進程必須運行在多個不相交的記憶體空間上，這與其它C語言運行環境不同。 CUDA（計算能力2.x）允許C++類功能的子集，如成員函式可以不是虛擬的（這個限制將在以後的某個版本中移除）[參見《CUDA C程式設計指南3.1》－附錄D.6] 雙精度浮點（CUDA計算能力1.3及以上）與IEEE754標準有所差異：倒數、除法、平方根僅支援捨入到最近的偶數。單精確度中不支援反常值（denormal）及sNaN（signaling NaN）；只支援兩種IEEE捨入模式（舍位與捨入到最近的偶數），這些在每條指令的基礎上指定，而非控制字碼；除法/平方根的精度比單精確度略低。
下列的範例是如何用 C++ 自GPU的image 陣列中取得紋理（texture）:

cudaArray* cu_array;
texture tex;

// Allocate array
cudaChannelFormatDesc description = cudaCreateChannelDesc();
cudaMallocArray(&cu_array, &description, width, height);

// Copy image data to array
cudaMemcpy(cu_array, image, width*height*sizeof(float), cudaMemcpyHostToDevice);

// Bind the array to the texture
cudaBindTextureToArray(tex, cu_array);

// Run kernel
dim3 blockDim(16, 16, 1);
dim3 gridDim(width / blockDim.x, height / blockDim.y, 1);
kernel<<< gridDim, blockDim, 0 >>>(d_odata, height, width);
cudaUnbindTexture(tex);

__global__ void kernel(float* odata, int height, int width)
{
   unsigned int x = blockIdx.x*blockDim.x + threadIdx.x;
   unsigned int y = blockIdx.y*blockDim.y + threadIdx.y;
   float c = tex2D(tex, x, y);
   odata[y*width+x] = c;
}

不過，我們今天要你做的沒有這麼複雜

這些Code我們都已經幫你處理好了

今天你要扮演的角色是測試者

你只要專心幫我們測試我們的程式對不對就好

從我們的機器會丟給你一些數字，這些數字是我們所產出來的output

你要把這些output變成你的input，去測試結果對不對

那要判定的規則很簡單

只要我們機器產出來的數字是質數，你就輸出 「I Love CUDA!!!」

不是的話就輸出 "CUDA Has Something Wrong!!!"
參考資料來源：Wiki

Input

第一行輸入n（1 <= n <= 100000 ），接下來有n行，每一行有一個數字 x ( 2 <= x <= 100000 )

Output

根據我們給你的規則，判斷 x 要輸出 「I Love CUDA!!!」，還是 "CUDA Has Something Wrong!!!"

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

島風和天津風一起到沙漠中度假，

看到沙漠中有一盞神燈，

噢？你一定會認為一定要搓他才會有東西跑出來吧！

當然囉！這可是故事中精華！

於是島楓把神燈撿起來，

直接往天津風的身上砸，

突然有一個人影從神燈裡面老神在在踩著天津風走了出來，

島風一眼便認出這個人，嚇壞了，

這個人便是停留在歷史漩渦中的賭聖 ----- ＷＯ，

ＷＯ運用久違的破中文向島風說：『想要通過這裡嗎？那得先通過我的考驗喔！』

ＷＯ從頭上拔下像是桌遊的賽局盤，

島風不懂為什麼ＷＯ這麼雀躍，不過她確定ＷＯ一定是要測驗他的智商，

島風決定利用他剩下的腦容量，接受ＷＯ的賽局邀請，

開始述說賽局的規則：

歡迎來到我創立的賽局，這個遊戲的名稱叫做Starvation Thirsity

用方言來稱呼就是『四面楚歌』，世俗皆稱『望梅充饑』

如果你想要通過我的考驗，你必須要贏過我一半以上的回合數，遊戲規則如下：

1.  每回合會掉下三個數字，第一個數字是Starvation Number（ SN ），

    第二個數字是Hunger Goal( HG )，第三個數字是Thirsity State( TS ) 

2.  每回合的TS的起始值都會是 0

3.  SN 代表的是饑餓表的範圍，SN = n，雙方可以使用的Starvation value（饑餓值）為 1 ~ n 

    Ex. SN = 5，雙方可以選擇的饑餓值就是 1 ~ 5  [1,2,3,4,5] 

        SN = 8，雙方可以選擇的饑餓值就是 1 ~ 8  [1,2,3,4,5,6,7,8]

4.  雙方輪流從饑餓表中選擇其中一個數字，就讓這個數字累加到TS裡面，    
    若其中一方經過選擇後，使得 TS == HG，那一方即獲勝一回合。

    EX. Start : TS = 0, SN = 8, HG = 20

        島風先手：

        先 島風 選：           2 , TS = 0 + 2 = 2 

        換 ＷＯ 選：           5 , TS = 2 + 5 = 7 

        換 島風 選：           4 , TS = 7 + 4 = 11

        換 ＷＯ 選：           4 , TS = 11 + 4 = 15

        換 島風 選：           5 , TS = 15 + 5 = 20 

                            島風先達到 HG = 20，島風獲勝！！！ 

不管怎樣，由於我是莊家，所以每回合都是由島風你開始

啊～我忘記跟你說，這賽局是我自己設計的，

所以不管怎樣，我『絕對不會失誤』，除非你厲害到能夠把我打敗。

島風思考著遊戲規則，運用一切的腦容量想著必勝的方法

島風已經完全想好應對的方法

身為遊戲預測之神的你，雖然你不能幫他解決問題

但是你可以雙方在用盡全力的情況下

預測到底誰會贏

這時候，你就盡情的應用你的預測能力，邁向預測的航道吧！

Input

第一行為Ｔ（ 0 <= T <= 500 ），代表有Ｔ組測試資料。
接下來每一筆測試資料的第一行 n ( 1 <= n <= 2003 )，代表 n 回合。
為了確保勝負的公平性，我們保證回合數 n 都是奇數。
接下來 n 行輸入 SN , HG ( 1 <= SN <= 10000 , SN <= HG <= 10 ^ 9 )

Output

如果島風會贏，就輸出 "Shimakaze Wins!!"
如果ＷＯ會贏，就輸出 "WO Wins!!"

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

OAO 

OAOAOAOTAT 

AAAAAXYZAAA 

Description

在C中，一個整數(int)的範圍介於-2147483648~2147483647之間，

如果想做超出這個範圍的運算，可能會發生和預期不同的結果～

因此，有一種東西叫做大數運算，

概念是如果現在有一個整數，有100位數，那就用100個int去個別存這100位每一位的數字是多少，再用直式的方式做運算。

假設我們要計算111+19:

先寫成這樣，將兩個數字的最低位對齊：

    1 1 1
+     1 9
----------

然後從最低位開始一位一位做加法，


      1
    1 1 1
+     1 9
----------
        0

發現1+9=10需要進位，就將1加倒下一位～

      1
    1 1 1
+     1 9
----------
      3 0

然後繼續做加法，直到加完每個位數～

    1 1 1
+     1 9
----------
    1 3 0

我們習慣用array來存每個位數，假設用一個int來存一個位數，

假設我們用一個int array來存19，並且用a[0]存最低位，

那麼19可以存成：

a[1]=1
a[0]=9

假設我們用另一個array b 來存111這個數字，並拿array c 來儲存結果，

那麼計算111+19的時候，我們可以這樣寫：

for(i=0;i<4;i++){ // 三位數+二位數最高可達4位數
    c[i]+=a[i]+b[i]; // 做第i位數的加法
    c[i+1]+=c[i]/10; // 進位後，下一位數字要加多少
    c[i]%=10; // 進位後，這一位數字剩下多少
}

如果我們要計算111x19：

for(i=0;i<2;i++){
    for(j=0;j<3;j++){
        c[i+j]+=a[i]*b[j]; // 做乘法
    }
}
// 然後進位
for(i=0;i<5;i++){ // 三位數乘二位數最高會變成5位數
    c[i+1]+=c[i]/10;
    c[i]%=10;
}

這題的題目是，給你兩個整數 p 和 r ，請你計算 p 開 r 次根號的結果。

你可能記得，或許你忘記，在那不知道是國中還是高中的時候，大部分考試不能帶工程用計算機，

可是題目會叫你開根號，

這時候，有一種方法，叫做直式開方法，

這個方法非常深奧難以用二次元的圖片或文字說明，讓我們直接看一段影片～

Hint:

Maybe you can use something in or ?

關於各種型別的範圍，可以參考這裡。

大數運算還有很多其他的細節，你可以上網搜尋更多資料或是偷看演算法筆記。

Input

第一行為T(0<=T<=25)，代表有Ｔ組測試資料。
接著有T行，每一行有兩個整數 p ( 0 <= p < 10^101 )和 r ( r = 2, 4, 8, 16, 32 中任何一個數)。

Output

根據input每行的p和r輸出p開r次根號後的結果k ( 0 <= k <= 10^9 )，k可能會有小數，不過你只需要輸出k的整數部分就可以了~

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

請跟據輸入訊號求出該邏輯電路的輸出訊號

基本邏輯符號及真值表可參考wiki的邏輯閘條目
在C語言中也有運算子可直接使用:
NOT: !
AND: &
OR: |

Input

第一行有一T<100表測資數
接下來T行，每行代表一筆測資
輸入分別為D0 D1 D2 D3 S1 S2，每數只可能為0或1，兩數間有一空格隔開

Output

對於每筆測資，請輸出結果F(只可能為0或1)，並換行

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

你在房間 像幻燈片
你在我眼裡蔓延
你在手機 你在筆電 無法隔絕
你在深夜 像黑咖啡
你在我心裡面 陪我失眠
可是卻不在 我身邊
耳邊迴盪著郭采潔的歌聲
海帶認真地尋找著朝思暮想的那女孩的消息

原來海帶最喜歡的女孩被一個瘋狂的歹徒綁走了
在案發現場的電腦中有找到一絲的線索
一份被加密過的檔案，以及片段描述密碼的程式碼

雖然真正的密碼已經被歹徒刪除掉
但是海帶為了救出那女孩，透過各種蛛絲馬跡
在三天三夜不睡的奮鬥下，終於找出線索中的規律
原來這是一個叫做康廷索特的加密法

不過在體力嚴重透支的情況下，海帶竟然昏迷過去了
現在只好依賴可靠的你來幫忙解出這組密碼

來說明一下康廷索特加密法的特性：
所有的 key 值總共有一百萬個整數
每個整數都只會落在 [0, 100] 之間
一開始會先用康廷的方式把它弄亂
接著透過索特的方法依 key 從小到大排好歸類
舉例而言，原本 key 值若為
1 2 1 1 3
在康廷之後可能變成
3 1 2 1 1
在索特之後將變成
1 1 1 2 3

Input

單筆測資，只有一行，共一百萬個整數代表 key 值
0 <= key 值 <= 100

Output

把這些 key 值透過康廷索特加密法依序印出

兩個 key 之間請用空白隔開，別忘記在行末的時候要加上換行喔！

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

海帶非常喜歡 Pusheen
今天他終於收到 Pusheen 寄來的邀請函
原來 Pusheen 要開大量食物的派對想要跟大家分享
也希望能和大家一起出來玩

不過因為有風聲說會有食物小偷和搗蛋鬼要來亂場
於是 Pusheen 就把邀請函上頭的訊息用奇怪的編碼方式
讓除了被 Pusheen 認可以外的人都不能去派對

海帶看了看邀請函上的編碼
0x0 ----> 0
0x1 ----> 1
0x10 ---> 16
原來這個奇怪的編碼就是十六進位

好不容易解決了編碼的問題，當海帶要進入派對時
Pusheen 護衛卻說還要另外的密碼才行
又給了海帶另外一張解碼卡
0 ----> 0
1 ----> 1
16 ----> 10000
原來是要把邀請函上的十六進位轉成二進位呀

在千辛萬苦之後海帶終於得願以償的可以跟 Pusheen 一起玩了！
為了下次能不浪費跟 Pusheen 玩的時間
海帶想麻煩你幫忙寫一個程式把十六進位的數字快速的換成二進位

Input

第一行有一個整數 t 代表有多少測資(0 < t <= 100)
接著有 t 行十六進位的數字，每行為一筆測資
測資保證這些數字最大不超過 2147483647 (0x7fffffff)

Output

對每筆測資輸出一行二進位的數字
P.S.
0x10 的時候印出 10000
在最左邊的 1 前面都不需要補 0

Sample Input  Download

Sample Output  Download

Tags

Discuss