SWERC12

Beehive (Problem A)

Online Judge: [1]

ผึ้งอยู่ในป่าและผึ้งจะเก็บเกษรจากต้นไม้ในป่านี้ ต้นไม้แต่ละต้นกำกับด้วยหมายเลข 0 ถึง n-1 ผึ้งมีรายการของทางเดิน ซึ่งเป็นเส้นตรงที่เชื่อมต่อระหว่างต้นไม้สองต้น ผึ้งจะไม่บินออกนอกทางเดินเด็ดขาด และทางเดินนี้สามารถใช้เดินทางได้ทั้งสองทิศทาง

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

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

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

ข้อมูลนำเข้า

บรรทัดแรกมีค่า T <= 50 ซึ่งระบุจำนวน Test Case ทั้งหมด และมีบรรทัดว่างหนึ่งบรรทัดคั่นระหว่างแต่ละ Test Case และแต่ละ Test Case เป็นดังต่อไปนี้

• บรรทัดแรกประกอบด้วยจำนวนเต็มสองตัวคือ n (2 <= n <= 500) ซึ่งระบุจำนวนต้นไม้ทั้งหมด และ m (0 <= m <= 20000) ซึ่งระบุจำนวนทางเดินทั้งหมด
• หลังจากนั้นอีก m บรรทัดเป็นข้อมูลของทางเดิน แต่ละบรรทัดประกอบด้วยตัวเลขสองตัวคือ u v (0 <= u,v < n และ u != v) ซึ่งระบุว่ามีทางเดินเชื่อมระหว่างต้นไม้ u และ v

ข้อมูลส่งออก

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

ตัวอย่าง

ให้ดูจาก http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=441&page=show_problem&problem=3989

RNA Secondary Structure (Problem D)

Online Judge: [2]

RNA หรือ Ribonucleic Acid เป็นโครงสร้างพื้นฐานของโมเลกุล ซึ่งประกอบด้วยสายโซ่ของส่วนประกอบที่เรียกว่า nucleotides โดย nucleotide นั้นมีอยู่ 4 แบบ เรียกว่าฐาน ซึ่งเขียนแทนด้วยตัวอักษา A, C, G หรือ U โครงสร้างหลักของ RNA นั้นประกอบด้วยฐานดังกล่าวนี้ เราจะกล่าวถึงโครงสร้างรองของ RNA ซึ่งก็คือการจับคู่ของฐานต่าง ๆ โดยที่ฐาน A สามารถจับคู่ได้กับฐาน U และ ฐาน C จับคู่กับฐาน G ความเสถียรของ RNA นั้นขึ้นอยู่กับจำนวนคู่ฐานที่จับกันได้ โครงสร้างสุดท้ายของ RNA คือ โครงสร้างที่มีการจับคู่มากที่สุด

กำหนดให้โครงสร้างหลักนั้นถูกอธิบายด้วยสายอักขระ ของตัวอักษร ACGU กฎของโครงสร้างของโครงสร้างรองเป็นดังต่อไปนี้

1. ฐาน A ใด ๆ สามารถจับกับฐาน U ได้
2. ฐาน C ใด ๆ สามารถจับกับฐาน G ได้
3. ฐานแต่ละฐานนั้นสามารถจับคู่ได้เพียงคู่เดียว
4. กำหนดให้ w < x และ y < z และ w < y ถ้าฐานซึ่งอยู่ ณ ตำแหน่ง w จับคู่กับ ฐาน ณ ตำแหน่ง x และ ฐาน ณ ตำแหน่ง y จับคู่กับฐาน ณ ตำแหน่ง z แล้ว เงื่อนใขหนึ่งในสองข้อต่อไปนี้จะต้องเป็นจริง
   1. y > x
   2. z < x
   3. การจับคู่ระหว่าง C กับ G นั้นไม่สามารถมีได้เกิน K คู่

คุณจะได้รับสายอักขระที่อธิบายถึงโครงสร้างหลักของสิ่งมีชีวิตชนิดหนึ่ง หน้าที่ของคุณคือคำนวณจำนวนการจับคู่ในโครงสร้างสุดท้ายที่ตรงกับเงื่อนไขข้างต้นนี้

โครงสร้างหลักที่มีให้นั้นจะอยู่ในรูปแบบ Run Length Encoding ซึ่งอักขระที่เหมือนกันที่อยู่ติดกันนั้นจะถูกลดรูปเป็นอักขระตามด้วยตัวเลขที่บอกจำนวนตัวที่อยู่ติดกัน ตัวอย่างเช่น “AAAACCGAAUUG” สามารถเขียนได้เป็น “A4C2G1A2U2G1” กล่าวโดยละเอียดคือโครงสร้างหลักนั้นจะอยู่ในรูปแบบ $<c_{1}f_{1}c_{2}f_{2}c_{3}f_{3}...c_{n}f_{n}>$ โดยที่ $c_{i}$ จะเป็น A, C, G หรือ U และ $f_{i}$ จะเป็นตัวเลขจำนวนเต็มบวก

นอกจากนี้ เรายังทราบว่าสิ่งมีชีวิตที่เรากำลังศึกษาอยู่นั้นมีลักษณะดังต่อไปนี้

1. $f_{1}+f_{2}+f_{3}+...f_{n}<=10050$
2. $f_{1}<=5000$
3. $f_{n}<=5000$
4. $f_{2}+f_{3}+f_{4}+...+f_{n-1}<=50$

ข้อมูลนำเข้า

บรรทัดแรกมีค่า T <= 200 ซึ่งระบุจำนวน Test Case ทั้งหมด โดยแต่ละ Test Case เป็นดังต่อไปนี้

• บรรทัดแรกประกอบด้วย run length encoding ของ RNA
• บรรทัดที่สองประกอบด้วยค่า K (0 <= K <= 20) ซึ่งระบุจำนวนคู่ C-G มากสุดที่สามารถมีได้

ข้อมูลส่งออก

ในแต่ละ Test Case ให้พิมพ์หมายเลขของ Test Case ตามด้วยจำนวนการจับคู่มากสุดที่สามารถทำได้

ตัวอย่างและภาพประกอบ

ให้ดูจาก http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=3992

Sentry Robot (Problem F)

Online Judge: [3]

เราต้องการที่จะเฝ้าระวังจุดที่สนใจโดยใช้หุ่นเฝ้ายาม โดยที่หุ่นดังกล่าวไม่สามารถที่จะเคลื่อนที่หรือหันหน้าไปมาได้ เราสามารถวางหุ่นไว้ ณ ตำแหน่งต่าง ๆ โดยหุ่นสามารถหันหน้าไปทางทิศ เหนือ ใต้ ออก ตกเท่านั้น เมื่อวางหุ่นไปแล้วหุ่นจะเฝ้าระวังจุดที่อยู่ตรงหน้ามัน และจุดถัด ๆ ไปที่อยู่ในแถวหรือคอลัมน์เดียวกันเท่านั้น อย่างไรก็ตาม มันมีสิ่งกีดขวางที่หุ่นไม่สามารถมองทะลุได้อยู่

เรามีแผนทีเป็นตาราง จากจุดสนใจที่กำหนดให้ หน้าที่ของเราคือคำนวณหาจำนวนหุ่นน้อยสุดที่ต้องใช้ในการเฝ้าระวังจุดสนใจหล่านี้ การที่หุ่นจะเฝ้าระวังจุดสนใจดังกล่าวได้ หุ่นจะต้องหันหน้าไปทางจุดสนใจและไม่มีสิ่งกีดขวางขวางกั้นอยู่

ยกตัวอย่างเช่นรูปด้านล่างนี้ กำหนดให้ # หมายถึงสิ่งกีดขวาง * หมายถึงจุดสนใจ จำนวนหุ่นน้อยสุดที่สำหรับการเฝ้ายามคือ 2 ตัว โดยวางตำแหน่งและทิศทางดังรูปข้าง ๆ

http://uva.onlinejudge.org/external/125/p12549b.png

รูปต่อไปนี้แสดงตัวอย่างที่ต้องการหุ่น 4 ตัว

http://uva.onlinejudge.org/external/125/p12549c.png

ข้อมูลนำเข้า

บรรทัดแรกมีค่า T <= 50 ซึ่งระบุจำนวน Test Case ทั้งหมด ระหว่าง test case แต่ละอันจะมีบรรทัดว่างหนึ่งบรรทัดนำหน้า โดยแต่ละ Test Case เป็นดังต่อไปนี้

• บรรทัดแรกประกอบด้วยจำนวนเต็มสองตัว Y และ X ซึ่งอธิบายถึงความสูงและความกว้างของตาราง
• บรรทัดที่สองประกอบด้วยจำวนเต็มหนึ่งตัว P ซึ่งระบุถึงจำนวนของจุดสนใจ
• อีก P บรรทัดถัดมา แต่ละบรรทัดมาประกอบด้วยจำนวนเต็มสองตัว px py จะบอกถึงข้อมูลของจุดสนใจแต่ละจุด
• บรรทัดถัดมามีจำนวนเต็ม W ซึ่งระบุถึงจำนวนของสิ่งกีดขวาง
• อีก W บรรทัดถัดมา แต่ละบรรทัดมาประกอบด้วยจำนวนเต็มสองตัว wx wy จะบอกถึงข้อมูลของสิ่งกีดขวางแต่ละตำแหน่ง

ข้อมูลส่งออก

สำหรับแต่ละชุดข้อมูลทดสอบ ให้พิมพ์ตัวเลขจำวนเต็มหนึ่งตัว ซึ่งระบุถึงจำนวนหุ่นยนต์น้อยสุดที่ต้องการ

ข้อกำหนด

• 1<=Y,X<=100
• 0<=P<=Y*X
• 0<=W<=Y*X
• 0<=P+W<=Y*X
• 1<=px;wx<=X
• 1<=py;wy<=Y

ตัวอย่างและภาพประกอบ

ให้ดูจาก http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=441&page=show_problem&problem=3994

Share (Problem H)

Online Judge: [4]

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

หน้าที่ของคุณคือเลือกว่าจะซื้อหุ้นชุดใดบ้างเพื่อให้ได้กำไรมากสุดโดยไม่ใช้เงินเกินทุนที่มีอยู่

ข้อมูลนำเข้า

• บรรทัดแรกระบุค่า C (1 <= C <= 2³²) ซึ่งคือจำนวนเงินทุนที่มีอยู่
• บรรทัดถัดมามีจำนวนเต็มสองตัวคือ N (0 < N <= 500) และ P (0 < P <= 50000) โดย N ระบุถึงจำนวนหุ้นทั้งหมด ส่วน P ระบุถึงจำนวนชุดของหุ้นที่นายหน้านำมาขาย
• อีก N บรรทัดถัดมา แต่ละบรรทัดประกอบด้วยตัวเลขจำนวนเต็มสองตัวคือ ai และ ti จะระบุข้อมูลของหุ้นแต่ละตัวที่ i (1 <= i <= N) โดย ai คือราคาของหุ้น ณ วันนี้ ส่วน ti คือราคาของหุ้น ณ วันพรุ่งนี้
• อีก P บรรทัดถัดมา ระบุข้อมูลของชุดหุ้นแต่ละชุด แต่ละบรรทัด เริ่มต้นด้วยตัวเลข R ซึ่งระบุถึงจำนวนหุ้นในชุด หลังจากนั้นจะมีตัวเลขอีก R คู่ โดยคู่ที่ j (1 <= j <= R) ประกอบด้วยตัวเลขจำนวนเต็มสองตัว คือ sj และ qj โดยที่ sj คือหมายเลขหุ้น ส่วน qj คือจำนวนหุ้นดังกล่าวในชุดนี้

ข้อมูลส่งออก

มีหนึ่งบรรทัด ซึ่งระบุถึงกำไรมากสุดที่สามารถทำได้ในวันนี้

ตัวอย่างและภาพประกอบ

ให้ดูจาก http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=3996