Q10994: Simple Addition(真正uva會過版)
Q10036 - Divisibility
Q11413 - Fill the Containers (還沒寫出來)
Q10036 - Divisibility
Q11413 - Fill the Containers (還沒寫出來)
離上篇離了也太久了吧2011-5-25的我都快刷完了
我討厭牛奶阿!!!
為了先後順序先弄這篇未完成品
題外話:最後放水也放太兇了吧~GJ
我討厭牛奶阿!!!
為了先後順序先弄這篇未完成品
題外話:最後放水也放太兇了吧~GJ
Q10994: Simple Addition
日子過太久細節都忘光了(這好像是在不知什麼課上導的吧)
基本上他就是一直加由右至左第一個不為0的數也就是1~9
S(1,10)=(1+2+3+....+9)+1=45+1
S(1,20)=(1+2+3+....+9)+1+(1+2+3......+9)+2=45*2+3
另外由於會出現1 TO 2147483647 這種極端測資所以請注意答案會超過INT
日子過太久細節都忘光了(這好像是在不知什麼課上導的吧)
基本上他就是一直加由右至左第一個不為0的數也就是1~9
S(1,10)=(1+2+3+....+9)+1=45+1
S(1,20)=(1+2+3+....+9)+1+(1+2+3......+9)+2=45*2+3
另外由於會出現1 TO 2147483647 這種極端測資所以請注意答案會超過INT
不像樣的參考解答,內收
加映~JAVA版~(會超時)
明明算法一樣卻會TLE~真不愧是JAVA,內收
還沒學所以不會修正~應該是IO太慢的問題、之後等有人教再處理~
(PS1.我還是比較喜歡寫C++阿~超自由的XD 自由到怎麼錯的都不曉得= =|||
PS2.JAVA限制好多.....居然不予許自動轉換型別= =|||
PS3.第一次寫果然還是該Hello World!
)
Q10036 - Divisibility
我去Methods to Solve 看解題提示之後弄出來了XD
歡樂的DP(動態規劃)題
提示照轉
(PS1.我還是比較喜歡寫C++阿~超自由的XD 自由到怎麼錯的都不曉得= =|||
PS2.JAVA限制好多.....居然不予許自動轉換型別= =|||
PS3.第一次寫果然還是該Hello World!
)
Q10036 - Divisibility
我去Methods to Solve 看解題提示之後弄出來了XD
歡樂的DP(動態規劃)題
提示照轉
10036 - Divisibility (By: Gawry)
Looks simple but if you use brute force (count all possible values of +/- for N numbers) then determine whether it is divisible by K or not, then your solutions possibly get Time Limit Exceeded.
Use mathematical properties + Dynamic Programming
Let d[1],...,d[N] be sequence of N integers and t[I,J] (2 dimensional array, but after some considerations, we'll find out that we only need 2 linear array of size J) be true iff we can place +/- operators in the sequence of first I integers so that result = J (mod K).
We can use DP to calculate t[I,J] for all [I,J]:
for i=1
t[1,j] = true for t[1,j] where j=abs(d[1]) mod K
This means: You divide one integer (the first integer from N integers) with K, get the remainder, t[1,remainder] is set to be true.
for i>1
if t[i-1,j] true then
t[i,(j+abs(d[i]) mod K] = true /* add */
t[i,(j+K-abs(d[i]) mod K] = true /* substract */
This means: For the 2nd integer up to Nth integer, you either add it with previous remainder modulo K or substract it with previous remainder modulo K, to get another remainders in the range [0..K] that can be reached using combination of i integers.
Answer should be Divisible iff t[N,0], which means, you can arrange +/- operators in the sequence of N integers, with remainder 0 / divisible.
Looks simple but if you use brute force (count all possible values of +/- for N numbers) then determine whether it is divisible by K or not, then your solutions possibly get Time Limit Exceeded.
Use mathematical properties + Dynamic Programming
Let d[1],...,d[N] be sequence of N integers and t[I,J] (2 dimensional array, but after some considerations, we'll find out that we only need 2 linear array of size J) be true iff we can place +/- operators in the sequence of first I integers so that result = J (mod K).
We can use DP to calculate t[I,J] for all [I,J]:
for i=1
t[1,j] = true for t[1,j] where j=abs(d[1]) mod K
This means: You divide one integer (the first integer from N integers) with K, get the remainder, t[1,remainder] is set to be true.
for i>1
if t[i-1,j] true then
t[i,(j+abs(d[i]) mod K] = true /* add */
t[i,(j+K-abs(d[i]) mod K] = true /* substract */
This means: For the 2nd integer up to Nth integer, you either add it with previous remainder modulo K or substract it with previous remainder modulo K, to get another remainders in the range [0..K] that can be reached using combination of i integers.
Answer should be Divisible iff t[N,0], which means, you can arrange +/- operators in the sequence of N integers, with remainder 0 / divisible.
看不懂英文直接看程式碼應該也能懂~簡單來講就是開個二維陣列[N,K]儲存第N數加進去時可能會出現的餘數值
從第一個數開始到最後一個數都算完看看[N,0]會不會是可能出現的餘數就可以知道能不能整除了
但是歡樂的C++送了一個非常非常機車的陷阱~因為那東西多花了3~4個小時創造了一排的WA
從第一個數開始到最後一個數都算完看看[N,0]會不會是可能出現的餘數就可以知道能不能整除了
但是歡樂的C++送了一個非常非常機車的陷阱~因為那東西多花了3~4個小時創造了一排的WA
數學太爛學術不經的解答,內收
TLE~TLE~TLE~TLE~TLE~TLE~TLE~TLE~TLE~TLE~TLE~TLE~TLE~TLE~TLE~TLE~TLE~TLE~TLE~TLE~TLE~TLE~TLE
還沒弄出來可以不用把所有解都算出來比較的答案= =|||
倒是弄出兩種會TLE的
剛剛的提示界面
11413 - Fill the Containers
Binary search on the capacity of the largest container and see if such number of containers is enough to contain all the milk according to the stated rules.
﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍
高手建議的解法:Backtracking
因為跟我相性不合大概會先完成別題再補~
還沒弄出來可以不用把所有解都算出來比較的答案= =|||
倒是弄出兩種會TLE的
剛剛的提示界面
11413 - Fill the Containers
Binary search on the capacity of the largest container and see if such number of containers is enough to contain all the milk according to the stated rules.
﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍
高手建議的解法:Backtracking
因為跟我相性不合大概會先完成別題再補~