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