Just algorithm!
Crop Triangles



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

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

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

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

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



สูตรการหาจุดศูนย์กลางคือ (x1 + x2 + x3) / 3, (y1 + y2 + y3) /3



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

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

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



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

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



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


หมายความว่า x1 + x2 + x3 หาร 3 ลงตัว

ซึ่งก็หมายความว่า x1 mod 3 + x2 mod 3 + x3 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*+ B) % M
               let yN = (C*+ 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

จบ






Create Date : 15 พฤศจิกายน 2557
Last Update : 15 พฤศจิกายน 2557 23:10:03 น. 0 comments
Counter : 95 Pageviews.

ชื่อ : * blog นี้ comment ได้เฉพาะสมาชิก
Comment :
  *ส่วน comment ไม่สามารถใช้ javascript และ style sheet
 

chaowman
Location :
กรุงเทพฯ Thailand

[Profile ทั้งหมด]

ให้ทิปเจ้าของ Blog [?]
ฝากข้อความหลังไมค์
Rss Feed
Smember
ผู้ติดตามบล็อก : 8 คน [?]









New Comments
Group Blog
 
All Blogs
 
Friends' blogs
[Add chaowman's blog to your web]
Links
 

 Pantip.com | PantipMarket.com | Pantown.com | © 2004 BlogGang.com allrights reserved.