หลังจากคุณดู Discovery คุณก็อยากจะสร้าง Crop Circles บ้าง
แต่ระดับคุณ คุณจะสร้าง Crop Triangles แทน
และ Triangle ของคุณต้องไม่ธรรมดา
มุมต่างๆ ของสามเหลี่ยม ต้องอยู่บนจุดตัดบน Grid
ไม่พอ จุดศูนย์กลางของสามเหลี่ยมจะต้องอยู่บนจุดตัดบน Grid ด้วย
สูตรการหาจุดศูนย์กลางคือ (x
1 + x
2 + x
3) / 3, (y
1 + y
2 + y
3) /3
โจทย์จะมีสูตรให้สร้างจุดต่างๆ บน Grid
แล้วให้หาว่าเราสามารถสร้าง Crop Triangles ได้กี่แบบ
อ่านต่อ
ที่นี่ เนื่องจาก large dataset สามารถสร้างจุดได้ถึง 100,000 จุด
เราจึงไม่สามารถใช้วิธี brute force ได้ ซึ่งจะต้องหาทั้งหมด 100,000! วิธี
แต่จริงๆ พอจะมีทางลัด ถ้า (x
1 + x
2 + x
3) / 3 เป็นจุดตัดบน grid
หมายความว่า x
1 + x
2 + x
3 หาร 3 ลงตัว
ซึ่งก็หมายความว่า x
1 mod 3 + x
2 mod 3 + x
3 mod 3 หาร 3 ลงตัว
เริ่มเลย
let solve n A B C D x0 y0 M =
let unfoldFn (n, (x, y)) =
match n with
| 0 -> None
| n -> let xN = (A*x + B) % M
let yN = (C*y + D) % M
Some((x, y), (n-1, (xN, yN)))
let trees = Seq.unfold unfoldFn (n, (x0, y0))
n A B C D x0 y0 M เป็น input ที่โจทย์กำหนด
unfoldFn ก็เป็น function ที่โจทย์กำหนด เพื่อสร้างจุดต่างๆ
ส่วน trees คือจุดต่างๆ
let buckets = trees |> Seq.groupBy (fun (x, y) -> (int x % 3)*3 + (int y % 3))
|> Seq.map (fun (key, g) -> key, g.LongCount())
|> Seq.sortBy fst
|> Seq.cache
ทีนี้ก็จัดกลุ่มเป็น 9 กลุ่ม (x mod 3) ตัดกับ (y mod 3)
แล้วก็นับจำนวนในกลุ่ม
let sameBucketCount = buckets |> Seq.map (fun (key, cnt) -> cnt * (cnt-1L) * (cnt-2L) / 6L)
|> Seq.sum
ถ้าเป็นกลุ่มเดียวกัน ก็แปลว่าหารลงตัวแน่นอน
เรื่องการหาจำนวนในกลุ่ม ใช้สูตร
combinatorics หยิบ 3 จาก cnt ตัว
อีกแบบคือ คนละกลุ่มหมด แต่หาร 3 ลงตัว
let diffBucketCount = seq {
for key1,cnt1 in buckets do
for key2,cnt2 in buckets do
if key1 < key2 then
for key3,cnt3 in buckets do
if key2 < key3 then
if (key1+key2+key3) % 3 = 0 then
if (key1/3 + key2/3 + key3/3) % 3 = 0 then
yield cnt1 * cnt2 * cnt3
} |> Seq.sum
คือ ถ้ามาจากคนละกลุ่มหมดเลย
และทั้งแกน x และ y หาร 3 ลงตัว
ก็เอาจำนวนมาคูณกันได้เลย
จบแล้วครับ ได้คำตอบ
sameBucketCount + diffBucketCount |> string
จบ