Coci

หน้านี้แสดงข้อสอบ coci วันที่ 24 ต.ค. 52 ฉบับแปล

domino

โดมิโนเป็นชิ้นส่วนสำหรับเกมหลาย ๆ เกม แต่ละชิ้นโดมิโนจะมีเครื่องหมายสองอัน แต่ละเครื่องหมายจะมีจุดหลาย ๆ จุด (อาจมี 0 จุดได้) จำนวนจุดขึ้นกับขนาดของเซต (set size) แต่ละเครื่องหมายในชิ้นโดมิโนในเซตขนาด N จะมีค่าตั้งแต่ 0 ถึง N ชิ้นโดมิโนสองชิ้นจะถือว่าเหมือนกันถ้ามีจำนวนจุดเท่ากัน (โดยไม่ขึ้นกับว่าจะอ่านจากทางใด) เช่น ชิ้นที่มีจุด 2 และ 8 จุด จะเหมือนกับชิ้นที่มี 8 และ 2 จุด ชุดโดมิโนที่ถูกต้องจะไม่มีโดมิโนซ้ำกัน เซตโดมิโน ที่สมบูรณ์ ที่มีขนาด N จะมีชิ้นส่วนทั้งหมดที่มีจุด N จุดหรือน้อยกว่านั้น โดยไม่มีชิ้นที่ซ้ำ

เขียนโปรแกรมที่ตำนวณจำนวนจุดรวมบนชิ้นโดมิโนในเซตโดมิโนที่สมบูรณ์ที่มีขนาด N

dobra

Lea เจอคำมากมายในชีวิตของเธอ และเธอไม่พึงใจคำจำนวนมาก เพื่อลดความไม่พึงใจนี้ เธอจึงเริ่มสร้างคำที่เธอพึงใจ Lea สร้างคำใหม่โดยเริ่มจากการเขียนสตริงของตัวอักษรบนกระดาษ หลังจากนั้นเธอจะลบตัวอักษรกลุ่มที่น่าเกลียดที่สุดออกไปแล้วแทนพวกมันแต่ละตัวด้วยเครื่องหมายขีดล่าง (underscore: '_') หลังจากนั้นเธอจะพยายามเปลี่ยนเครืื่องหมายขีดล่างเป็นตัวอักษรที่เธอยอมรับมากกว่าเพื่อทำให้คำนั้นพึงใจเธอ

Lea จะพึงใจคำคำหนึ่ง ถ้าหากว่าคำนั้นไม่มีสระ 3 ตัวติดกัน และไ่ม่มีพยัญชนะ 3 ตัวติดกัน และมีตัวอักษร L อย่างน้อยหนึ่งตัว

สระภาษาโครเอเชียคืิอตัวอักษร A, E, I, O, U เท่านั้น ตัวอักษรอื่นๆ เป็นพยัญชนะทั้งหมด

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

ข้อมูลนำ้เข้ามีเพียงบรรทัดเดียว และในบรรทัดนั้นมีสตริงของตัวอักษรความยาวไม่เกิน 100 ตัวอักษร สตริงนี้จะประกอบด้วยตัวอักษรภาษาอังกฤษตัวพิมพ์ใหญ่และเครื่องหมายขีดล่าง '_' เท่านั้น และจะมีเครื่องหมายขีดล่างไม่เกิน 10 ตัว

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

ข้อมูลส่งออกมีเพียงบรรทัดเดียว และในบรรทัดนั้นจะมีจำนวนเต็มเพียงหนึ่งตัว ซึ่งมีค่าเท่ากับจำนวนคำที่ Lea พีงใจที่สามารถสร้างได้จากการแทนเครื่องหมายขีดล่างในสตริงในข้อมูลนำเข้าด้วยตัวอักษรภาษาอังกฤษตัวพิมพ์ใหญ่

คำเตือน: ใช้เลข 64 บิตเพื่อทำคำตอบ กล่าวคือใช้ long long ในภาษา C/C++ และใช้ int64 ในภาษาปาสกาล

MALI

Mirko และ Slavko กำลังเล่นเกมใหม่กันอยู่ เช่นเคย Slavko เริ่มเกมแต่ละรอบโดยให้จำนวนสองจำนวน A และ B กับ Mirko โดยจำนวนทั้งสองมีค่าน้อยกว่า 100. Mirko จะต้องแก้ปัญหาต่อไปนี้ให้กับ Slavko: จะจับคู่บรรดาจำนวน A ทั้งหมดที่ได้รับมากับบรรดาจำนวน B ทั้งหมดที่ได้รับมาอย่างไร ให้ผลรวมที่มากที่สุดของคู่ทั้งหลายที่จับนั้น มีค่าน้อยที่สุด

กล่าวคือ ถ้าในรอบทั้งหมดก่อนหน้านั้น Slavko ให้จำนวน a1, a2, a3 .... an และ b1, b2, b3 ... bn, ให้หาวิธีการจับคู่ n คู่ (ai, bj) ที่แต่ละจำนวนในลำดับ A ถูกใช้ในหนึ่งคู่พอดี และแต่ละจำนวนในลำดับ B ถูกใช้ในหนึ่งคู่พอดี และ ค่ามากที่สุดของผลรวม ai + bj ในทุกคู่ มีค่าน้อยที่สุด

GENIJALAC

Mirko เป็นอัจฉริยะ แต่เป้าหมายของสิ่งประดิษฐ์ของเขานั้นบางทีก็ไม่ใช่สิ่งที่เห็นได้ชัดเจน สิ่งประดิษฐ์ล่าสุดของเขาคือเครื่อง Shuffle-o-matic 3175 ก็เป็นเช่นนั้น เครื่อง Shuffle-o-matic ถูกนำไปใช้อย่างพิเศษ เริ่มต้น Mirko วานการ์ดกระดาษ N แผ่นที่มีหมายเลข 1 ถึง N พิมพ์อยู่บนพื้นที่ทำงานของเครื่อง Shuffle-o-matic จากนั้นเขาป้อนลำดับการสลับ (shuffle sequence) เข้าสู่เครื่องผ่านทางหน้าจอป้อนข้อมูลเข้าและกดปุ่มเริ่มทำงาน เครื่องจักรก็จะอ่านการ์ดเปล่านั้นและพิมพ์ลำดับของจำนวนที่อ่านเข้าไปออกทางเทปผลลัพธ์ จากนั้นเครื่องจะสลับการ์ดตามลำดับการสลับ (shuffle sequence) หลังจากนั้นเครื่องจากอ่านลำดับใหม่ที่ได้และเขียนผลลัพธ์ออกทางบรรทัดใหม่ที่เทปผลลัพธ์ เครื่องจะดำเนินการสลับการ์ดอีกครั้งโดยใช้ลำดับการสลับเดิม อ่านเทป และพิมพ์ผลลัพธ์ออกทางเทป เครื่องจักรจะทำงานไปเรื่อย ๆ จนกว่าเทปจะหมด

After experimenting with the machine Mirko decided to rest a bit on the floor. There he noticed a piece of output tape. The piece is neatly cut just before the A-th output row nad just after the B-th output row. It is also missing the first C number and the last D numbers in all rows.

He now wonders how many rows on that piece of paper have the property that all numbers in the row, that are still on the paper, are in the exact same spot they were before all the shuffling began.