2009年12月13日 星期日

我的ZeroJudge Solutions也搬上GitHub了!


為了練習GIT
我把我寫的所有ZeroJudge解答都放上GitHub啦

請參考這個連結
http://github.com/yrchen/ZeroJudge/tree/chchwy

上面同時還有禹任跟俊諺的解答
NetLab ZeroJudge團 在這裡誠摯的歡迎您的加入 一同切磋程式技巧

2009年11月29日 星期日

UVa 11461 Square Numbers

UVa 11172 Relational Operators

非常適合作為ACM入門第一題。

UVa 10924 Prime Words

質數題大屠殺的時候解的

UVa 10783 Odd Sum

似乎有不需要任何if判斷的寫法? 還沒參透

UVa 10079 Pizza Cutting

有關空間分割的小題目,雖然規則容易找。
至於為什麼是這樣,有興趣的人可以當作歸納法證明的小菜。


UVa 900 Brick Wall Patterns

無所不在的費波納西數列。

UVa 583 Prime Factors

解題策略

這題要做質因數分解,只要先用篩法建好質數表,接下來就簡單了。
要注意的是這題的數字非常大,很接近 int 的上限,一個不小心就會溢位,要小心。

2009年11月23日 星期一

UVa 516 Prime Land

解題策略

這題是考質因數分解,先把質因數分解表示法轉成數字,數字減一後,再轉回質因數分解表示法。

關鍵測資

Input:
18 1 17 1 15 1 
17 1 11 1 
11 1 29 1 9 1 
2 1 4 1 5 1 7 1 11 1 
18 1 23 1 29 1 
31 1 29 1 
2 3 11 2 25 1 
41 2 
51 1 5 1 
17 1 19 1 23 1 
0 
Output: 
353 1 13 1 
31 1 3 1 2 1 
41 1 7 1 5 1 2 1 
3079 1 
7 4 5 1 
449 1 2 1 
3457 1 7 1 
7 1 5 1 3 1 2 4 
127 1 2 1 
619 1 3 1 2 2 

閒聊

最近狂殺質數題。

UVa 406 Prime Cuts

寫得時候頭腦不是很清楚
有點亂,不夠漂亮,只能算剛好AC而已

UVa 11462 Age Sort

很偷懶...這題用counting sort說不定比較快

2009年11月22日 星期日

UVa 10200 Prime Time

我一直以來使用的簡單質數檢驗法栽在這題,TLE
上網找了一下,發現2倍數可以先去掉不除
雖然只是簡單的小技巧,但效果很明顯
檢驗過程時間降了一半

就靠著這樣AC了

UVa 10533 Digit Prime

最近都在研究質數問題

本題因為IO量極大
原本只建了質數表,發現不夠快(TLE)
索性連DigitPrime累計表也建起來
dpCum[n]: 從0~n 累計總共有幾個Digit Prime
這樣每筆測資的時間就降到O(1)

這陣子學了不少質數的技巧
像是這題用的高速篩法

像這種百萬等級的問題,建表都很快
另一題大到十億左右,建表就太慢了

UVa 591 Box of Bricks

zz...輕鬆簡單的小題

2009年11月19日 星期四

在Code::Blocks上使用GDB

  1. Project's Build Option -> Compiler選項
    Produce debugging symbols(-g) (打勾)
    Strip all symbols from binary(-s) (不要勾)
  2. 插入Break point
  3. 左邊 "Watches" Tag -> right click "Add watches" -> 輸入 variable name
  4. re-build
  5. press "F8" into debug mode
  6. press "step into" to see the variable content step by step

2009年11月18日 星期三

UVa 11388 GCD LCM

花了點時間推導才發現原來是個送分題
因為GCD,LCM的GCD,LCM就是自己呀...

2009年11月12日 星期四

UVa 101 The Blocks Problem

解題策略

模擬機器手臂推方塊,典型的模擬題,乖乖照著命令的意思操作方塊,然後細心一點吧。

這題雖然有四個命令 [move/pile] a [onto/over] b,但是仔細觀察,就發現命令只分成兩種,一種是搬動方塊之前,要把目標上面的方塊都歸位(move/onto),另一種是整疊方塊直接跟著搬動(pile/over)。

以下的程式,move()是搬動方塊,clear_above()是歸位的動作。整個處理的主迴圈就長這樣:
// 指令格式 [move/pile] a [onto/over] b
    while( scanf("%s %d %s %d", cmd1, &a, cmd2, &b)==4 ) {

        // 排除不合理的命令
        if(a==b) continue;
        if( in_the_same_stack(a,b) ) continue;
 
        // [move a] 把a上頭的方塊都歸位,[pile a] 則什麼都不做。
        if( strcmp("move", cmd1)==0 ) 
            clear_above(a); 

        // [onto b] 把b上頭的方塊都歸位,[over b] 則什麼都不做。
        if( strcmp("onto", cmd2)==0 ) 
            clear_above(b);

        // 搬動方塊
        move(a,b);
    }

閒聊

把年以前寫的爛code重新整理了一番,把linked list換成vector,速度也小進: 0.030s -> 0.008s。

以下完整code。


2009年11月4日 星期三

UVa 10050 Hartals


/*
* UVa 10050
* Author: chchwy
* Last Modified: 2009.11.4
*/
#include <iostream>
#include <bitset>

#define MAX 3651

int countHartals(){
int numDay, numParty;
scanf("%d %d ", &numDay, &numParty);

std::bitset<MAX> day; //1-3650

for(int i=0;i<numParty;++i){
int hartal;
scanf("%d ", &hartal );

for(int i=0;i<=numDay; i+=hartal ){
if( i%7 == 0 || i%7 == 6) //friday & saturday
continue;
day.set(i);
}
}
return day.count();
}

int main(){
#ifndef ONLINE_JUDGE
freopen("10050.in","r",stdin);
#endif

int numCase;
scanf("%d ", &numCase);

while( numCase-- )
printf("%d\n", countHartals() );

return 0;
}



用bitset實做,快又有效。

2009年11月3日 星期二

UVa 10315 Poker Hand

寫這支程式比較像在做苦工,因為規則實在很繁瑣,
當初我差點要寫不下去,後來轉念一想,就當作給自己一個挑戰,把繁雜的事情寫得有條有理。

這是我第一次嘗試將Unit Test應用在UVa題目上(拿來對付這種煩人題目剛好)
成果很不錯,只要有強大完整的Test Case在,根本就不用怕改爛程式碼,或者是改東邊炸西邊這種事情發生。
所以我在後期也大膽的修正了兩次架構,目前看起來算滿意,整個程式架構相當清楚,而且一次就AC了。
附上我的TestCase
ps.我用的是GTest (Google C++ Testing Framework)

題外話,最近跟0.008秒有緣,我已經連三題0.008秒AC了 XDDDDD

2009年8月14日 星期五

UVa 10071 Back to High School Physics

Back to High School Physics ....
真的很像高中物理題目...在紙上推導了一下


#include <stdio.h>

int main(){
int v,t;
while( scanf("%d %d", &v, &t)==2 )
printf("%d\n", 2*v*t );
return 0;
}

2009年8月13日 星期四

UVa 10055 Hashmat the Brave Warrior

解題策略

看似簡單,的確也不難,只是有很基本的東西要注意。XDDD

附上測資
0 4294967296
2 4294967296
0 4294967295
2 4294967295

這題測資剛好會超過int(long)的有效範圍,所以必須用 long long 或者 double。

閒聊

ACM真是有趣....而且殘酷....在最基本的地方栽跟頭,毫不留情。

#include <cstdio>
#include <cmath>
int main(){

    double hashmat, enemy;

    while( scanf("%lf %lf ", &hashmat, &enemy )==2 )
        printf("%.0lf\n", fabs( enemy-hashmat ) );

    return 0;
}

2009年8月10日 星期一

UVa 10038 Jolly Jumpers


#include<iostream>
#include<bitset>
using namespace std;

#define MAXSIZE 3000

int main(){

#ifndef ONLINE_JUDGE
freopen("10038.in", "r", stdin);
#endif

int length; //the length of sequence
int seq[MAXSIZE];
bitset<MAXSIZE> s;

//for each case
while( scanf("%d ",&length)==1 ){

//read sequence
for(int i=0;i<length;++i)
scanf("%d ", &seq[i] );

if(length==1){
puts("Jolly");
continue;
}

s.reset(); //init set

//add into set
for(int i=1;i<length;++i){
int diff = abs( seq[i] - seq[i-1] );
if(diff>0 && diff<length)
s.set(diff);
}

//judge
if( s.count() == length-1 )
puts("Jolly");
else
puts("Not jolly");
}
return 0;
}


一次AC !!! 太爽啦~

做法就不講了,我是用Algorithmist的作法,如下
http://www.algorithmist.com/index.php/UVa_10038

Set應用題,非常簡潔俐落的作法...虧我之前還在想一堆有的沒的。
bitset的速度也讓我驚豔, 0.008s ,相當的快!!

2009年6月25日 星期四

PHP Developer's Cookbook

「經典就是大家都希望曾經讀過卻又沒人想讀的作品」— 馬克吐溫

我有一堆與程式設計相關的書籍,一冊冊完好如初地擺在我的書架上,這些書曾經影響我程式設計的方式和風格,它們是程式設計師塑造個人哲學的聖經。

不過我也有其他書籍,有的置於書桌上,有些則散落在床邊及客廳沙發上。
這些書多半已破舊、變形且沾滿咖啡漬。那是我賦予它們的最高榮耀,因為它們本來就是實用性的書籍,我參考這些書籍並解決每天碰到的問題。

這本書的目的也是如此。

寫作動機也是期望它能幫你解決每天碰到的程式設計問題。
你所賦予它的最大榮耀就是使用它—想辦法讓它對你有用處,即使~你偶爾拿內頁擦拭濺到的咖啡也無妨!



相當迷人的書序,讓我也不禁想要找這本書來看看了

2009年4月28日 星期二

UVa 116 Unidirectional TSP

簡化版旅行推銷員問題,用DP解

這題我的醒悟就是,用演算法不要太死腦筋
因為這題有一個機歪點,就是如果有多條權重相同的最短路徑,要輸出字典順序最小的那一條。

如果從起點往後DP,那麼字典順序很難解
如果從終點DP回來起點,那麼字典順序自然而然解決了。

瞭解演算法以後,果然還是要靈活使用才行。


附上測資
應該足夠應付各種狀況了

2009年4月21日 星期二

UVa 107 The Cat in the Hat

解題策略

這題的關鍵其實就是找N (廢話...),每隻貓都可以從帽子中變出N隻小貓,小貓的高度是 1/(N+1) ,所以有N一切的謎底就都解開了。我的做法也很簡單,就是用個for迴圈去代 n ,然後比對最後工作的小貓數量,直到符合為止。

一個可能蠻有用的測資
483736625 481890304
0 0
答案是 615441 1931252289,找出來的N應該是784。

注意

官網論壇上面很多亂七八糟的測資,像是(3 1), (5 1), (7 1) 等等除不盡的測資,請 完 全 不 要 管 這些東西。所有合法測資都是剛剛好整除的整數,貓的初始高度也一定是某數的完全次方。

閒聊

開心,終於達成100~113連號答題,整排都是綠色的AC看起來就很爽。雖然不是用很數學的方式,但是這個解法是我自己想出來的,相當有成就感。

2009年4月20日 星期一

UVa 10196 Check The Check

有趣,但是很繁瑣的題目。
我還花了很長的時間想要怎麼把check的程式簡化縮短,後來發現沒什麼好辦法,就直接爆破了。

1. 用12*12的棋盤可以省掉很多邊界檢查。
2. 從king出發去找敵棋,比較快;用其他棋子去找king,比較慢。

0.000秒AC \(>﹏<)/

2009年4月7日 星期二

UVa 10267 Graphical Editor

好有趣的題目。
不過因為參考網路上某份code,實做錯誤的BFS,導致好幾次TE= =a。
話說這好像是我第一次親手實做BFS ?
自己寫了一個Queue,看起來速度很快。
最後AC 0.020秒 Ranking 51

有兩點注意
1. V的y1,y2,測資有可能y1>y2。H也一樣。
2. fillRegion若目標顏色跟原色相同,那就不用做了。


2009年4月2日 星期四

UVa 10142 Australian Voting

弄了我三天的題目,深深覺得自己還未夠班。
Ranking 136, 但是Run Time相當不理想: 0.760。不知道要怎麼壓到0.2秒以下。

提供下面這份測資,非常關鍵,我通過這份測資後就一次AC了。
來源:http://online-judge.uva.es/board/viewtopic.php?p=49650#49650


7

2
i am jalal
he is Hasan
1 2
2 1


3
L
P
M
1 2 3
1 3 2
2 3 1
2 1 3
1 3 2
2 3 1

6
A
B
C
D
E
F
2 1 6 5 3 4
6 3 2 5 4 1
5 2 6 1 3 4
3 6 1 5 2 4
1 2 4 6 3 5
3 2 5 6 1 4
5 6 2 4 3 1
5 3 1 4 2 6
2 4 5 6 3 1
2 5 3 4 6 1

4
jalal
hasan
bijon
saiket
1 2 3 4
3 1 2 4
1 2 3 4
2 1 3 4
3 1 2 4
4 3 1 3

3
John Doe
Jane Smith
Sirhan Sirhan
1 2 3
2 1 3
2 3 1
1 2 3
3 1 2

3
John Doe
Jane Smith
Sirhan Sirhan
1 2 3
2 1 3
2 3 1
1 2 3
3 1 2

4
jalal
hasan
bijon
saiket
1 2 3 4
2 1 3 4
1 2 3 4
2 1 3 4
3 1 2 4
4 2 1 3



正解

i am jalal
he is Hasan

L
P

B

jalal
bijon

John Doe

John Doe

jalal
hasan



2009年3月26日 星期四

UVa 10137 The Trip

引用某個解題者的話:This problem IS a trip.

乍看很簡單,但是很容易在浮點數精確度上吃悶虧。
最後我全部轉成int來運算,確保一切在掌握之內。

兩點提醒
1. 平均開銷算出來以後要四捨五入到小數第二位(1 cent)
2. 因為平均開銷不精確,所以exchange amount 要統計兩個,輸出小的那一個。


UVa 10033 Interpreter

蠻有趣的一題,還好距離組語記憶還不算太久。
朝每天至少一題邁進吧。 目前是第二天^+++++^

ps. 雖然我很想以德國人般的嚴謹來面對UVa Online Judge的格式要求。
但常常跟空白、換行對抗感覺不太好...orz

ps2. 距離一次AC的目標又進了一步。這題兩次AC。



2009年3月24日 星期二

UVa 706 LCD Display


簡單的問題,但是有些機歪的狀況

摘自UVa forum by kckckc
1. Space or NewLine that have mentioned in previous Post.
2. Maybe the code will meet some problem in some input sets such as
input is X 0
3. I didn't handle the leading 0 situation,
that means if input is 00007, my out put is 7.


所以下面這是關鍵測資
10 99999999
3 00007
5 0
0 0

UVa 10189 Minesweeper

小題目。
寫完很久了,不知為何忘了放上來。

最近被848 FMT弄得心煩意亂,唉。

2009年3月18日 星期三

[ACM] 常用程式片段

Debug用
#ifndef ONLINE_JUDGE
freopen("848_input.txt", "r",stdin);
freopen("848_output.txt","w",stdout);
#endif

進階版getch(), ungetch() (from K&R)
// ungetch(): push a char to stack
// getch(): if stack is not empty, pop a char
//          or get a char from stdin.

int buffer[1024];
int top = -1; //stack pointer

void ungetch(int c){
    buffer[++top] = c;
}

int getch(){
    if(top > -1)
        return buffer[top--];        
    else
        return getchar();
}

2009年3月13日 星期五

最後一天了

不管結果如何,再一天,這樣的日子都要成為過去了。
有一點苦澀,又有一點懷念。

2009年1月1日 星期四

UVa 113 Power of Cryptography

之前看到p值的範圍(10101),以為要做大數,實際上只要用double就行了,難度相當低的一題。