ผลต่างระหว่างรุ่นของ "SWERC12"
Nattee (คุย | มีส่วนร่วม) |
Nattee (คุย | มีส่วนร่วม) |
||
แถว 5: | แถว 5: | ||
ผึ้งอยู่ในป่าและผึ้งจะเก็บเกษรจากต้นไม้ในป่านี้ ต้นไม้แต่ละต้นกำกับด้วยหมายเลข 0 ถึง n-1 ผึ้งมีรายการของทางเดิน ซึ่งเป็นเส้นตรงที่เชื่อมต่อระหว่างต้นไม้สองต้น ผึ้งจะไม่บินออกนอกทางเดินเด็ดขาด และทางเดินนี้สามารถใช้เดินทางได้ทั้งสองทิศทาง | ผึ้งอยู่ในป่าและผึ้งจะเก็บเกษรจากต้นไม้ในป่านี้ ต้นไม้แต่ละต้นกำกับด้วยหมายเลข 0 ถึง n-1 ผึ้งมีรายการของทางเดิน ซึ่งเป็นเส้นตรงที่เชื่อมต่อระหว่างต้นไม้สองต้น ผึ้งจะไม่บินออกนอกทางเดินเด็ดขาด และทางเดินนี้สามารถใช้เดินทางได้ทั้งสองทิศทาง | ||
− | ผึ้งกำลังวางแผนจะสร้างรังผึ้งใหม่ขึ้นมีหลาย ๆ รังบนต้นไม้บางต้น โดยมีเป้าหมายคือผึ้งจะเลือกสร้างรังบนต้นไม้ที่จำเป็นเท่านั้น และผึ้งจะไม่เก็บเกษรจากกต้นไม้ที่ไม่มีรังอยู่ อย่างไรก็ตาม ผึ้งยังคงต้องการเดินทางจากรังต่าง ๆ ไปยังรังต่าง ๆ ดังนั้น ผึ้งต้องการสร้างรังให้ผิ้งสามารถเดินทางไปมาระหว่างรังต่าง ๆ | + | ผึ้งกำลังวางแผนจะสร้างรังผึ้งใหม่ขึ้นมีหลาย ๆ รังบนต้นไม้บางต้น โดยมีเป้าหมายคือผึ้งจะเลือกสร้างรังบนต้นไม้ที่จำเป็นเท่านั้น และผึ้งจะไม่เก็บเกษรจากกต้นไม้ที่ไม่มีรังอยู่ ดังนั้น ผึ้งจะลบทางเดินที่มิได้เชื่อมต่อระหว่างต้นไม้ที่มีรังอยู่ทิ้งไปทั้งหมด |
+ | |||
+ | อย่างไรก็ตาม ผึ้งยังคงต้องการเดินทางจากรังต่าง ๆ ไปยังรังต่าง ๆ ดังนั้น ผึ้งต้องการสร้างรังให้ผิ้งสามารถเดินทางไปมาระหว่างรังต่าง ๆ โดยใช้เฉพาะทางเดินที่เหลืออยู่หลังจากที่ได้ลบทางเดินที่มิได้ใช้ทิ้งไปแล้ว โดยมีเงื่อนไขว่า ถึงแม้ว่าจะมีทางเดิน 1 ทางในรายการทางเดินนั้นใช้งานไม่ได้ขึ้นมา | ||
นอกจากนี้ ผึ้งต้องการที่จะสร้างรังอย่างน้อยสองรัง (เพราะรังเดียวไม่พอทำกิน) แต่ก็ไม่ต้องการสร้างรังเกินความจำเป็น จากข้อมูลของต้นไม้และทางเดินที่มีอยู่ จงหาว่า ผึ้งต้องสร้างรังกี่รังจึงจะตรงตามข้อกำหนดดังกล่าว (ในบางกรณี ผึ้งอาจจะไม่สามารถสร้างรังตามเงื่อนไขดังกล่าวได้เช่นกัน) | นอกจากนี้ ผึ้งต้องการที่จะสร้างรังอย่างน้อยสองรัง (เพราะรังเดียวไม่พอทำกิน) แต่ก็ไม่ต้องการสร้างรังเกินความจำเป็น จากข้อมูลของต้นไม้และทางเดินที่มีอยู่ จงหาว่า ผึ้งต้องสร้างรังกี่รังจึงจะตรงตามข้อกำหนดดังกล่าว (ในบางกรณี ผึ้งอาจจะไม่สามารถสร้างรังตามเงื่อนไขดังกล่าวได้เช่นกัน) |
รุ่นแก้ไขปัจจุบันเมื่อ 04:59, 14 พฤษภาคม 2556
เนื้อหา
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 ถ้าไม่สามารถสร้างรังตามเงื่อนไขดังกล่าวได้
ตัวอย่าง
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 กฎของโครงสร้างของโครงสร้างรองเป็นดังต่อไปนี้
- ฐาน A ใด ๆ สามารถจับกับฐาน U ได้
- ฐาน C ใด ๆ สามารถจับกับฐาน G ได้
- ฐานแต่ละฐานนั้นสามารถจับคู่ได้เพียงคู่เดียว
- กำหนดให้ w < x และ y < z และ w < y ถ้าฐานซึ่งอยู่ ณ ตำแหน่ง w จับคู่กับ ฐาน ณ ตำแหน่ง x และ ฐาน ณ ตำแหน่ง y จับคู่กับฐาน ณ ตำแหน่ง z แล้ว เงื่อนใขหนึ่งในสองข้อต่อไปนี้จะต้องเป็นจริง
- y > x
- z < x
- การจับคู่ระหว่าง C กับ G นั้นไม่สามารถมีได้เกิน K คู่
คุณจะได้รับสายอักขระที่อธิบายถึงโครงสร้างหลักของสิ่งมีชีวิตชนิดหนึ่ง หน้าที่ของคุณคือคำนวณจำนวนการจับคู่ในโครงสร้างสุดท้ายที่ตรงกับเงื่อนไขข้างต้นนี้
โครงสร้างหลักที่มีให้นั้นจะอยู่ในรูปแบบ Run Length Encoding ซึ่งอักขระที่เหมือนกันที่อยู่ติดกันนั้นจะถูกลดรูปเป็นอักขระตามด้วยตัวเลขที่บอกจำนวนตัวที่อยู่ติดกัน ตัวอย่างเช่น “AAAACCGAAUUG” สามารถเขียนได้เป็น “A4C2G1A2U2G1” กล่าวโดยละเอียดคือโครงสร้างหลักนั้นจะอยู่ในรูปแบบ โดยที่ จะเป็น A, C, G หรือ U และ จะเป็นตัวเลขจำนวนเต็มบวก
นอกจากนี้ เรายังทราบว่าสิ่งมีชีวิตที่เรากำลังศึกษาอยู่นั้นมีลักษณะดังต่อไปนี้
ข้อมูลนำเข้า
บรรทัดแรกมีค่า 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
ตัวอย่างและภาพประกอบ
Online Judge: [4]
คุณเป็นเศรษฐีซึ่งต้องการที่จะลงทุนในตลาดหุ้น โดยคุณมีผู้ช่วยที่สามารถบอกได้ล่วงหน้าว่าราคาหุ้นแต่ละตัวของวันพรุ่งนี้เป็นเท่าไร (คุณรู้ราคาหุ้นของวันนี้อยู่แล้ว) คุณจะทำกำไรโดยซื้อหุ้นในวันนี้และขายหุ้นในวันพรุ่งนี้ ในแต่ละวันคุณมีเงินลงทุนอยู่จำนวนหนึ่ง อย่างไรก็ตาม คุณสามารถซื้อหุ้นได้เฉพาะจากนายหน้าขายหุ้น ซึ่งจะขายหุ้นเป็นชุด ๆ เท่านั้น (คุณไม่สามารถแยกซื้อหุ้นเป็นตัว ๆ ได้ ต้องซื้อหุ้นไปทั้งชุดตามที่นายหน้าจัดไว้ให้)
หน้าที่ของคุณคือเลือกว่าจะซื้อหุ้นชุดใดบ้างเพื่อให้ได้กำไรมากสุดโดยไม่ใช้เงินเกินทุนที่มีอยู่
ข้อมูลนำเข้า
- บรรทัดแรกระบุค่า C (1 <= C <= 232) ซึ่งคือจำนวนเงินทุนที่มีอยู่
- บรรทัดถัดมามีจำนวนเต็มสองตัวคือ 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