Code Workshop: 8月 2016

2016年8月26日星期五

[C_MM275-易] 字串之編碼數值總和

http://e-tutor.itsa.org.tw/e-Tutor/mod/programming/view.php?id=20485

這題把字串放入字元陣列中再一一的相加

[C_MM252-易] 十進位轉二進位

http://e-tutor.itsa.org.tw/e-Tutor/mod/programming/view.php?id=15774

這題利用Integer.toBinaryString()轉換成二進位,但題目要求32位數所以前面要補齊0

2016年8月23日星期二

Q10494 - If We Were a Child Again

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

這題要一個一個去讀取如果用字串去切割空白會Runtime error
最後做大數的運算

Q1225 - Digit Counting

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

這題就把每個數字丟到陣列一個一個存入1~9 arr[ 9 ]

2016年8月17日星期三

Q10323 - Factorial! You Must be Kidding!!!

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

這題就是判斷階層結果大於6227020800就Overflow小於1000(不包含負數)Underflow
當負數時偶數-2 -4 -6...為Underflow 奇數-1 -3 -5...為Overflow
先利用DP建立1001個階層表當輸入值大於1000直接Overflow
補充:
比較大小
int i=b1.compareTo(b2)
i可能為-1、0、1，分别表示小於、等於、大於
i=-1 ==> b1<b2
i=0 ==> b1=b2
i=1 ==> b1>b2

Q10220 - I Love Big Numbers !

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

這題是算出階層後每一個位數的總和最大測資有1000階層會爆所以要利用大數運算動態配置儲存1000筆資料
叫出每一個位數BigInteger先變成字串toString( )再拆成字元陣列toCharArray( )
注意當0!輸出1

Q623 - 500!

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

這題最大測資有1000階層會爆所以要利用大數運算動態配置儲存1000筆資料

ITSA 串接字串

http://e-tutor.itsa.org.tw/e-Tutor/mod/programming/view.php?id=29581

寫一支可以串接字串的程式。要求如下。給兩個字串s₁及s₂，將這兩個字串串接起來，得到一個新的字串s₃。s₃要滿足底下的要求：

1. s₁字串在前面

2. s₂字串在後面

3. s₃是s₁及s₂所串起來的字串中，最短的字串。

關於第3點，我們用底下的例子來解說：

例1：

s₁ = “birthday”

s₂ = “daylight”

所以s₃=”birthdaylight”

例2：

s₁ = “birthdays”

s₂ = “daylight”

那 s₃ = “birthdaysdaylight”

例3：

s₁=”abc”

s₂=”bcdef”

那s₃=”abcdef”

輸入

輸入的第一行是一個整數N，其代表了共有N個字串。0 < N <= 1000 。接下來的N行包含了N個字串，每個字串為一行。每一個字串的長度介於1到100之間。

輸出

請將這N個字串串接的結果輸出。

Sample Input:	Sample Output:
3 abc bcdef g	abcdefg

這題做法是用要插入的字串去比對要被新增的串列中是否有重疊的字串所以從最大長度開始遞減假如跟str有重疊就插入s[i]後面的子字串

Q455 - Periodic Strings

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

這題要算出最短的重複子字串的字母個數,要注意測資可能有空白行所以要重讀取,而且每個答案之間要多空一行
Periodic String=>http://www.csie.ntnu.edu.tw/~u91029/LongestCommonSubstring.html

Q10298 - Power Strings

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

這題就是要找出最短子字串且算出有幾個重複
程式架構是子字串1~n一個一個去跟原本字串做比對
if(str.length()%sub.length()!=0)

continue;
這個是判斷子字串是否為原本字串的倍數否就繼續執行下一個迴圈
補充若子字串用String會超時所以必須要用StringBuffer 每次append一個字母進去

2016年8月16日星期二

Q10101 - Bangla Numbers

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

這題就是就是把每個除出來的數字除到剩二位為止,利用疊代直到0為止
當輸入0時直接印出0一開始空四格

2016年8月15日星期一

[C_ST59-易] 字串旋轉運算

http://e-tutor.itsa.org.tw/e-Tutor/mod/programming/view.php?id=8314

這題這題會給五組資訊每一組有兩個數字分別為更改位置的索引值以及左移或右移的數目
當(索引值+上位移數)%26小於0要加回26,並且位移的對象為a~z所以要建立兩個a~z陣列一個是原本乾淨沒位移過的一個是放答案的陣列

[C_ST76-易] 文字解密

http://e-tutor.itsa.org.tw/e-Tutor/mod/programming/view.php?a=6839

這題處理字串切割要比較麻煩除了英文字母其他的都要捨去(包含數字標點符號空白),所以要利用政則表達是來切出字串,所以先用split( " [ 0-9-\\pP ] " ) 分別切出0~9(\d)以及標點符號 \pP是代表萬國碼字元雙引號內要跳脫字元所以兩個反斜線,最後切出來的s1以及s2長度不一因為空白也切進去了所以建立一個List儲存非""的字串
That 1000 treasure was not in City. =>That treasure was not in City
That power is not at Chiayi123. =>That power is not at Chiayi

Q10420 - List of Conquests

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

這題就只是紀錄國家數目(國家要排序)注意一開始可能有空白所以要用tirm( )把前面空白省略

Q11115 - Uncle Jack

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

這題只是D的n次方因為每個CD都不同分給大家
例如3個CD分給5個人有3*3*3*3*3種分法
由於這題測資會有10的25次方所以要用大數運算
可參考這篇:http://blog.xuite.net/wang620628/twblog/126093649-%E5%B0%876%E4%BB%B6%E7%89%A9%E5%93%81%E5%85%A8%E9%83%A8%E6%94%BE%E5%85%A54%E5%80%8B%E7%AE%B1%E5%AD%90%E5%85%A7%EF%BC%8C%E8%AB%8B%E5%95%8F%E4%B8%8B%E5%88%97%E6%9C%89%E5%B9%BE%E7%A8%AE%E6%94%BE%E6%B3%95%3F

ITSA 47 [Problem 5] Geodesic Distance

http://e-tutor.itsa.org.tw/e-Tutor/mod/programming/view.php?id=30637

這題請參考這篇文章當S或W時要變成負數
http://fecbob.pixnet.net/blog/post/43546822-%5Bjava%5D-%E7%B6%93%E7%B7%AF%E5%BA%A6%E8%B7%9D%E9%9B%A2%E8%A8%88%E7%AE%97

[C_MM060-易] 疊積木

http://e-tutor.itsa.org.tw/e-Tutor/mod/programming/view.php?id=2000

這題先用迴圈遞增算寬然後得出高就能利用三角形勾股定理求出對角長了

[C_MM119-中] 計算兩個整數 m 和 n 的商，精確至小數點下任意位

http://e-tutor.itsa.org.tw/e-Tutor/mod/programming/view.php?id=3063

這題要使用大數BigDecimal 除法 a.divide( b,n,BigDecimal.ROUND_HALF_EVEN ).toPlainString()
要注意測資可能很大會變成科學記號所以要使用toPlainString

/*
BigDecimal.ROUND_CEILING　正數無條件進入,負數無條件捨去
BigDecimal.ROUND_DOWN 　無條件捨去到 scale 位
BigDecimal.ROUND_FLOOR　正數無條件捨去，負數無條件進入
BigDecimal.ROUND_HALF_DOWN　四捨五捨六入
BigDecimal.ROUND_HALF_EVEN　四捨六入,五入捨後該scale位數值必需為偶數
BigDecimal.ROUND_HALF_UP　四捨五入
BigDecimal.ROUND_UP　無條件進入到 scale 位
*/

[C_MM115-中] 奇妙數列

http://e-tutor.itsa.org.tw/e-Tutor/mod/programming/view.php?id=2969

這題S(n)=S(n-1)+T(n-1),並且注意T(n)的值不在S(n)中

2016年8月14日星期日

[C_MM145-易] 質因數分解

http://e-tutor.itsa.org.tw/e-Tutor/mod/programming/view.php?id=3631

這題要使用long迴圈下去除

[C_MM058-中] 二項式求解

http://e-tutor.itsa.org.tw/e-Tutor/mod/programming/view.php?id=1903

迴圈從0開始下去跑,跑到c/a為止,一一下去做判斷是否整除

Q568: Just the Facts

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

這題是要找階層後尾部數過來低一個不為0的數,測資最大可能有10000階層肯定會爆
所以每乘1次要把尾數0去掉,最後再%100000

Q357: Let Me Count The Ways

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

這是動態規化的問題題目限定範圍所以建立一個30001的陣列,一開始先把全部初始化1
然後再一個個幣值dp[]相加

Q530: Binomial Showdown

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

r取k有公式=>r ! / ( r - k ) ! * k ! ,也就是斯巴卡三角形注意溢位的問題
另外要考慮到 C10取1 跟C10 取9 是一樣的,做一下轉換就能避免超時的問題

2016年8月13日星期六

Q386: Perfect Cubes

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=&problem=322&mosmsg=Submission+received+with+ID+17836106

四個迴圈結束

Q382: Perfection

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=&problem=318&mosmsg=Submission+received+with+ID+17836051

完美數的求法利用圈1~n-1判斷是否整除(求公因數)若全部加總等於n就是PERFECT

2016年8月12日星期五

[C_SO36-易] 我想要聯誼

http://e-tutor.itsa.org.tw/e-Tutor/mod/programming/view.php?id=15532

把每個人的分數存入字串之後再跟要求的cp去一個一個比對是否出現在字串中(indexOf)

[C_SO41-中] 撲克牌排序

http://e-tutor.itsa.org.tw/e-Tutor/mod/programming/view.php?a=10530

這題利用List排序做翻轉

[C_SO09-易] 字串重排

http://e-tutor.itsa.org.tw/e-Tutor/mod/programming/view.php?a=1436

這題算出1有幾個就印出來就行了其餘印0

[C_SO03-中] 最遠的兩點

http://e-tutor.itsa.org.tw/e-Tutor/mod/programming/view.php?id=1936

這題取兩點不重複所以利用雙迴圈去把可能列出來做比對

[C_MM247-易] 環狀排列

http://e-tutor.itsa.org.tw/e-Tutor/mod/programming/view.php?id=15578

n個人有 n!/n個方法

2016年8月11日星期四

2016年8月8日星期一

[C_MM114-易] 進位轉換

http://e-tutor.itsa.org.tw/e-Tutor/mod/programming/view.php?id=2856

這題是字串轉任何進位所以要Integer.parseInt("字串",轉換位數成10進位)

[C_MM102-易] 小蝸牛

http://e-tutor.itsa.org.tw/e-Tutor/mod/programming/view.php?id=2651

這題要注意單位換算然後迴圈進入先扣除往上爬是否小於等於0再加上往下滑,只要小於0就跳出迴圈了

2016年8月7日星期日

[C_MM254-易] 切蛋糕問題

http://e-tutor.itsa.org.tw/e-Tutor/mod/programming/view.php?id=15780

這題可依發現他是個有遞增的數列2 4 7 11 16 分別加2 3 4 5

2016 闖關組 [Problem B11] Rotate around a circle

http://e-tutor.itsa.org.tw/e-Tutor/mod/programming/view.php?id=30527

這題用模擬會溢位,所以要用數學方法解,環狀位置要用餘數運算
我們可以遵循它的規律
D會員人數 K會員代號 N換位次數 L每次移動距離
ex:
會員代號偶數時
8 3 2 1
原本位置 4 3 2
第一次換位結果 6 3 4
第二次換位結果 8 3 6
推導出
((k+1)-(2*N*L))%D =>8//因為偶數逆時鐘所以減若為負數加上D

會員代號奇數時
8 4 2 1
原本位置 5 4 3
第一次換位結果 3 4 1
第二次換位結果 1 4 7
((k+1)+(2*N*L))%D =>1//奇數順時鐘所以加

最後當數字為0時要變成D

2016年8月6日星期六

[C_GD02-難] Busy day

http://e-tutor.itsa.org.tw/e-Tutor/mod/programming/view.php?id=23932

這題不要想太多直接全部加起來判斷是否為偶數

[C_GD03-易] 線段切割

http://e-tutor.itsa.org.tw/e-Tutor/mod/programming/view.php?id=23935

把數字連加當大於num跳出迴圈輸出i-1

[Problem B1-易] Eigenvalues of a 2x2 Matrix

http://e-tutor.itsa.org.tw/e-Tutor/mod/programming/view.php?id=23222

這題使用公式解 2A分之負B正負根號b平方減4AC
就能求出xy解

Q10684 : The jackpot

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=&problem=1625&mosmsg=Submission+received+with+ID+17796056

這題使用貪婪法,一個有序的數列中,累積總和遇到負數歸零,時間複雜度O(N)

2014 闖關組 [Problem B5-易中] Apple trees in a line

http://e-tutor.itsa.org.tw/e-Tutor/mod/programming/view.php?id=23212

這題使用貪婪法,累積總和遇到負數歸零,時間複雜度O(N)

2014 闖關組 [Problem B2-易] Computing C(n,k)

http://e-tutor.itsa.org.tw/e-Tutor/mod/programming/view.php?id=23224

2014 闖關組 [Problem B3-易] Rock-paper-scissors-lizard-Spock

http://e-tutor.itsa.org.tw/e-Tutor/mod/programming/view.php?id=23226

2016年8月4日星期四

2015 闖關組 [Problem B5-中易] Coin Change(換零錢方法數)

http://e-tutor.itsa.org.tw/e-Tutor/mod/programming/view.php?id=23650

這題利用動態規劃先把1~15000的換錢方法存入陣列(long)
coins[ ]={1,5,10,20,50}
1.首先建立dp[15001]個陣列並每個存1(一元的分法)
2.外迴圈從coin[i=1]開始~coin[4]內迴圈從j=coin[i]開始~15000,dp[ j ]+=dp[ j-coins[i] ]
ex:10元
i=1時
dp[10]+=dp[10-5]=1+2=3
i=2時
dp[10]+=dp[10-10]=3+1=4

2016年8月3日星期三

2016 闖關組 [Problem B10] Password Complexity

http://e-tutor.itsa.org.tw/e-Tutor/mod/programming/view.php?id=30526

這題要注意可能會溢位必須要用BigInteger,有大小寫區分
ex: 排列組合abbccc =>6!/(1!*2!*3!)

2016 闖關組 [Problem B1] Product and remainder

http://e-tutor.itsa.org.tw/e-Tutor/mod/programming/view.php?a=15733

這題要注意可能會溢位必須要用BigInteger,每個數相乘直到餘一為止

2016年8月26日 星期五

2016年8月23日 星期二

2016年8月17日 星期三

2016年8月16日 星期二

2016年8月15日 星期一

2016年8月14日 星期日

2016年8月13日 星期六

2016年8月12日 星期五

2016年8月11日 星期四

2016年8月8日 星期一

2016年8月7日 星期日

2016年8月6日 星期六

2016年8月4日 星期四

2016年8月3日 星期三

2016年8月2日 星期二

2016年8月1日 星期一