Project Euler 084~087
關(guān)于啥是Project Euler 詳見 https://projecteuler.net/about? ? ???
觀前聲明：? ? ? ? ? ? ??
這是個人興趣使然的對自己入坑pe的記錄，僅提供思路和部分代碼； 各個方面肯定都是有著優(yōu)化與提升空間的，甚至在許多大佬看來這應(yīng)該是初學(xué)者的淺薄而未經(jīng)剪枝的丑碼，如果能幫到有興趣的人自是最好，也歡迎能醍醐灌頂?shù)纳疃扔懻摗??
大佬看到了笑笑就行，還請輕噴。
帶著惡意，抬杠者...俺也噴不過您，也不能拿您咋樣...畢竟這只是我個人興趣使然的行為或者說是學(xué)習(xí)記錄分享。?（說是記錄，但因為是早先寫的所以其實是在各種意義上公開處刑和吐槽自己 并嘗試補救優(yōu)化）
語言是c++，用的VS平臺
前排：本期莫得感情的暴搜機器.
Monopoly odds
Problem 84
In the game,?Monopoly, the standard board is set up in the following way:
A player starts on the GO Square and adds the scores on two 6-sided dice to determine the number of Squares they advance in a clockwise direction. Without any further rules we would expect to visit each Square with equal probability: 2.5%. However, landing on G2J (Go To Jail), CC (community chest), and CH (chance) changes this distribution.
In addition to G2J, and one card from each of CC and CH, that orders the player to go directly to jail, if a player rolls three consecutive doubles, they do not advance the result of their 3rd roll. Instead they proceed directly to jail.
At the beginning of the game, the CC and CH cards are shuffled. When a player lands on CC or CH they take a card from the top of the respective pile and, after following the instructions, it is returned to the bottom of the pile. There are sixteen cards in each pile, but for the purpose of this problem we are only concerned with cards that order a movement; any instruction not concerned with movement will be ignored and the player will remain on the CC/CH Square.
Community Chest (2/16 cards):
Advance to GO
Go to JAIL
Chance (10/16 cards):
Advance to GO
Go to JAIL
Go to C1
Go to E3
Go to H2
Go to R1
Go to next R (railway company)
Go to next R
Go to next U (utility company)
Go back 3 Squares.
The heart of this problem concerns the likelihood of visiting a particular Square. That is, the probability of finishing at that Square after a roll. For this reason it should be clear that, with the exception of G2J for which the probability of finishing on it is zero, the CH Squares will have the lowest probabilities, as 5/8 request a movement to another Square, and it is the final Square that the player finishes at on each roll that we are interested in. We shall make no distinction between "Just Visiting" and being sent to JAIL, and we shall also ignore the rule about requiring a double to "get out of jail", assuming that they pay to get out on their next turn.
By starting at GO and numbering the Squares sequentially from 00 to 39 we can concatenate these two-digit numbers to produce strings that correspond with sets of Squares.
Statistically it can be shown that the three most popular Squares, in order, are JAIL (6.24%) = Square 10, E3 (3.18%) = Square 24, and GO (3.09%) = Square 00. So these three most popular Squares can be listed with the six-digit modal string: 102400.
If, instead of using two 6-sided dice, two 4-sided dice are used, find the six-digit modal string.
玩家從 GO 開始，每次將兩個六面骰子的得分相加來決定他下一步走向的格子（順時針方向）。如果沒有其他規(guī)則的話，可以預(yù)料每個格子被訪問到的幾率是相等的：2.5%。但是，如果落到格子 G2J（去監(jiān)獄 JAIL），格子 CC（公益金），格子 CH（機會）的話，這個分布就會被改變。
除了 G2J 以及 CC 和 CH 中的一張牌能夠讓玩家直接進監(jiān)獄（JAIL）以外，如果玩家連續(xù)三次擲骰子得到兩個相同的數(shù)字，那么第三次玩家也將直接進監(jiān)獄。
在游戲開始時，CC 和 CH 中的牌是亂序排放的。當(dāng)玩家落到 CC 或 CH 時，他從相應(yīng)的牌堆頂上拿一張牌，并執(zhí)行完下面的指令后，將牌放回到牌堆的底部。每個牌堆中有 16 張牌，但是簡單起見在此題目中只考慮涉及到移動的牌，任何不涉及到移動的牌將會被忽略，而且玩家仍然將處于 CC/CH 格子上。
這個題目的核心問題是每個格子被訪問到的可能性。也就是每次擲骰子之后落到某個格子的幾率。因此，除了落到 G2J 的幾率為零以外，落到 CH 的幾率最小，因為落到 CH 后有 5/8 的幾率會再次移動到其他格子。而我們感興趣的是每次擲骰子之后最終落到的那個格子。我們對“只是訪問”和被送到 JAIL不作區(qū)分，我們也同時忽略需要擲一個 double（兩個相同的數(shù)字）才能走出 JAIL 的規(guī)則，只是假設(shè)玩家下一輪自動走出監(jiān)獄。
從 GO 開始對格子編號（00 到 39），我們將這些兩位數(shù)的數(shù)字相連接來得到與格子的集合相對應(yīng)的字符串。
從統(tǒng)計上來說可以得到三個最受歡迎的格子按順序是，JAIL（6.24%）= 10，E3（3.18%）= 24 ，GO（3.09%）= 00 。所以這三個最受歡迎的格子可以用一個六位的字符串表示：102400。
如果我們用兩個 4 面的骰子代替兩個 6 面的骰子，找出代表三個最受歡迎格子的六位字符串。
回想起上次被54題的撲克牌支配的恐懼...
所以我決定粗略說說思路就行了；模擬題，顧名思義難點和有趣的點都在將題中涉及的流程模擬出來，本題也是，模擬出玩家在每格對應(yīng)的行動，使用隨機函數(shù)不斷進行游戲，最后統(tǒng)計落到每個格子的概率即可，模擬的流程題設(shè)就按題設(shè)來即可. 不放代碼了..
ans：101524
Counting rectangles
Problem 85
By counting carefully it can be seen that a rectangular grid measuring 3 by 2 contains eighteen rectangles:
Although there exists no rectangular grid that contains exactly two million rectangles, find the area of the grid with the nearest solution.
在3×2的網(wǎng)格中放置單個長方形，共有18種放法，圖見上。
問最接近2000000種方法的網(wǎng)格的面積。
如果用opt[m][n]來表示m×n網(wǎng)格的長方形放法，那么在腦內(nèi)粗淺的遞推一下可知：
opt[m+1][n]中肯定包含了opt[m][n]的所有放法，且新的放法必定與新多出來的那一行有關(guān)
考慮所有在m+1行有方格的放置情況，
不難得出：opt[m+1][n]=opt[m][n]+(n+1)n(m+1)/2
同理：? ? ? ?opt[m][n+1]=opt[m][n]+(m+1)m(n+1)/2
存數(shù)組，主函數(shù)跑一遍即可.
最接近2000000的解法是36×77的網(wǎng)格，有1999998種放法
ans：2772
Cuboid route
Problem 86
A spider, S, sits in one corner of a cuboid room, measuring 6 by 5 by 3, and a fly, F, sits in the opposite corner. By travelling on the surfaces of the room the shortest "straight line" distance from S to F is 10 and the path is shown on the diagram.
However, there are up to three "shortest" path candidates for any given cuboid and the shortest route doesn't always have integer length.
It can be shown that there are exactly 2060 distinct cuboids, ignoring rotations, with integer dimensions, up to a maximum size of M by M by M, for which the shortest route has integer length when M = 100. This is the least value of M for which the number of solutions first exceeds two thousand; the number of solutions when M = 99 is 1975.
Find the least value of M such that the number of solutions first exceeds one million.
一只蜘蛛 S 坐在一個 6×5×3 的立方體屋子的一個角落里，一個蒼蠅 F 坐在與之相對的角落里。如果只允許在屋子的表面行走的話，從 S 到 F 的最短“直線”距離是 10，路線在圖中標(biāo)出。
但是，每個立方體都有三條可能的最短路徑，而且最終的最短路徑并不一定是整數(shù)。
考慮所有整數(shù)邊長的立方體屋子，最大不超過 M×M×M，當(dāng) M=100 時一共有 2060 個立方體的最短路徑是整數(shù)，而且這也是解超過 2000 的最小的 M；M=99 時又 1975 個立方體的最短路徑是整數(shù)。
找出最短路徑整數(shù)解個數(shù)超過一百萬的最小的 M。
......BF選手已就位；
對每個a×b×c的長方體先找到3個路徑中最短的那條，檢驗是否為整數(shù)解..
3個路徑的平方：
a * a + (b + c) * (b + c);
b * b + (a + c) * (a + c);
c * c + (a + b) * (a + b);
為了不重復(fù)找b>=a,c>=b
實際上這題應(yīng)該用勾股數(shù)生成公式先跑出所有的整數(shù)解再計數(shù)的...
但最原始的暴搜也不慢
結(jié)果為M=1818時有1000457個整數(shù)解
ans：1818
Prime power triples
Problem 87
The smallest number expressible as the sum of a prime Square, prime cube, and prime fourth power is 28. In fact, there are exactly four numbers below fifty that can be expressed in such a way:
28 = 2^2?+ 2^3?+ 2^4
33 = 3^2?+ 2^3?+ 2^4
49 = 5^2?+ 2^3?+ 2^4
47 = 2^2?+ 3^3?+ 2^4
How many numbers below fifty million can be expressed as the sum of a prime Square, prime cube, and prime fourth power?
最小的能寫成質(zhì)數(shù)的 2，3，4 次方之和的數(shù)是 28。50 以下一共有 4 個數(shù)可以寫成這種形式
5000 萬以下的數(shù)中有多少個能寫成一個質(zhì)數(shù)的 2 次方，一個質(zhì)數(shù)的 3 次方和一個質(zhì)數(shù)的 4 次方之和？
簡單的暴搜. 50000000把以內(nèi)的質(zhì)數(shù)的2，3，4次方都找出來，記錄并計數(shù)所有可能的和即可
因為根號50000000為7071+，所以質(zhì)數(shù)表只需要跑到7071即可
ans：1097343
嗯.偏水的一期（35% 15% 35% 20%）（明明不算低但連BF都能輕易過...）
隨緣更新后續(xù).
