| description |
|---|
โจทย์สอบสัมภาษณ์เข้า Saladpuk |
ทรัพยากรทั้งโลกสามารถผลิตยาต้านโควิดได้แค่ 1,000 ขวดเท่านั้น แต่ก็ดันมีคนร้ายแอบผสมยาพิษลงไป 1 ขวด ซึ่งยาพิษตัวนี้ตรวจด้วยวิธีการใดๆก็ไม่พบ และคนที่กินก็จะตายในอีก 23 ชั่วโมงหลังจากที่กินเข้าไป ประจวบกับคนสำคัญทั่วโลกต้องได้รับยาตัวนี้ภายใน 24 ชั่วโมงไม่งั้นจะไม่สามารถรักษาชีวิตพวกเขาไว้ได้ ซึ่งทั่วทั้งโลกมีอาสาสมัครเพียงแค่ 10 คนเท่านั้น ที่พร้อมจะกินยาเหล่านั้นแม้รู้ว่าอาจจะตายก็ตาม
- ในขวดมียาหลายเม็ด ส่วนคนกินแค่เม็ดเดียวก็พอ
- ทุกเม็ดในขวดยาพิษกินแล้วตายใน 23 ชม เหมือนกัน
- จะให้คนกินกี่เม็ดก็ได้ กี่ขวดก็ได้ กินขวดซ้ำกันก็ได้
- จะใช้อาสาสมัครทุกคน หรือ แค่บางคนก็ได้ แต่ต้องไม่เกิน 10 คนที่กำหนดไว้
- ถ้าจะช่วยผู้ป่วยได้ครบต้องมียาเหลือเกิน 900 กระปุก
เราจะทำยังไงเพื่อรักษาชีวิตคนให้ได้มากที่สุด โดยที่เสียยาไปน้อยที่สุด?
{% hint style="success" %}
แนะนำให้อ่าน
บทความนี้เป็นส่วนหนึ่งของ 🧠 Challenges ที่จะคอยรวบรวมโจทย์ที่น่าสนุกคิดเพลินๆ หากใครสนใจอยากดูว่ามีโจทย์อะไรบ้างก็อัญเชิญกดที่ชื่อสีฟ้าๆไปเสพต่อได้เบย ส่วนใครที่คิดว่ามีโจทย์น่าสนใจก็สามารถส่งมาได้ที่ Saladpuk Fanclub นะกั๊ฟ 😘
{% endhint %}
โจทย์ข้อนี้พอเอามาให้โปรแกรมเมอร์เล่นแล้วพบว่ามี 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 ขวด ก็จะผ่านเงื่อนไขขั่นต่ำแล้วนั่นเอง แต่ถ้าจะรีดเน็นจริงๆแล้วคงต้องใช้เวลาคิดมากกว่านี้ ซึ่งถ้าต้องแลกกับเวลาเลี้ยงลูกเลี้ยงเมียมากเกินไป ก็เอาเวลาไปทำในส่วนอื่นจะเหมาะกว่านะ (เมียแอบกระซิบมา) 🤣