ProjectEuler 688 - Solution

ProjectEuler#688 第19名！！！

ProjectEuler 666 - Solution

不知不覺ProjectEuler已經出到第666題了！

666 - 魔鬼的印記

但題目卻不是那麼魔鬼，剛開始像是墜入五里霧中，了解其原理後才發現意外的簡單。不過就是列式子外加疊代，大約只要50次的疊代就可以達到14位的精度。題目只要求8位的精度實在太低了-_-


附帶一提， 這題刷新了我在fastest table的最低名次，第97名--__--

ProjectEuler 663 - Solutions

這題大家都說要用線段樹(segment tree)，可是我不會用啊！我當然知道線段樹，只是不知道要如何將線段樹用在這題？

觀察到要更動的項數很少，大約是2*10^5項，忽然想到區間查詢可以將 陣列分割成Sqrt(N)個區間來做。對於S(N,m)-S(N,n)有著(m-n)*N^0.5的複雜度。依題目的要求，大約是6.3*10^8的計算量。最後程式跑了15秒！1分鐘以內，算是達標了！第23名。就憑著這23名，讓我又回到歐拉人的前20名。175分，歐拉人第15名！！！

ProjectEuler 657 and ProjectEuler 658

本週一次出兩題，第657題跟658題，應該又是賺分的機會了。每次出兩題的時候，我都有很大的機會可以賺到分數。

沒想到這次657題居然跟我在某個地方曾經做過的題目幾乎一模一樣。只有兩個地方不一樣，原題要求的是complete word的數目且word不允許某些字元為開頭。然而這兩個不一樣的地方還是讓我想了一會兒，最後用了20分鐘解出這題，撈到個第8名真是超爽der。20分鐘0秒創了我個人史上最快紀錄，之前保持的最快紀錄是解第581題的20分55秒，那時拿到了第5！

拍個照留念一下，以後要拿前10名，機會不太多了。

ProjectEuler 652 - Solution

這大概是我題目讀得最久的一次。花了將近一個小時還是讀不懂這兩句。

$\quad \, \, \, \, g(m_1,n_1)=g(m_2,n_2)$ if any integers $a,b,e,f$ fulfilling 1. or 2. can be found

and $\, g(m_1,n_1) \ne g(m_2,n_2)$ if no integers $a,b,e,f$ fulfilling 1. or 2. can be found

最後發覺時間不能再耗下去，決定從題目給的測資下手，$D(5)=13$, $D(10)=69$, $D(100)=9607$ 且 $D(10000)=99959605$

然後靈機一動，想到會不會是指那個？試了一下果然是....
原來$D(N)$是指在$2\le m, n\le N$的情況下${log}_mn$不同值的個數。例如${log}_22$跟${log}_33$的值都是1，因此視為相同。

很快的寫了程式驗證一下，果然是 $D(5)=13$, $D(10)=69$, $D(100)=9607$ 且$D(10000)=99959605$

ProjectEuler 645 Every Day is a Holiday

前幾天在解 ProjectEuler第645題《 Every Day is a Holiday》

大意是說，宇宙上某一個星球上一年有D天，一開始的時候，沒有一天是假日。當第一個統治者來的時候，他的生日變成假日，然後這個統治者可能駕崩，之後換第2個統治者來統治的時候，他的生日又變成假日(第一個的統治者的生日依然是假日)，然後換第三個統治者來統治的時候，他的生日又是假日(第一跟第二個的統治者的生日依然是假日)，如此不斷的繼續下去‧‧‧這個星球還有一個特點，如果某一天的前一天跟後一天都是假日，這一天也必然成為假日。而且成為假日後絕對不會被砍假。我們假設每一個統治者出生於D天中的每一天是機會均等的。求使得D天中每一天都是假日的統治者數目的期望值。令E(D)為這個期望值。題目給出了 $E(2)=1$, $E(5)=31/6$, $E(365)\approx 1174.3501$

有點鳥的題目，而且也沒說清楚到底每一年的最後一天可以當作隔年第一天的前一天嗎？用紙筆仔細算了一下，好像這條件必須為真才能得到E(5)=31/6

然後就陷入長考中‧‧‧似乎不是簡單的題目‧‧‧

就在這個時候，不可思議的事發生了！

ProjectEuler 636 - Solution

早上5點起來，腦袋還沒完全清醒就開始做題了。剛讀完題目沒有任何想法，不過愈看愈眼熟，咦？這不就是ProjectEuler之前出過的某道題目嗎？當然，不完全一樣，是個變化題型。

還好在出那道題目時我有把當初的解法寫成講義，裡面甚至有我親自寫的詳細解題過程跟公式，不過由於已經是好多年前，解法差不多全忘光了，只好一邊看著講義一邊慢慢回想當初是怎麼解的？