三角形が原点を内包する<=>原点からのベクトルの外積 の符号が３つとも同じ
だって言うのを先生と飲んでるときに聞いて初めて知った。
これはシューティングゲームの衝突判定とかに利用されてるらしい。外積すごい。
問題
Three distinct points are plotted at random on a Cartesian plane, for which -1000 x, y 1000, such that a triangle is formed.
Consider the following two triangles:
A(-340,495), B(-153,-910), C(835,-947)
X(-175,41), Y(-421,-714), Z(574,-645)
It can be verified that triangle ABC contains the origin, whereas triangle XYZ does not.
Using triangles.txt (right click and ‘Save Link/Target As…’), a 27K text file containing the co-ordinates of one thousand “random” triangles, find the number of triangles for which the interior contains the origin.
NOTE: The first two examples in the file represent the triangles in the example given above.
コード
(*
入力となる三角形の集合を以下のようなlist listで持っておく。
let tri_list = [[-340;495;-153;-910;835;-947];[-175;41;-421;-714;574;-645];(*・・・略・・・*)]
*)
(*外積を求める*)
let sign_cp
(x1,y1
) (x2,y2
) =
let cp
= x1
*y2
- x2
*y1
in
if cp
>= 0 then 1 else -1
(*外積の符号が全て一致するかどうかを判定*)
let check l
=
match l
with
| [a
;b
;c
;d
;e
;f
] -> if sign_cp
(a,b
) (c,d
) = sign_cp
(c,d
) (e,f
) && sign_cp
(a,b
) (c,d
) = sign_cp
(e,f
) (a,b
) then true else false
| _
-> false
(*原点を含む三角形をカウント*)
let _
=
let rec loop l count
=
match l
with
| [] -> print_int count
| x
::rest
-> if check x
then loop rest
(count
+1) else loop rest count
in loop tri_list
0
実行時間
real 0m0.009s
user 0m0.001s
sys 0m0.004s
１〜１００００００まで全部確認すればOK
問題
The number 145 is well known for the property that the sum of the factorial of its digits is equal to 145:
1! + 4! + 5! = 1 + 24 + 120 = 145
Perhaps less well known is 169, in that it produces the longest chain of numbers that link back to 169;
it turns out that there are only three such loops that exist:
169 -> 363601 -> 1454 -> 169
871 -> 45361 -> 871
872 -> 45362 -> 872
It is not difficult to prove that EVERY starting number will eventually get stuck in a loop. For example,
69 -> 363600 -> 1454 -> 169 -> 363601 (-> 1454)
78 -> 45360 -> 871 -> 45361 (-> 871)
540 -> 145 (-> 145)
Starting with 69 produces a chain of five non-repeating terms, but the longest non-repeating chain with a starting number below one million is sixty terms.
How many chains, with a starting number below one million, contain exactly sixty non-repeating terms?
コード
(*０から９までの階乗を持っておく*)
let fact_table
=
let tab
= [|1;1;0;0;0;0;0;0;0;0|] in
let rec loop n
=
if n
=10 then tab
else (tab
.(n
) <- tab
.(n
-1)*n
; loop
(n
+1)) in
loop
2
(*nの各桁の階乗の和*)
let sum_of_fact n
=
let rec loop n ans
=
if n
< 10 then ans
+fact_table
.(n
)
else loop
(n
/10) (ans
+fact_table
.(n
mod 10))
in loop n
0
(*nのループの長さ*)
let chain n
=
let rec loop n l
=
if List.mem n l
then List.length l
else loop
(sum_of_fact n
) (n
::l
)
in loop n
[]
(*1000000未満でループの長さが60になるnの個数をカウント*)
let _
=
let rec loop n count
=
if n
>= 1000000 then print_int count
else
if chain n
= 60 then loop
(n
+1) (count
+1) else loop
(n
+1) count
in
loop
1 0
実行時間
real 0m23.198s
user 0m22.384s
sys 0m0.049s
1/3と1/2の間にある分数について、１つずつhcf＝１となるかチェックして数えていけばOK.
ちょっと遅い
問題
Consider the fraction, n/d, where n and d are positive integers. If nd and HCF(n,d)=1, it is called a reduced proper fraction.
If we list the set of reduced proper fractions for d 8 in ascending order of size, we get:
1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8
It can be seen that there are 3 fractions between 1/3 and 1/2.
How many fractions lie between 1/3 and 1/2 in the sorted set of reduced proper fractions for d 12,000?
Note: The upper limit has been changed recently.
コード
let rec hcf a b
=
if a
< b
then hcf b a
else
if a
mod b
= 0 then b
else hcf b
(a
mod b
)
let _
=
let rec loop n d count
=
if d
> 12000 then print_int count
else
if (float_of_int n
) /. (float_of_int d
) >= 0.5 then loop
((d
+1)/3) (d
+1) count
else
if ((float_of_int n
) /. (float_of_int d
) > (1. /. 3.)) && (hcf n d
= 1) then loop
(n
+1) d
(count
+1) else loop
(n
+1) d count
in loop
1 1 0
実行時間
real 0m3.357s
user 0m3.266s
sys 0m0.011s
これも何も考えずにやったら時間がすごくかかった。
どうもこの数列はファレイ数列というらしい。
後で調べてもうちょっと工夫してみる。
問題
Consider the fraction, n/d, where n and d are positive integers. If nd and HCF(n,d)=1, it is called a reduced proper fraction.
If we list the set of reduced proper fractions for d 8 in ascending order of size, we get:
1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8
It can be seen that 2/5 is the fraction immediately to the left of 3/7.
By listing the set of reduced proper fractions for d 1,000,000 in ascending order of size, find the numerator of the fraction immediately to the left of 3/7.
コード
let _
=
let upper
= 3. /. 7. in
let rec loop n d
(n
',d
',ans
) =
if d
> 1000000. then Printf.printf
"%f / %f \n" n
' d
' else
if n
/. d
>= upper
then loop
(float_of_int (int_of_float ((d
+. 1.)*. 0.4))) (d
+. 1.) (n
',d
',ans
) else
if n
/. d
> ans
then loop
(n
+. 1.) d
(n,d,
(n
/. d
)) else loop
(n
+. 1.) d
(n
',d
',ans
)
in loop
1. 2. (0.,
0.,
0.)
実行時間
real 10m22.979s
user 9m55.120s
sys 0m1.384s
bruteforceでは時間がかかりすぎた。
と、今ブログに貼りつけながら、桁数が奇数のとき多少工夫できそうな気もしてきた。
もう少し考えてみる。
問題
Some positive integers n have the property that the sum [ n + reverse(n) ] consists entirely of odd (decimal) digits. For instance, 36 + 63 = 99 and 409 + 904 = 1313.
We will call such numbers reversible; so 36, 63, 409, and 904 are reversible.
Leading zeroes are not allowed in either n or reverse(n).
There are 120 reversible numbers below one-thousand.
How many reversible numbers are there below one-billion (10^9)?
コード
(*整数を各桁のリストに*)
let int_to_list x
=
let rec sub_int_to_list x l
=
if x
< 10 then x
:: l
else sub_int_to_list
(x
/10) ((x
mod 10)::l
)
in sub_int_to_list x
[]
(*整数のリストを結合*)
let list_to_int
list =
let rec loop
list ans
=
match list with
| [] -> ans
| x
::rest
-> loop rest
(ans
*10 + x
)
in loop
list 0
(*nがreversibleかどうか判定*)
let is_reversible n
=
if n
mod 10 = 0 then false else
let rec loop l1 l2 carry
=
match (l1,l2
) with
| ([],
[]) -> true
| (x1
::rest1,x2
::rest2
) ->
if (x1
+ x2
+ carry
) mod 2 = 0 then false
else loop rest1 rest2
((x1
+x2
+carry
)/10)
| _
-> false
in loop
(int_to_list n
) (List.rev
(int_to_list n
)) 0;;
let _
=
let rec loop n count
=
if n
= 1000000000 then print_int count
else
if is_reversible n
then loop
(n
+1) (count
+1) else loop
(n
+1) count
in loop
1 0
実行時間
real 8m10.360s
user 8m9.385s
sys 0m0.376s
