เกมประกบคู่ (toi10_pairoffours)


Time limit:
1000 ms
Memory limit:
64 MB

ณ ดินแดนแห่งต๋อย (Land of TOI) มีผู้คิดค้นและสร้างเกมแปลกๆ เขาผู้นั้นมีนามว่า มิสเตอร์อูบู้ (Mr. UBU) วันหนึ่ง มิสเตอร์อูบู ได้คิดค้นเกมใหม่ ชื่อ “Pairs of Four” ขึ้น เป็นเกมที่เล่นคนเดียว และใช้การ์ด จํานวนทั้งหมด k ใบในการเล่นเกม การ์ดแต่ละใบจะมีอักษรหนึ่งตัวจากกลุ่มอักษร ‘U’, ‘B’, ‘O’ และ ‘N’ (อักษรภาษาอังกฤษตัวพิมพ์ใหญ่) ปรากฏอยู่บนการ์ด

มิสเตอร์อูบู้ กําหนดขั้นตอนวิธีการเล่นเกม Pairs of Four ไว้ดังนี้

  1. เริ่มต้นมีการ์ดทั้งหมด k ใบ ซึ่งจัดเรียงเป็นแถวตรง โดยไม่ให้การ์ดที่มีอักษรเดียวกันอยู่ติดกัน
  2. ให้คะแนนเริ่มต้นของผู้เล่นเป็น ศูนย์
  3. ผู้เล่นเลือกหยิบการ์ดใบใดก็ได้หนึ่งใบออกจากแถว
  4. หลังจากนั้นให้ผู้เล่นตรวจสอบดูว่า มีการ์ดที่มีอักษรเดียวกันอยู่ติดกันหรือไม่ ถ้าพบว่ามี ให้หยิบการ์ดทั้งสองใบที่มีอักษรเดียวกันนั้นออกจากแถวและเพิ่มคะแนน 1 คะแนน แล้วทําซ้ําขั้นตอนที่ 4
  5. ในกรณีที่มีการ์ดเหลือในแถวมากกว่า 2 ใบ ให้กลับไปทําขั้นตอนที่ 3 มิฉะนั้นให้จบเกม
รูปที่ 1 แสดงตัวอย่างรูปแบบการจัดเรียงเริ่มต้นของการ์ด 6 ใบ ที่มีตัวอักษร ‘U’, ‘B’, ‘N’, ‘B’, ‘O’และ ‘U’ ตามลําดับ

จากรูปแบบการจัดเรียงการ์ดตามรูปที่ 1 สามารถยกตัวอย่างวิธีเล่นเกมบางวิธีได้ ดังนี้

 

จากตัวอย่างทั้งสี่วิธี พบว่า ลำดับในการหยิบการ์ดที่ต่างกันก็อาจจะมีโอกาสที่จะได้คะแนนต่างกัน

มิสเตอรอูบู้ อยากจะทราบว่า ในแต่ละรูปแบบการจัดเรียงการ์ด เพื่อเล่นเกม Pairs of Four นี้ผู้เล่นจะสามารถทําคะแนนได้สูงสุดเท่าไร จึงขอความช่วยเหลือมายังผู้รู้วัยเยาว์ที่มารวมตัวกันในการแข่งขันคอมพิวเตอรโอลิมปกระดับชาติ ครั้งที่ 10 ณ มหาวิทยาลัยอุบลราชธานี

Input

มีจํานวน 2 บรรทัด ดังนี้

บรรทัดแรก มีหนึ่งจํานวน คือจํานวนเต็ม k ซึ่งแทนจํานวนการ์ดทั้งหมดที่ใช้เล่นเกม เมื่อ 5 ≤ k ≤ 1,000

บรรทัดที่ 2 แสดงรูปแบบการจัดเรียงการด จํานวน k ใบ จากซ้ายไปขวา ด้วยอักษรภาษาอังกฤษตัวพิมพใหญ ‘U’, ‘B’, ‘O’ หรือ ‘N’ จํานวน k ตัว โดยที่แต่ละตัวถูกคั่นด้วยช่องว่างหนึ่งช่อง

Output

มีบรรทัดเดียว แสดงคะแนนสูงสุดที่ผู้เล่นเกมจะสามารถทําได้

Constrains/Subtasks

  • Subtask #1: k ≤ 25 (20 points)
  • Subtask #2: k ≤ 50 (20 points)
  • Subtask #4: Original Constraints (60 points)

Editor:

Source: Thailand Olympiad in Informatics 2014 (TOI10 / TOI 2014)

Select description language

Thai (raw)

If you don't find what you want

Translate it!

Edit this description

Edit

Tag

None