|
Google Code Jam 2008 รอบคัดเลือกผ่านไปแล้ว
Google Code Jam 2008 รอบคัดเลือกผ่านไปแล้ว..
ตามที่ google ได้จัดให้มีการแข่งขัน พัฒนาโปรแกรมคอมพิวเตอร์ เพื่อแก้ปัญหา ที่มี ชื่อว่า Google Code Jam 2008 ได้ ผ่านรอบคัดเลือกไปแล้วเมื่อเช้านี้ (18/07/51 06:00) ซึ่งรอบนี้ ทางผู้จัด ให้เวลา 24 ชั่วโมงในการพัมนาโปรแกรม และส่งคำตอบ แต่ทั้งนี้ทั้งนั้น ผู้ส่วนใจก็ยังสามารถทดสอบตัวเองได้ ด้วยการส่งคำตอบไปว่าถูกต้องหรือไม่ได้อยู่
ซึ่งโจทย์มี อยู่ 3 ข้อ คือ
ข้อ A เป็นการหาจำนวนครั้งน้อยที่สุดในการเปลี่ยนเส้นทางการส่งของเครื่องค้นหา โดยโจทย์กำหนดจำนวนเครื่อง ทั้งหมด พร้อมชื่อ ที่ไม่ซ้ำกันมาให้ และ จำนวนคิวที่จะส่ง พร้อมชื่อ โดยที่การส่งจะส่งเรียงตามลำดับ ของ คิว และ เครื่องชื่อเดียวกันจะไม่สามารถส่งกันได้ ก็ให้เปลี่ยนเครื่องส่ง เช่น
มีเครื่องอยู่ 3 เครื่อง คือ เครื่อง A , B และ C
และมีคิวอยู่ 10 คิว คือ A, B, B, C, A, A, B, A, C, A
คำตอบคือ 3
เพราะ
A, B, B ส่งด้วยเครื่องส่ง C
C, A, A ส่งด้วยเครื่องส่ง B
B, A ส่งด้วยเครื่อง C
C, A ส่งด้วยเครื่อง B
ซึ่งก็คือเปลี่ยนเครื่องส่ง 3 ครั้ง (ครั้งแรกไม่นับ)
(*ข้อนี้ถือว่าง่ายที่สุด แต่ตอนแรกผู้เขียนแปลโจทย์ผิดพลาดไปเลยทำไม่ทัน แต่มาลองหลังหมดเวลาถูกต้อง ตามนี้ครับ)
ข้อ B ให้เราเป็นการรถไฟ โดยมีสถานีรถไฟ อยู่ 2 สถานี คือ สถานี A และ B โจทย์กำหนด เวลาการเดินรถไฟมาให้ ว่า รถออกจากสถานี A ไป B มีกี่ขบวน ออกเวลาเท่าไร ถึงเวลาเท่าไร และ รถออกจากสถานี B ไป A มีกี่ขบวน ออกเวลาเท่าไร ถึงเวลาเท่าไร โดยที่เวลาออกและเวลาถึง แน่นอนตามนั้น และโจทย์กำหนดด้วยว่ารถไฟ ต้องจอดที่สถานีเป็นเวลากี่นาทีถึงจะวิ่งต่อไปได้
โจทย์ให้หาจำนวนรถไฟที่เริ่มวิ่งจากสถานี A และ จำนวนรถไฟที่เริ่มวิ่งจากสถานี B
เช่น
เวลาจอด 5 นาที
เที่ยววิ่งที่ออกจากสถานี A
09:00 12:00
10:00 13:00
11:00 12:30
เที่ยววิ่งที่ออกจากสถานี B
12:02 15:00
09:00 10:30
คำตอบคือ 2 กับ 2
เพราะ
ขบวนที่1 เริ่มจาก A : (A)09:00-12:00+5
ขบวนที่1 เริ่มจาก A : (A)10:00-13:00+5
ขบวนที่1 เริ่มจาก B : (B)09:00-10:30+5 (A)11:00-12:30
ขบวนที่2 เริ่มจาก B : (B)12:02-15:00
ข้อนี้ตอนแรกก็ดูเหมือนจะยาก ใช้เวลาทำไปนานพอสมควร แล้วก็มานึกดูๆคิดมาไปนี่เอง เลยทำใหม่ใช้เวลาไปไม่มาก ข้อนี้เป็นคนที่ทำได้
ข้อ C โจทย์ มีอยู่ว่า เรามีไม้เทนนิสกลมสมบูรณ์ อยู่อันหนึ่ง ไม่สนใจด้าน และขึงด้วยลวดเป็นตาข่าย โจทย์ให้หาความน่าจะเป็นที่จะโดนลูก บางท่านอาจจะงง หายังไงหว่า
ไม่ต้องงครับ เพราะ บางกรณี โจทย์กำหนดให้ การขึงลวด ตามันใหญ่แต่ลูกมันเล็ก มันก็เลย จะลอดรูไปนั้นเอง
ข้อนี้ยังทำไม่ได้ยกตัวอย่างไปก็ไม่เข้าใจครับ แต่วิธีคำนวนก็คือ
(พื้นที่ทั้งหมด - พื้นที่ที่ลูกจะลอดรู)/พื้นที่ทั้งหมด
โดยโจทย์กำหนด ความกว้างของช่องตาข่าย , รัศมีของลวด , ความกว้างของขอบ, รัศมีวงนอกของไม้ , รัศมีของลูก (ดูรูปในเวปของ codejam เพื่อความเข้าใจมากขึ้นนะครับ)
เป็นยังไงบ้างครับ เข้าใจมากน้อยเพียงใด
หวังว่าหลายๆท่านจะสนใจ ถ้ามีใครสนใจเฉลยวิธี ข้อ A และ ข้อ B ก็แจ้งมาได้เลยครับ (เฉลยตามวิธีการที่ผมทำส่ง)
ลองทดลองดูได้ที่ Qualification Round ที่ http://code.google.com/codejam/contest/
สำหรับรอบแรก
ข้อ A มีผู้ส่งคำตอบไปทั้งสิ้น 10,473 User ถูกต้อง 6,760 User
ข้อ B มีผู้ส่งคำตอบไปทั้งสิ้น 6,516 User ถูกต้อง 5,076 User
ข้อ C มีผู้ส่งคำตอบไปทั้งสิ้น 1,536 User ถูกต้อง 1,007 User
สำหรับข้อมูลขนาดเล็กนะครับ
แต่ละข้อมี 5 คะแนนสำหรับข้อมูลขนาดเล็ก และ 20 คะแนนสำหรับข้อมูลขนาดใหญ่
ในรอบคัดเลือกนี้ ทำถูกเพียงข้อเดียว สำหรับข้อมูลขนาดเล็ก และ ขนาดใหญ่ ก็ผ่านแล้วครับ (ผ่านที่ 25 คะแนน)
คนที่มี 5 คะแนนขึ้นไป ทั้งสิ้น 7,154 User
คนที่มี 25 คะแนนขึ้นไป ทั้งสิ้น 6,773 User (เข้ารอบ)
คนที่มี 75 คะแนน ทั้งสิ้น 576 User (คะแนนเต็ม)
รอบที่ 1 จะจัดวันที่ 25-31 ก.ค. คัดเหลือ 2,520 user
รอบที่ 2 จะจัดวันที่ 2 ส.ค. คัดเหลือ 1,000 user
รอบที่ 3 จะจัดวันที่ 9 ส.ค. คัดเหลือ 500 user
รอบที่ 4 จะจัดวันที่ 22 ก.ย. คัด 20% โซน Asia
รอบที่ 5 จะจัดวันที่ 29 ก.ย. คัด 20% โซน อเมริกา
รอบที่ 6 จะจัดวันที่ 6 ต.ค. คัด 20% โซนยุโรป และ แอฟริกา
รอบชิง จะจัดวันที่ 14 พ.ย. พึ่งหา 100 คนสุดท้าย ที่สหรัฐอเมริกา
ชิงรางวัล
1st Place $10,000
2nd Place $5000
3rd Place $2500
4th 10th Place $1500
11th 30th Place $1000
31st 50th Place $750
51st 75th Place $500
76th 100th Place $250
มาดูกันว่าผมจะไปได้สักกี่น้ำ
** add id ผมได้นะครับ ชื่อ thai.micro ไม่ค่อยเก่งนะครับอันดับท้าย (แปลโจทย์ไม่ค่อยจะได้)
ข้อ C ใครมายืนยันทีว่าผมเข้าใจไม่ผิด
| Create Date : 18 กรกฎาคม 2551 |
| Last Update : 18 กรกฎาคม 2551 16:43:46 น. |
| |
|
|
My FriendFlock
ฝากข้อความหลังไมค์
Rss Feed