ยาต้านโควิด
โจทย์สอบสัมภาษณ์เข้า Saladpuk
Last updated
Was this helpful?
โจทย์สอบสัมภาษณ์เข้า Saladpuk
Last updated
Was this helpful?
ทรัพยากรทั้งโลกสามารถผลิตยาต้านโควิดได้แค่ 1,000 ขวดเท่านั้น แต่ก็ดันมีคนร้ายแอบผสมยาพิษลงไป 1 ขวด ซึ่งยาพิษตัวนี้ตรวจด้วยวิธีการใดๆก็ไม่พบ และคนที่กินก็จะตายในอีก 23 ชั่วโมงหลังจากที่กินเข้าไป ประจวบกับคนสำคัญทั่วโลกต้องได้รับยาตัวนี้ภายใน 24 ชั่วโมงไม่งั้นจะไม่สามารถรักษาชีวิตพวกเขาไว้ได้ ซึ่งทั่วทั้งโลกมีอาสาสมัครเพียงแค่ 10 คนเท่านั้น ที่พร้อมจะกินยาเหล่านั้นแม้รู้ว่าอาจจะตายก็ตาม
ในขวดมียาหลายเม็ด ส่วนคนกินแค่เม็ดเดียวก็พอ
ทุกเม็ดในขวดยาพิษกินแล้วตายใน 23 ชม เหมือนกัน
จะให้คนกินกี่เม็ดก็ได้ กี่ขวดก็ได้ กินขวดซ้ำกันก็ได้
จะใช้อาสาสมัครทุกคน หรือ แค่บางคนก็ได้ แต่ต้องไม่เกิน 10 คนที่กำหนดไว้
ถ้าจะช่วยผู้ป่วยได้ครบต้องมียาเหลือเกิน 900 กระปุก
เราจะทำยังไงเพื่อรักษาชีวิตคนให้ได้มากที่สุด โดยที่เสียยาไปน้อยที่สุด?
โจทย์ข้อนี้พอเอามาให้โปรแกรมเมอร์เล่นแล้วพบว่ามี bug เยอะมาก เพราะตัวโจทย์ไม่ได้เคลียเรื่องเวลา มันต้องเอาไปใช้จริงหรือเปล่า บลาๆ ดังนั้นกระผมขอทราบขออภัยที่ไม่ได้ระวังในเรื่องนี้ก่อนครับ 🙇♂️ ดังนั้นแมวน้ำจะขอเฉลยในรูปแบบต่างๆตามด้านล่างนี้ละกันนะ
จำนวนผู้อาสาสมัคร 10 คนนั้น ถ้าเราวางแผนดีๆก็จะสามารถระบุขวดยาพิษได้ 100% เลย โดยการ สลับกันกินคนละครึ่ง ตามตารางด้านล่างนี้
คนที่
ขวดยาที่เหลือ (เริ่มที่ 1,000)
1
500
2
250
3
125
4
62.5
5
31.25
6
15.625
7
7.8125
8
3.90625
9
1.953125
10
0.9765625
จากตารางด้านบนจะทำให้เรารู้ว่า ถ้าใช้คน 1 คน เราจะเสียขวดยาแค่ 500 ขวด แต่ถ้าใช้ 2 คนช่วยกันจะเสียขวดย่แค่ 250 ขวด ไปเรื่อยๆจนอาสาสมัคร 10 คนช่วยกันก็จะเสียขวดยาแค่เพียง 1 ขวดเท่านั้น (เศษปัดขึ้นทุกกรณี)
เพื่อให้เขาใจง่ายๆเลยขอแปลงยาทั้ง 1000 ขวดเป็นตามรูปด้านล่าง ซึ่งในกรอบสีขาวหมายถึงยังไม่มีคนกินยาเลย
ถัดมาให้อาสาคนแรกกินยาไปครึ่งหนึ่ง (1000 / 2 = 500 ขวด) ก็จะได้ตามรูปด้านล่าง
จากรูปด้านบนถ้าโชคดี/โชคร้าย เราก็จะมั่นใจได้ว่ามียาที่ปลอดภัยแน่ๆ 500 ขวด และมีอีก 500 ขวดที่ยังมั่นใจไม่ได้ ดังนั้นเราก็จะให้อาสาสมัครรายที่ 2 ไปช่วยกิน ซึ่งเราก็จะให้เขากิน 500 ขวดเหมือนกัน แต่จะให้เว้นช่วงเป็นครึ่งหนึ่งของคนแรก (500 /2 = 250) ดังนั้นอาสาคนนี้จะกินยา 250 ขวดแล้วเว้นไว้ 250 ขวด สลับไปเรื่อยๆ ตามรูปด้านล่าง
จากรูปด้านบนถ้าโชคดีไม่มีคนตายเลย เราก็จะมั่นใจได้ว่ายาที่อาสาทั้งสองกิน 750 ขวดนั้นปลอดภัย โดยเทียบกับตารางด้านล่างนี้
เหตุการณ์ที่เกิดขึ้น
ยาพิษอยู่ในกลุ่ม
รอดทั้งคู่
F
คนที่ 2 ตายคนเดียว
E
คนที่ 1 ตายคนเดียว
D
ตายทั้งคู่
C
ดังนั้นจากที่ว่ามาเราก็สามารถทำแบบนี้ให้กับอาสามัครไปเรื่อยๆ ให้ทุกคนกินเว้นระยะกันไปแบบนี้เรื่อยๆก็จะทำให้เราได้ผลลัพท์ออกมาราวๆนี้
ดังนั้นจากรูปด้านบนก็จะทำให้เรารู้ว่า กรณีที่ดีที่สุดคืออาสาหมายเลข 10 ตายคนเดียว และ กรณีที่เลวร้ายที่สุดก็อาจจะตายหมดก็ได้ 😥 แต่ไม่ว่ายังไงก็ตาม เราก็จะสามารถระบุขวดที่เป็นยาพิษได้ 100% นั่นเอง
สาเหตุที่ใช้คำว่าอาจจะตายหมด เพราะขึ้นอยู่กับว่าเราจะให้อาสาสมัครกินขวดที่คร่อมกันยังไงนั่นเอง เพราะจำนวนคน 10 คนนั้นสามารถทำความน่าจะเป็นออกมาได้ทั้งหมด 2 ยกกำลัง 10 = 1,024 แบบนั่นเอง
เราก็ให้อาสาสมัครทั้ง 10 คนมายืนตามตำแหน่งด้านล่าง
ถัดมาเราก็ให้อาสาสมัครกินตามเงื่อนไขของตัวเองตามนี้
อธิบายด้านบนนิด เราจะติดเลขไว้บนขวดยาไว้ตั้งแต่ 1~1000 และใส่ขวดยาเปล่าที่ติดเลข 0 ไว้ แล้วส่งไปให้อาสาสมัครทีละขวดตามลำดับ
พอขวดยาขวดแรกที่เป็นเลข 0 มา ก็จะไม่มีใครกินเพราะทุกคนต้องปล่อยให้ขวดยาไหนผ่านเท่ากับตัวเลขที่อยู่ตรงหน้า
ขวดถัดมาที่เป็นเลข 1 ไหลมาปุ๊ป ผู้อาสาคนแรกก็จะเปิดกินเพราะเขาปล่อยขวดยาไหลผ่านครบเงื่อนไขหนึ่งขวดแล้ว ส่วนคนอื่นๆยังไม่ครบก็จะไม่มีใครกิน
ขวดถัดมาที่เป็นเลข 2 ไหลมาปุ๊ป ผู้อาสาคนแรกก็จะไม่กินเพราะกินครบแล้วต้องรอให้มันไหลผ่านไป แต่อาสาหมายเลขสองจะต้องกินเพราะเขาปล่อยขวดยาไหลผ่านไป 2 ขวดครบตามเงื่อนไขแล้ว
ทั้งหมดก็ทำวนแบบนี้ไปเรื่อยๆ
พออธิบายมาถึงตรงนี้เหล่าขาเฟทั้งหลายก็น่าจะถึงบางอ้อนว่า การกินยาเขาไปนั้นก็มีโอกาสแค่ เป็น กับ ตาย เท่านั้น ซึ่งมันก็เหมือนกับ Binary ที่มีค่าเป็น 0 กับ 1 ดังนั้นสมมุติว่าอาสาสมัครหมายเลข 9 กับ 4 ตายเราก็จะรู้เลยว่าขวดยาพิษนั้นเป็นหมายเลข 264 นั่นเอง ตามรูปด้านล่าง
วิธีกินยาแบบนี้กับแบบแรกจริงๆคือแบบเดียวกัน แต่เอามาอธิบายให้ต่างกันนิดหน่อยโดยการกลับด้านเจ๋ยๆ ไม่เชื่อลองเอาคนที่ 10 ของวิธีนี้ไปเทียบกับคนที่ 1 ของวิธีแรกจิ ซึ่งจะเห็นว่ามันไม่ต่างอะไรกันเลยนั่นเอง 😁
อย่างที่บอกว่าโจทย์นี้มี bug เรื่องเวลา ซึ่งถ้ายาพิษมันออกฤทธิ์แบบเที่ยงตรงระดับ millisecond นั่นหมายความว่า เราสามารถให้ผู้สมัครคนเดียวกินยาทั้ง 1,000 ขวด โดยเว้นระยะห่างกัน 0.0001 ms แล้วก็รอดู 23 ชั่วโมงให้หลังว่าเขาจะตาย ms ที่เท่าไหร่นั่นเอง 👏
ของทุกอย่างที่อยู่ในมือเราจะทำแค่ พอผ่าน หรือ ดีเยี่ยม ก็ได้ แต่ไม่ใช่ว่าทุกครั้งจะทำแบบพอผ่านหรือดีเยี่ยมเสมอ เราต้องดูสถานะการณ์ปัจจุบันด้วยว่า ความพอดีมันอยู่ที่ตรงไหน เพราะในบางครั้งที่เรา develope อะไรซักอย่าง เราก็รู้ว่ามันยังทำให้ดียิ่งขึ้นได้อีก แต่จะต้องแลกกับเวลาที่มากขึ้นซึ่งทำให้ส่งงานไม่ได้ ดังนั้นเราก็ควรจะชั่งน้ำหนักว่าจุดไหนคือ ทางสายกลาง ของเรานั่นเองครับ
โจทย์ข้อนี้ถ้าทำพอผ่านก็ให้อาสาสมัคร 10 คนกินยาคนละ 100 ขวด ก็จะผ่านเงื่อนไขขั่นต่ำแล้วนั่นเอง แต่ถ้าจะรีดเน็นจริงๆแล้วคงต้องใช้เวลาคิดมากกว่านี้ ซึ่งถ้าต้องแลกกับเวลาเลี้ยงลูกเลี้ยงเมียมากเกินไป ก็เอาเวลาไปทำในส่วนอื่นจะเหมาะกว่านะ (เมียแอบกระซิบมา) 🤣
แนะนำให้อ่าน บทความนี้เป็นส่วนหนึ่งของ ที่จะคอยรวบรวมโจทย์ที่น่าสนุกคิดเพลินๆ หากใครสนใจอยากดูว่ามีโจทย์อะไรบ้างก็อัญเชิญกดที่ชื่อสีฟ้าๆไปเสพต่อได้เบย ส่วนใครที่คิดว่ามีโจทย์น่าสนใจก็สามารถส่งมาได้ที่ นะกั๊ฟ 😘
