|
|
|||||||
| สมัครสมาชิก | คู่มือการใช้ | รายชื่อสมาชิก | ปฏิทิน | ข้อความวันนี้ | ค้นหา |
  |
|
|
เครื่องมือของหัวข้อ | ค้นหาในหัวข้อนี้ |
|
#1
21 พฤษภาคม 2004, 14:16
|
|||
|
|||
ขอคำแนะนำหน่อยครับ
ข้อ 1
ถ้ามีก้อนหินอยู่ n ก้อน แล้วเรารู้น้ำหนักทุกก้อน แล้วเราจะจัดก้อนหินออกเป็น 2 กลุ่ม โดยให้น้ำหนักทั้ง 2 กลุ่มต่างกันน้อยที่สุด ถามว่าจะจัดอย่างไร  ข้อ 2 เป็นเกมเกมหนึ่งนะครับ สมมุติว่าเรามีกระดานกว้างมากๆ เป็นอนันต์คูณอนันต์ช่องเลยแล้วกัน แล้วเรามีหมากวางเป็น m แถว แถวละ n ตัวอยู่ ให้หาจำนวนหมากที่น้อยที่สุดที่เป็นไปได้ว่าจะเหลืออยู่บนกระดานหลังจากให้หมากกินกัน (หมายความว่าให้กินกันมากที่สุด) การกินให้เป็นลักษณะการข้ามตัวที่ถูกข้ามจะหายไป การข้ามมีเฉพาะแนวตั้งและแนวนอนที่มีช่องติดกันเท่านั้น 
|
|
#2
22 พฤษภาคม 2004, 06:29
|
|||
|
|||
|
ตอบข้อแรกก่อนละกัน (ข้อสองนี่ดูแล้วคุ้นๆ เหมือนข้อสอบ IMO)
ไม่ว่าเราจะจัดแบ่งก้อนหินออกเป็น 2 กลุ่มด้วยวิธีใด ผลรวมน้ำหนักของก้อนหินทุกก้อนมีค่าคงที่เสมอ สมมติว่าเป็น x ดังนั้นผลต่างของน้ำหนัก ที่น้อยสุดที่เป็นไปได้คือศูนย์(เมื่อน้ำหนักรวมของแต่ละกลุ่มคือ x/2)  แต่หากเราไม่สามารถทำให้ น้ำหนักรวมของแต่ละกลุ่มเป็น x/2 ได้ ก็ต้องทำให้น้ำหนักของกลุ่มใดกลุ่มหนึ่ง ใกล้เคียงกับ x/2 มากที่สุด วิธีจัดแบ่งก้อนหินของกลุ่มหนึ่งให้ใกล้เคียงกับ x/2 มากที่สุด ใช้หลักการเดียวกับเลขฐาน คือให้เลือกหยิบก้อนหินทีละก้อน จากก้อนที่มีน้ำหนักมากที่สุดไปหาน้อยที่สุด มาวางรวมกันให้น้ำหนักไม่เกิน x/2 หากก้อนใดถ้าวางลงไปแล้วน้ำหนักเกิน ให้ข้ามก้อนนั้นไป
|
|
#3
23 พฤษภาคม 2004, 12:34
|
||||
|
||||
ลองดูว่าคิดผิดตรงไหนหรือเปล่า ส่วนเรื่องเขียนให้เข้าใจคิดว่าลำบากครับ. แนะนำว่าน้องพิชญ์ควรนั่งเล่นดูก่อนนะ หาเหรียญบาทมาสัก 9 เหรียญ นั่งเล่นดู แล้วลองจดบันทึกดูว่าถ้า m = 1, n = 1 ได้อะไร ทำงี้ไปเรื่อย ๆสัก m = 3, n = 3 ก็น่าจะพอ ไม่งั้นงงแน่นอน พี่ก็ลองนั่งเล่นดูแล้วครับ.
ให้ S(m, n) แทนจำนวนหมากที่น้อยที่สุด ซึ่งเหลืออยู่บนกระดาน จากการวางหมาก m แถว และ n หลัก จากการทดลองเราจะพบว่า S(1, 1) = 1, S(1, 2) = 1, S(1, 3) = 2, S(1, 4) = 2, S(1, 5) = 3, ... ซึ่งจะได้ว่า S(1, n) = ้n/2๙ เมื่อให้ ้x๙ แทน Ceiling function แทน จำนวนเต็มที่น้อยที่สุดที่มากกว่าเท่ากับ x เช่น ้p๙=4 ในทำนองเดียวกันจะได้ว่า S(m, 1) = ้m/2๙ จากการทดลองเดินดูจะพบว่า จะต้องเริ่มกินหมากจากตัวหมากที่อยู่ในแถวที่ 2(หรือหลักที่ 2) ไปยังตัวหมากในแถวที่ 1(หรือ หลักที่ 1) [ หรือ จะเริ่มกินจากแถวที่ m - 1 ไปยังแถวที่ m (หรือหลักที่ n - 1 ไปยังหลักที่ n ก็ได้) ] ทีนี้เพื่อให้ตัวหมากเหลือบนกระดานน้อยที่สุด จากการลองเดินดูจะพบว่า เวลากิน จะต้องทีละทั้งหมดในแถวนั้น ๆ เช่น S(2, 2) ถ้ากินถูกวิธีจะเหลือ 1 ตัว แต่ถ้ากินผิดจะเหลือ 2 ตัว เป็นต้น. ในการกินจะกินตามแถวไปแถว หรือ หลักไปหลักก่อน ถ้ากินถูกวิธีจะพบว่าได้คำตอบเท่ากัน งานมี 2 ขั้นตอน ขั้นที่ 1 . กินตามหลักก่อน สมมติว่าจะเริ่มกินตามหลักก่อน กล่าวคือ เริ่มกินจากหลักที่ 2 ไปหลักที่ 1 จากนั้นกินจากหลัก 4 กินไปหลัก 3 ทำเช่นนี้เรื่อย ๆ ไป จะพบว่าสุดท้าย จะเหลือหลักอยู่จำนวน ้n/2๙ หลัก (หมายเหตุ จะเริ่มจาก หลักที่ 2 ไปหลักที่ 1 พร้อม ๆ กับ กินจากหลักที่ n - 1 ไปหลักที่ n ก็ได้ เป็นต้น.) ขั้นที่ 2. กินในแต่ละหลัก ในแต่ะหลักที่เหลืออยู่ จะมีตัวหมากอยู่ m ตัว ซึ่งเมื่อกินในหลักนั้น ๆ ก็จะเหลือตัวหมากเท่ากับ S(m, 1) = ้m/2๙ เช่นนี้ทุกหลัก ดังนั้น จะมีตัวหมากเหลืออยู่น้อยสุด ้n/2๙ ด ้m/2๙ ตัว บนกระดาน เช่น ถ้ามี 15 แถว 8 หลัก ก็จะเหลือหมากอยู่ ้15/2๙ ้8/2๙ = 8*4 = 32 ตัว
__________________
The Lost Emic <<-- หนังสือเฉลยข้อสอบระดับประถมนานาชาติ EMIC ครั้งที่ 1 - ครั้งที่ 8 ชุดสุดท้าย หลงมา 
23 พฤษภาคม 2004 15:29 : ข้อความนี้ถูกแก้ไขแล้ว 3 ครั้ง, ครั้งล่าสุดโดยคุณ gon
|
|
#4
23 พฤษภาคม 2004, 14:38
|
|||
|
|||
|
หากกำหนดให้ o แทนตัวหมาก และ x แทนช่องว่าง
จะสังเกตได้ว่า เราสามารถลดตัวหมากจาก 3m แถว n หลัก ให้เหลือเพียง 3m แถว 1 หลัก ได้เสมอ ดังนี้ Code:
s(m,n) = s(n,m) s(1,n) = ceil(n/2) s(2,n) = ceil(n/2) s(3,n) = 2 s(3m,3n) = s(1,3m) เมื่อ m <= n s(3m+1,3n) = s(1,3m+1) + s(1,3n-1) เมื่อ m < n; = s(1,3n) เมื่อ m >= n s(3m+2,3n) = s(1,3m+2) + s(1,3n-1) เมื่อ m < n; = s(1,3n) เมื่อ m >= n s(3m+1,3n+1) = s(1,3m+1) + s(1,3n) เมื่อ m <= n s(3m+2,3n+1) = s(1,3m+2) + s(2,3n) เมื่อ m < n; = s(1,3n+1) + s(1,3m+1) เมื่อ m >= n s(3m+2,3n+2) = s(1,3m+2) + s(2,3n+1) เมื่อ m <= n
|
|
#5
24 พฤษภาคม 2004, 05:33
|
|||
|
|||
ข้อ 1. วิธีของคุณ<คิดด้วยคน>เป็นวิธีที่ดีมากอันนึงแต่ไม่สามารถรับประกันได้ว่า
จะได้คำตอบที่ถูกต้องเสมอไป ตัวอย่างเช่น ถ้าเรามีก้อนหิน 8 ก้อนซึ่งมีน้ำหนัก 10, 9, 8, 8, 8, 7, 7, 6 ถ้าแบ่งตามวิธีดังกล่าวจะได้ 10 + 9 + 8 = 27 กับ 8 + 8 + 7 + 7 + 6 = 36 ในขณะที่เราสามารถทำได้ดีกว่านั้นเช่น 9 + 8 + 8 + 6 = 31 กับ 10 + 8 + 7 + 7 = 32 จริงๆแล้ววิธีนี้จะมีปัญหาตั้งแต่ช่วงแรกแล้วเพราะการตรวจสอบว่ามี subset ใดที่มี ผลรวมเท่ากับ x/2 เป็นเรื่องยากมาก แต่เราก็แก้ปัญหานี้ได้ง่ายๆโดยใช้ algorithm ของช่วงสองตั้งแต่เริ่มเลย โดยไม่สนใจว่าจะมี subset ใดที่มีผลรวมเท่ากับ x/2 หรือไม่ ผมเดาเอาว่าปัญหาข้อนี้น่าจะเป็น NP-hard problem นะครับ ข้อ 2. ผมไม่แน่ใจว่าผมเข้าใจวิธี "กิน" ถูกต้องรึเปล่า แต่ถ้า "กิน" แบบที่ผมเข้าใจ จะได้คำตอบเท่ากับของคุณ gon คือ ้m๙ x ้n๙ ครับผม 24 พฤษภาคม 2004 06:04 : ข้อความนี้ถูกแก้ไขแล้ว 1 ครั้ง, ครั้งล่าสุดโดยคุณ warut
|
|
#6
24 พฤษภาคม 2004, 10:43
|
||||
|
||||
|
ผมกินไม่น้อยสุดจริง ๆ ด้วย กินไขว้ไปมาได้น้อยกว่า ลองแล้วได้ S(3, 4) = 2 จริง น่าจะจริงที่ S(3, n) = 2 ปัญหาข้อนี้ใกล้เคียงกับ IMO 1993/3 มาก http://www.mathcenter.net/imo/1993/imo1993.shtml ยากกว่าด้วยซ้ำมั้ง เพราะถามทั่วไปกว่า ถ้าทำจริง ๆ คงต้องพิสูจน์เพียบหมดกระดานตรึมแน่ ๆ เลย. ข้อแรกโดยสามัญสำนึก ทีแรกผมก็คิดแบบนั้นเหมือนกัน นึกว่าไม่มีปัญหาเสียอีก เดี๋ยวว่าง ๆ จะลองคิดอีกที
__________________
The Lost Emic <<-- หนังสือเฉลยข้อสอบระดับประถมนานาชาติ EMIC ครั้งที่ 1 - ครั้งที่ 8 ชุดสุดท้าย หลงมา
|
|
#8
27 พฤษภาคม 2004, 08:23
|
|||
|
|||
|
ขอบคุณมากครับ ได้แนวคิดขึ้นมากเลย
ลองเล่นดู พอจะสรุปได้ว่า 1. ถ้า เป็นแถวเดี่ยวจะได้ว่า จำนวนหมากที่เหลือ = (จำนวนตัว+1)/2 (ตัดเศษทิ้งนะครับ) 2. ถ้า m หรือ n หาร 3 ลงตัวจะได้จำนวนหมากที่เหลือ = 2 3. ถ้าไม่เข้าเงื่อนไขไหนเลย จำนวนหมากที่เหลือ = 1 คิดว่าน่าจะถูกแล้วนะครับ ถ้าไงช่วยตรวจสอบให้หน่อยนะครับ
|
|
#10
09 กรกฎาคม 2004, 17:15
|
||||
|
||||
น้อง ToT นั่นเอง. หายหน้าไปนานเลย ทีมุสมันคืออะไรหรือครับ. การสอบแข่งขันหรือ ?
__________________
The Lost Emic <<-- หนังสือเฉลยข้อสอบระดับประถมนานาชาติ EMIC ครั้งที่ 1 - ครั้งที่ 8 ชุดสุดท้าย หลงมา
|
|
#11
09 กรกฎาคม 2004, 19:41
|
||||
|
||||
|
http://acm.timus.ru
เป็นเว็บที่มีโจทย์เขียนโปรแกรม ที่สามารถส่งเ้ข้าไปตรวจแล้วจัด rank ให้ครับ ปล. ช่วงนี้ตกต่ำอย่างหนัก เข้ามาอ่านเรื่อยๆครับ 555+ 
__________________
Mmmm ....
|
| |
|
|
( stone pile )