หลังจากคุณดู Discovery คุณก็อยากจะสร้าง Crop Circles บ้าง

แต่ระดับคุณ คุณจะสร้าง Crop Triangles แทน

และ Triangle ของคุณต้องไม่ธรรมดา

มุมต่างๆ ของสามเหลี่ยม ต้องอยู่บนจุดตัดบน Grid

ไม่พอ จุดศูนย์กลางของสามเหลี่ยมจะต้องอยู่บนจุดตัดบน Grid ด้วย



สูตรการหาจุดศูนย์กลางคือ (x₁ + x₂ + x₃) / 3, (y₁ + y₂ + y₃) /3



โจทย์จะมีสูตรให้สร้างจุดต่างๆ บน Grid

แล้วให้หาว่าเราสามารถสร้าง Crop Triangles ได้กี่แบบ

อ่านต่อ ที่นี่



เนื่องจาก large dataset สามารถสร้างจุดได้ถึง 100,000 จุด

เราจึงไม่สามารถใช้วิธี brute force ได้ ซึ่งจะต้องหาทั้งหมด 100,000! วิธี



แต่จริงๆ พอจะมีทางลัด ถ้า (x₁ + x₂ + x₃) / 3 เป็นจุดตัดบน grid


หมายความว่า x₁ + x₂ + x₃ หาร 3 ลงตัว

ซึ่งก็หมายความว่า x₁ mod 3 + x₂ mod 3 + x₃ 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

จบ