PAtS.Computainment

สวัสดีครับ

ยังคงรู้สึกนอนไม่ค่อยหลับ..
เลยตื่นขึ้นมาเช็คสิ่งที่รบกวนใจอยู่

มันคือโจทย์ GCJ ข้อนึง ที่ผมทำผิดด้วยความสะเพร่า
ตอนนี้ก็เคลียร์แล้ว ว่าทำไมถึงผิด
ไหนๆ ก็ไหนๆ แล้ว เลยจะมาเล่าถึงโจทย์ข้อนี้ให้ฟังด้วยเลย

จริงๆ แล้ว รอบนี้ทั้งหมด มี 3 ข้อครับ ผมทำไปได้สอง
อีกข้อ... เฮ้อ.. ไว้จะเล่าให้ฟังตอนท้าย

และที่ทำได้สองเนี่ย ข้อนึงถูกแบบเต็ม อีกข้อ ถูกครึ่งเดียว
(คือมันจะมี input มาให้สองชุด ใหญ่กับเล็ก.. ซึ่งผมทำชุดใหญ่ผิด)

ก่อนจะว่าต่อ เรามาดูโจทย์กันก่อนดีกว่า ว่าเค้าให้ทำอะไร

..........
เรื่องมีอยู่ว่า ณ จักรวาลอันไกลโพ้น ได้มีปัญหาโลกแตกข้อนึง
ซึ่งจริงๆ แล้ว มันคือปัญหาจักรวาลแตก!!

เพราะว่า search engine ที่นั่น เค้ามีคุณสมบัติแปลกๆ
คือ ถ้าเราไปค้นหาข้อความที่มีชื่อเดียวกับ search engine นั่น
เช่น หาคำว่า Google ใน Google จะทำให้จักรวาลระเบิด!!!
(ใครรู้สึกว่าติงต๊อง ก็ไม่แปลก โจทย์พวกนี้มันจะเพี้ยนๆ แบบนี้แหละ)

ทีนี้ คนในจักรวาลนั้นก็เลยหาวิธี โดยการส่งคำค้นหาไปที่ระบบกลาง
เพื่อตรวจสอบว่าคำค้นไหนจะส่งไปให้ SE ตัวไหน แล้วจะไม่ระเบิด
ทีนี้ปัญหาก็คือ คำค้นมันจะมาเป็นชุดเยอะๆ ให้ระบบกลางส่งต่อไป SE ต่างๆ
ซึ่ง เมื่อมีการเปลี่ยน SE ที่จะส่งคำค้นไปหาครั้งนึง ก็มีค่าใช้จ่ายเกิดขึ้น
เลยทำให้ระบบจะพยายามส่งคำค้นไปให้ SE เดิมมากที่สุดเท่าที่จะทำได้

คำถามก็คือ.. ระบบกลาง จะต้องเปลี่ยน SE น้อยที่สุดกี่ครั้ง
เมื่อให้รายชื่อ SE และคำค้นมาให้ (งงๆ มั๊ย พยายามแปลให้เข้าใจง่ายแล้วนา อิอิ)
....................

ลองดูตัวอย่างก่อน เช่น ถ้ามี SE 3 ตัว ชื่อ A, B, C
คำค้นเป็น A, B, C, A, A, C, B, A (ต้องค้นตามลำดับนะครับ ห้ามสลับที่)
วิธีที่ดีที่สุดคือ ส่งให้ C ค้นก่อนสองอันแรก แล้วก็ส่งให้ A ค้นต่อ 5 คำ
สุดท้าย ก็ให้ B หรือ C ค้นคำสุดท้าย ก็จะได้ว่า ต้องเปลี่ยนทั้งหมด 2 ครั้ง

ปัญหาดูง่ายๆ ครับ แต่จะเขียนโปรแกรมแก้ยังไงดี - -a
วิธีนึงที่ดูตรงไปตรงมาคือ ไล่ลองใช้ SE ทีละตัว หาว่าตัวไหน ค้นคำติดกันได้มากที่สุด
แล้วก็หักที่ค้นไปแล้วออก แล้วก็เอาคำที่เหลือมาทำแบบเดิมต่อไปเรื่อยๆ จนคำหมด

แต่ มันมีอีกวิธีนึงง่ายกว่านี้ (ง่ายสำหรับผมอ่ะนะ เหอๆ)
คือมอง SE เป็นถังๆ ไว้ใส่ของหลายๆ ใบ ซึ่งมีกฏว่า ห้ามถังทุกใบมีของพร้อมกัน
หากมีของที่จะใส่ แล้วทำให้ถังทุกใบมีของ ให้เอาของในถังอื่นๆ ออกให้หมดก่อน
แล้วก็นับว่า ต้องเอาของออกกี่รอบ ก็เป็นจำนวนที่ต้องเปลี่ยน SE ที่น้อยที่สุด
มาดูรูปกันดีกว่า (ของที่ใส่คือ A, B, B, C)



หลังจากคิดได้ว่า วิธีนี้ น่าจะเขียนโปรแกรมง่าย + ไม่น่าจะผิด ก็เขียนดู
ลองกับชุดอินพุตอันเล็ก ก็คำตอบถูก ไม่มีปัญหา เลยทำชุดใหญ่ ส่งไป
(กฏของการแข่งคือ ชุดเล็กจะบอกเลยว่าถูกหรือผิด ชุดใหญ่ ต้องรอให้หมดเวลาแข่งก่อน)

เช้าวันรุ่งขึ้น ปรากฏว่ามัน... ผิด!!!

เกิดอาการเซ็งครับ... เซ็งจิต จิตตก...
มานั่งไล่วิธีคิดดู ก็ไม่น่าจะผิดอะไร คิดตั้งนาน คิดไม่ออก เลยเลิกสนใจ

เมื่อกี้กำลังจะนอน เลยมาลองเขียนใหม่ ด้วยแนวคิดเดิมนี่แหละ
ตอนแรกเขียน C เปลี่ยนมาเขียน PHP ของที่ถนัดกว่า (เนื่องจากไม่ได้เขียน C มาเป็นปี)

ปรากฏว่า ผลลัพท์ถูกต้อง... เชี่ย เอาแล้วไง บั๊กที่โปรแกรมชัวร์
ไล่ไปไล่มา ลองสลับเคสต่างๆ ดูว่าเป็นบั๊กอะไร แล้วก็ไปเจอเข้า...

มันคือบั๊ก malloc .... แบบว่า ใส่ตัวแปรที่บอกขนาดหน่วยความจำที่จะจองผิดตัว!!!!

อีบ้าาาาา

คือแบบ ผมจะจองเอาไว้เก็บลิสต์ของรายชื่อ SE ซึ่งก็ต้องใช้จำนวน SE ไปจองใช่ม่ะ
แต่ปรากฏว่า ผมดันไปใส่ตัวแปรบ้าไรไม่รู้ แถมเป็นตัวที่ uninitialized ด้วย
ไม่บั๊กให้มันรู้ไป ง่ะ อีโง่!!

ซวย.. คะแนนหายไปเยอะเลย ไอ้มนุษย์บั๊ก เหอๆ



ส่วนข้อสุดท้าย ที่ว่าจะพูดถึง เป็นเกี่ยวกับไม้ตียุง (จริงๆ คือแรคเก็ตเทนนิสกะแมลง)
คือเค้าให้หาว่า ความน่าจะเป็น ที่จะเอาไอ้ไม้เนี่ยไปตีโดนยุงเป็นเท่าไหร่!

หมูครับ คอนเซปไม่มีอะไรเลย
แค่เอาพื้นที่ที่ยุงลอดผ่านไปได้หารพื้นที่ทั้งหมด แล้วเอาไปลบออกจาก 1

แต่... จริงๆ มันยากสาดดดดดดดดด
เพราะพื้นที่มันเป็นเส้นโค้งวงกลม ดูจากรูปดีกว่า อธิบายยาก



คือต้องหาพื้นที่สีขาวๆ ข้างในอ่ะครับ (จริงๆ ต้องหักขนาดยุงไปด้วย ไอ้ตัวเหลืองๆ อ่ะ)
เห็นวงกลมแบบนี้ ผมก็เอาเลย แยกส่วนต่างๆ ใช้ตรีโกณฯ ช่วย
หาพ.ท. เซ็กเตอร์ สี่เหลี่ยมคางหมู สามเหลี่ยม ฯลฯ
สุดท้าย ก็ไม่รอด ไม่ตรงเฉลยเลย  ทำไปเป็นชม. ก็เลิก Y-Y
(แต่ทฤษฎีมันก็น่าจะถูกนา.. คงโปรแกรมมั่วแน่ๆ หน้าตาอย่างกะข้อสอบเอ็นท์เลยข้อนี้ หึหึ)

มีคนบอกว่า.. หาพื้นที่แบบนี้ วงกลมแบบนี้.. แคลคูลัสโลด อ่ะจ๊ากกกกกก
ลองๆ ดูโค้ดเค้า ก็อ่านไม่ค่อยรู้เรื่อง แต่คาดว่าเค้าคงอินทิเกรทกันสนุกสนาน
(แต่คนที่ใช้สามเหลี่ยมก็น่าจะเยอะนา อิอิ)

นี่แหละครับ ความเซ็ง ได้ระบายล่ะ จะได้นอนหลับ