Online Judge 基礎觀念:多測資輸入不需把資料都讀入後再輸出

有的題目會要求一次輸入多筆測資,例如:
TOJ 3
NTU judgegirl 80

常見初學者的寫法會將所有的資料讀入,存進陣列裡面,一個一個處理完之後再輸出。

但事實上不需要這麼做,你只需要每次讀入一個一組測資,直接輸出答案就行了!完全不需要浪費額外記憶體去開陣列。
以 TOJ 5 為例:

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <stdio.h>
int gcd(int a,int b){/*略*/}
int main()
{
int T;
scanf("%d",&T);
for(int i=0;i<T;i++)
{
int a,b;
scanf("%d %d",&a,&b);
printf("%d",gcd(a,b));
}
}

題目的output不是要求要一次輸出所有答案嗎?事實上並不是的。在你電腦裡面的terminal(或者cmd)中,輸入和輸出會有即時的互動,也就是說當你打完每一組測試資料,它就會立刻輸出答案,因此你會看到輸入和輸出湊在一起的情況。

在 Online Judge 中,輸入和輸出可以當成兩個檔案,因此先後順序是沒有關係的。
在你的電腦中,可以在terminal模擬類似的環境:

  1. 開啟terminal(在windows上則是cmd)。
  2. 使用cd命令切換到測資和執行檔所在的資料夾。
  3. 把要輸入的測試資料存成一個文字檔,例如input.txt
  4. 執行以下命令:執行檔 < input.txt > output.txt 或者 執行檔 < input.txt,此處使用了 io redirection 的技巧,細節可以自行上網查詢。

我們把input.txt作為程式的輸入資料,輸出的資料則存在output.txt,在 Online Judge 中也是使用類似的方法實作。

UVa 1569 - Multiple

Link: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4351

自己想不出這題,網路上題解也不多,後來研究了這篇的code才知道怎麼寫。

解法

想個暴利的解法,把題目給定的M個數字排序後,用這些數字去組合,BFS搜索下去(必須用BFS去搜索才會優先找到較小的數字),搜索的過程一邊模N就能判斷最後是不是N的倍數(搜索完成)。
不過這樣的作法複雜度是指數級別的,而且沒辦法判斷是不是找不到答案(需輸出0)。

接著我們可以發現一件事,假設某兩個狀態模N後是一樣的,則由他們到答案的路徑也是一樣的,所以他們之間較晚搜索到的數字可以直接忽略,因此狀態只剩下N種,紀錄一下哪個模數出現過即可。

Read More

Google Code Jam 賽制介紹

解題 / 大小測資

每題有分大小測資,解題時下載輸入測資檔,並上傳輸出答案
我習慣使用 出入重導向 的方式,或者也可以直接在程式碼裡面寫成 file i/o
小測資 下載後必須在4分鐘內上傳答案,若答案錯誤或超時未上傳,會被加4分鐘的penalty(如果最後這題AC的話),上傳後會立刻知道是否正確

Read More

IOI 2014 - 猜謎遊戲(game), TIOJ 1896

Link(original): http://www.ioinformatics.org/locations/ioi14/contest/day1/game/twn.pdf
Link(TIOJ): http://tioj.ck.tp.edu.tw/problems/1896


這題有三種解法,第一種大測資會TLE只能拿42分,不過我只想到第一種。

題解前,先做個定義:

  • 圖G: 由 尚未詢問過的邊 和 詢問過且回答yes的邊 構成
  • 圖H: 由 詢問過且回答yes的邊 構成

solution 1

Read More

竹園論壇文章搬家

由於論壇壞掉到現在還沒修好,今天把以前Po在竹園論壇( http://forum.tfcis.org/ )的解題分享文章轉貼到此。
論壇格式和部落格有點不同,稍微做了點修改,如果有任何格式亂掉或漏圖的問題歡迎跟我反映。

大約標記於2014年發布的文章都是以前論壇轉移過來的,以下為列表:
http://domen.logdown.com/posts/336598/google-code-jam-2014-round1a-a-charging-chaos
http://domen.logdown.com/posts/336572/google-code-jam-2014-round1b-a-the-repeater
http://domen.logdown.com/posts/336569/google-code-jam-2013-round-2-a-ticket-swapping
http://domen.logdown.com/posts/336561/poj-1182-food-chain
http://domen.logdown.com/posts/336559/toj-63-d-net-tricks
http://domen.logdown.com/posts/336553/codeforces-448c-painting-fence
http://domen.logdown.com/posts/336549/toj-75-f-hiking-and-ice-elves
http://domen.logdown.com/posts/336609/google-code-jam-2014-qualification-c-minesweeper-master
http://domen.logdown.com/posts/336563/codeforces-445c-dzy-loves-physics

2016/04/06

再度搬家,參考搬家到Hexo,因此 上面連結可能是壞的,就自己找一下吧XD

TIOJ 1332 - 名義老爸

Link: http://tioj.ck.tp.edu.tw/problems/1332

用map(也可用set包pair)隨便亂寫AC,插入的時候用map找比它大和比它小的兩數分別是誰,誰比較晚插入誰就是它的爸爸。
複雜度O(nlgn),據說正解是用笛卡爾樹O(n),參考:
http://ckhs1328.pixnet.net/blog/post/40525136-tioj-1332-%E5%90%8D%E7%BE%A9%E8%80%81%E7%88%B8
http://cbdcoding.blogspot.tw/2015/03/tioj-1332.html

Read More