ผลต่างระหว่างรุ่นของ "Coci"
Cardcaptor (คุย | มีส่วนร่วม) (→ALADIN) |
(→ALADIN) |
||
| (ไม่แสดง 11 รุ่นระหว่างกลางโดยผู้ใช้ 3 คน) | |||
| แถว 4: | แถว 4: | ||
โดมิโนเป็นชิ้นส่วนสำหรับเกมหลาย ๆ เกม แต่ละชิ้นโดมิโนจะมีเครื่องหมายสองอัน แต่ละเครื่องหมายจะมีจุดหลาย ๆ จุด (อาจมี 0 จุดได้) จำนวนจุดขึ้นกับขนาดของ''เซต'' (''set'' size) แต่ละเครื่องหมายในชิ้นโดมิโนในเซตขนาด '''N''' จะมีค่าตั้งแต่ 0 ถึง '''N''' ชิ้นโดมิโนสองชิ้นจะถือว่าเหมือนกันถ้ามีจำนวนจุดเท่ากัน (โดยไม่ขึ้นกับว่าจะอ่านจากทางใด) เช่น ชิ้นที่มีจุด 2 และ 8 จุด จะเหมือนกับชิ้นที่มี 8 และ 2 จุด ชุดโดมิโนที่ถูกต้องจะไม่มีโดมิโนซ้ำกัน เซตโดมิโน '''ที่สมบูรณ์''' ที่มีขนาด '''N''' จะมีชิ้นส่วนทั้งหมดที่มีจุด '''N''' จุดหรือน้อยกว่านั้น โดยไม่มีชิ้นที่ซ้ำ | โดมิโนเป็นชิ้นส่วนสำหรับเกมหลาย ๆ เกม แต่ละชิ้นโดมิโนจะมีเครื่องหมายสองอัน แต่ละเครื่องหมายจะมีจุดหลาย ๆ จุด (อาจมี 0 จุดได้) จำนวนจุดขึ้นกับขนาดของ''เซต'' (''set'' size) แต่ละเครื่องหมายในชิ้นโดมิโนในเซตขนาด '''N''' จะมีค่าตั้งแต่ 0 ถึง '''N''' ชิ้นโดมิโนสองชิ้นจะถือว่าเหมือนกันถ้ามีจำนวนจุดเท่ากัน (โดยไม่ขึ้นกับว่าจะอ่านจากทางใด) เช่น ชิ้นที่มีจุด 2 และ 8 จุด จะเหมือนกับชิ้นที่มี 8 และ 2 จุด ชุดโดมิโนที่ถูกต้องจะไม่มีโดมิโนซ้ำกัน เซตโดมิโน '''ที่สมบูรณ์''' ที่มีขนาด '''N''' จะมีชิ้นส่วนทั้งหมดที่มีจุด '''N''' จุดหรือน้อยกว่านั้น โดยไม่มีชิ้นที่ซ้ำ | ||
| − | + | เขียนโปรแกรมที่คำนวณจำนวนจุดรวมบนชิ้นโดมิโนในเซตโดมิโนที่สมบูรณ์ที่มีขนาด '''N''' | |
== dobra == | == dobra == | ||
| − | Lea เจอคำมากมายในชีวิตของเธอ และเธอไม่พึงใจคำจำนวนมาก เพื่อลดความไม่พึงใจนี้ เธอจึงเริ่มสร้างคำที่เธอพึงใจ Lea สร้างคำใหม่โดยเริ่มจากการเขียนสตริงของตัวอักษรบนกระดาษ หลังจากนั้นเธอจะลบตัวอักษรกลุ่มที่น่าเกลียดที่สุดออกไปแล้วแทนพวกมันแต่ละตัวด้วยเครื่องหมายขีดล่าง (underscore: '_') | + | Lea เจอคำมากมายในชีวิตของเธอ และเธอไม่พึงใจคำจำนวนมาก เพื่อลดความไม่พึงใจนี้ เธอจึงเริ่มสร้างคำที่เธอพึงใจ Lea สร้างคำใหม่โดยเริ่มจากการเขียนสตริงของตัวอักษรบนกระดาษ หลังจากนั้นเธอจะลบตัวอักษรกลุ่มที่น่าเกลียดที่สุดออกไปแล้วแทนพวกมันแต่ละตัวด้วยเครื่องหมายขีดล่าง (underscore: '_') หลังจากนั้นเธอจะพยายามเปลี่ยนเครื่องหมายขีดล่างเป็นตัวอักษรที่เธอยอมรับมากกว่าเพื่อทำให้คำนั้นพึงใจเธอ |
| − | Lea จะพึงใจคำคำหนึ่ง ถ้าหากว่าคำนั้นไม่มีสระ 3 ตัวติดกัน | + | Lea จะพึงใจคำคำหนึ่ง ถ้าหากว่าคำนั้นไม่มีสระ 3 ตัวติดกัน และไม่มีพยัญชนะ 3 ตัวติดกัน และมีตัวอักษร L อย่างน้อยหนึ่งตัว |
| − | + | สระภาษาโครเอเชียคือตัวอักษร A, E, I, O, U เท่านั้น ตัวอักษรอื่นๆ เป็นพยัญชนะทั้งหมด | |
=== ข้อมูลนำเข้า === | === ข้อมูลนำเข้า === | ||
| − | + | ข้อมูลนำเข้ามีเพียงบรรทัดเดียว และในบรรทัดนั้นมีสตริงของตัวอักษรความยาวไม่เกิน 100 ตัวอักษร สตริงนี้จะประกอบด้วยตัวอักษรภาษาอังกฤษตัวพิมพ์ใหญ่และเครื่องหมายขีดล่าง '_' เท่านั้น และจะมีเครื่องหมายขีดล่างไม่เกิน 10 ตัว | |
=== ข้อมูลส่งออก === | === ข้อมูลส่งออก === | ||
| แถว 28: | แถว 28: | ||
== GENIJALAC == | == GENIJALAC == | ||
| − | Mirko เป็นอัจฉริยะ แต่เป้าหมายของสิ่งประดิษฐ์ของเขานั้นบางทีก็ไม่ใช่สิ่งที่เห็นได้ชัดเจน สิ่งประดิษฐ์ล่าสุดของเขาคือเครื่อง Shuffle-o-matic 3175 ก็เป็นเช่นนั้น เครื่อง Shuffle-o-matic ถูกนำไปใช้อย่างพิเศษ เริ่มต้น Mirko | + | Mirko เป็นอัจฉริยะ แต่เป้าหมายของสิ่งประดิษฐ์ของเขานั้นบางทีก็ไม่ใช่สิ่งที่เห็นได้ชัดเจน สิ่งประดิษฐ์ล่าสุดของเขาคือเครื่อง Shuffle-o-matic 3175 ก็เป็นเช่นนั้น เครื่อง Shuffle-o-matic ถูกนำไปใช้อย่างพิเศษ เริ่มต้น Mirko วางการ์ดกระดาษ N แผ่นที่มีหมายเลข 1 ถึง N พิมพ์อยู่บนพื้นที่ทำงานของเครื่อง Shuffle-o-matic จากนั้นเขาป้อนลำดับการสลับ (shuffle sequence) เข้าสู่เครื่องผ่านทางหน้าจอป้อนข้อมูลเข้าและกดปุ่มเริ่มทำงาน เครื่องจักรก็จะอ่านการ์ดเปล่านั้นและพิมพ์ลำดับของจำนวนที่อ่านเข้าไปออกทางเทปผลลัพธ์ จากนั้นเครื่องจะสลับการ์ดตามลำดับการสลับ (shuffle sequence) หลังจากนั้นเครื่องจากอ่านลำดับใหม่ที่ได้และเขียนผลลัพธ์ออกทางบรรทัดใหม่ที่เทปผลลัพธ์ เครื่องจะดำเนินการสลับการ์ดอีกครั้ง'''โดยใช้ลำดับการสลับเดิม''', อ่านการ์ด, และพิมพ์ผลลัพธ์ออกทางเทป เครื่องจักรจะทำงานไปเรื่อย ๆ จนกว่าเทปจะหมด |
หลังจากได้ทดลองกับเครื่องไปแล้ว Mirko ได้ตกลงใจว่าจะนอนพักสักพักที่บนพื้น จากที่ตรงนั้นเขาสังเกตเห็นชิ้นของเทปผลลัพธ์ ชิ้นผลลัพธ์นั้นถูกตัดอย่างพอดิบพอดีก่อนบรรทัดที่ '''A''' และหลังบรรทัดที่ '''B''' นอกจากนั้นยังขาดจำนวนไป '''C''' จำนวนในตอนต้น และขาดอีก '''D''' จำนวน ในแต่ละบรรทัด | หลังจากได้ทดลองกับเครื่องไปแล้ว Mirko ได้ตกลงใจว่าจะนอนพักสักพักที่บนพื้น จากที่ตรงนั้นเขาสังเกตเห็นชิ้นของเทปผลลัพธ์ ชิ้นผลลัพธ์นั้นถูกตัดอย่างพอดิบพอดีก่อนบรรทัดที่ '''A''' และหลังบรรทัดที่ '''B''' นอกจากนั้นยังขาดจำนวนไป '''C''' จำนวนในตอนต้น และขาดอีก '''D''' จำนวน ในแต่ละบรรทัด | ||
| แถว 38: | แถว 38: | ||
'''500 000''', '''A''' ≤ '''B''' ≤ '''10^12''', '''0''' ≤ '''C''', '''D''' ≤ '''N''', '''C''' + '''D''' < '''N'''). | '''500 000''', '''A''' ≤ '''B''' ≤ '''10^12''', '''0''' ≤ '''C''', '''D''' ≤ '''N''', '''C''' + '''D''' < '''N'''). | ||
| − | บรรทัดที่สองระบุลำดับการสลับ (shuffle sequence) ลำดับดังกล่าวระบุเป็นการเรียงสับเปลี่ยน (permutation) ของจำนวนเต็มตั้งแต่ '''1''' ถึง '''N''' ถ้าจำนวนที่ '''k''' มีค่าเท่ากับ '''x''' หลังการสลับทุกครั้ง จำนวนที่ '''k'' ในลำดับผลลัพธ์จะมีค่าเท่ากับจำนวนที่ '''x''' ในลำดับตั้งต้น | + | บรรทัดที่สองระบุลำดับการสลับ (shuffle sequence) ลำดับดังกล่าวระบุเป็นการเรียงสับเปลี่ยน (permutation) ของจำนวนเต็มตั้งแต่ '''1''' ถึง '''N''' ถ้าจำนวนที่ '''k''' มีค่าเท่ากับ '''x''' หลังการสลับทุกครั้ง จำนวนที่ '''k''' ในลำดับผลลัพธ์จะมีค่าเท่ากับจำนวนที่ '''x''' ในลำดับตั้งต้น |
== ALADIN == | == ALADIN == | ||
| − | วันหนึ่ง ขณะที่อลาดินกำลังเดินอยู่ เขาเจอสิ่งที่แปลกที่สุดที่เคยเจอมา เขาเห็นกล่องว่าง '''N''' กล่องวางอยู่ข้างๆ เครื่องจักรต่างด้าวเครื่องหนึ่ง หลังจากอลาดินสำรวจเครื่องจักรนั้นพักหนึ่ง | + | วันหนึ่ง ขณะที่อลาดินกำลังเดินอยู่ เขาเจอสิ่งที่แปลกที่สุดที่เคยเจอมา เขาเห็นกล่องว่าง '''N''' กล่องวางอยู่ข้างๆ เครื่องจักรต่างด้าวเครื่องหนึ่ง หลังจากอลาดินสำรวจเครื่องจักรนั้นพักหนึ่ง เขาก็สามารถใช้เครื่องจักรได้ เขาพบว่าเครื่องจักรนั้นรับจำนวนเต็มสี่ตัว '''L''', '''R''', '''A''', และ '''B''' และหลังจากที่เขากดปุ่มเรืองแสงสีแดงที่มีข้อความเขียนไว้ว่า "NEDIRAJ" แล้ว เครื่องจักรก็จะเริ่มทำงานอย่างบ้าคลั่ง ตามขั้นตอนต่อไปนี้ |
* มันทำให้กล่องหมายเลข '''L''' มีก้อนหินอยู่ '''A''' mod '''B''' ก้อน | * มันทำให้กล่องหมายเลข '''L''' มีก้อนหินอยู่ '''A''' mod '''B''' ก้อน | ||
* จากนั้นมันจึงบินไปที่กล่องหมายเลข '''L'''+1 และทำให้กล่องนั้นมีก้อนหินอยู่ (2*'''A''') mod '''B''' | * จากนั้นมันจึงบินไปที่กล่องหมายเลข '''L'''+1 และทำให้กล่องนั้นมีก้อนหินอยู่ (2*'''A''') mod '''B''' | ||
| − | * จากนั้นมันจึงบินไปที่กล่องหมายเลข '''L'''+ | + | * จากนั้นมันจึงบินไปที่กล่องหมายเลข '''L'''+2 และทำให้กล่องนั้นมีก้อนหินอยู่ (3*'''A''') mod '''B''' |
| − | * โดยทั่วไปแล้ว | + | * โดยทั่วไปแล้ว มันจะบินไปยังกล่องทุกกล่องที่มีหมายเลขอยู่ระหว่าง '''L''' และ '''R''' และทำให้กล่องนั้นมีหินปรากฎอยู่เป็นจำนวนเท่ากับ (('''X''' - '''L''' + 1) * '''A''') mod '''B''' เมื่อ '''X''' เป็นหมายเลขของกล่อง |
* หลังจากทำงานที่กล่องหมายเลข '''R''' เสร็จแล้ว มันจะหยุดการทำงานและรอคอยคำสั่งต่อไป | * หลังจากทำงานที่กล่องหมายเลข '''R''' เสร็จแล้ว มันจะหยุดการทำงานและรอคอยคำสั่งต่อไป | ||
| แถว 54: | แถว 54: | ||
=== ข้อมูลนำเข้า === | === ข้อมูลนำเข้า === | ||
| − | + | บรรทัดแรกมีจำนวนเต็ม N และ Q (1 <= N <= 1,000,000,000) และ (1 <= Q <= 50,000) ซึ่งแสดงจำนวนกล่องและจำนวนคำถาม ตามลำดับ | |
หลังจากนั้น Q บรรทัดจะมีข้อมูลเกี่ยวกับการจำลองการทำงานของเครื่องจักรนั้น | หลังจากนั้น Q บรรทัดจะมีข้อมูลเกี่ยวกับการจำลองการทำงานของเครื่องจักรนั้น | ||
| แถว 60: | แถว 60: | ||
ถ้าหากบรรทัดใดในบรรทัด Q บรรทัดนี้เริ่มต้นด้วยเลข 1 มันจะมีรูปแบบ "1 L R A B" (1 <= L <= R <= N) (1 <= A, B <= 1,000,000) ซึ่งมีความหมายว่าอลาดินใส่เลข L, R, A, B แล้วกดปุ่มเพื่อสั่งให้เครื่องจักรเริ่มทำงาน | ถ้าหากบรรทัดใดในบรรทัด Q บรรทัดนี้เริ่มต้นด้วยเลข 1 มันจะมีรูปแบบ "1 L R A B" (1 <= L <= R <= N) (1 <= A, B <= 1,000,000) ซึ่งมีความหมายว่าอลาดินใส่เลข L, R, A, B แล้วกดปุ่มเพื่อสั่งให้เครื่องจักรเริ่มทำงาน | ||
| − | แต่ถ้าหากบรรทัดใดในบรรทัด Q บรรทัดนี้เริ่มต้นด้วยเลข 2 มันจะมีรูปแบบ "2 L R" (1 <= L <= R <= N) | + | แต่ถ้าหากบรรทัดใดในบรรทัด Q บรรทัดนี้เริ่มต้นด้วยเลข 2 มันจะมีรูปแบบ "2 L R" (1 <= L <= R <= N) หมายความว่าอลาดินต้องการทราบว่ามีหินอยู่จำนวนเท่าไหร่ในกล่องตั้งแต่หมายเลข L ถึง R (รวมขอบด้วย) |
=== ข้อมูลส่งออก === | === ข้อมูลส่งออก === | ||
| − | สำหรับคำถามที่ขึ้นต้นด้วย 2 ให้พิมพ์คำตอบของคำถามนั้นในบรรทัดบรรทัดหนึ่ง | + | สำหรับคำถามที่ขึ้นต้นด้วย 2 ให้พิมพ์คำตอบของคำถามนั้นในบรรทัดบรรทัดหนึ่ง คำตอบของคำถามจะต้องเรียงตามลำดับที่คำถามปรากฏในข้อมูลนำเข้า |
=== การให้คะแนน === | === การให้คะแนน === | ||
รุ่นแก้ไขปัจจุบันเมื่อ 17:06, 24 ตุลาคม 2552
หน้านี้แสดงข้อสอบ 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) หลังจากนั้นเครื่องจากอ่านลำดับใหม่ที่ได้และเขียนผลลัพธ์ออกทางบรรทัดใหม่ที่เทปผลลัพธ์ เครื่องจะดำเนินการสลับการ์ดอีกครั้งโดยใช้ลำดับการสลับเดิม, อ่านการ์ด, และพิมพ์ผลลัพธ์ออกทางเทป เครื่องจักรจะทำงานไปเรื่อย ๆ จนกว่าเทปจะหมด
หลังจากได้ทดลองกับเครื่องไปแล้ว Mirko ได้ตกลงใจว่าจะนอนพักสักพักที่บนพื้น จากที่ตรงนั้นเขาสังเกตเห็นชิ้นของเทปผลลัพธ์ ชิ้นผลลัพธ์นั้นถูกตัดอย่างพอดิบพอดีก่อนบรรทัดที่ A และหลังบรรทัดที่ B นอกจากนั้นยังขาดจำนวนไป C จำนวนในตอนต้น และขาดอีก D จำนวน ในแต่ละบรรทัด
เขาสงสัยว่ามีกี่บรรทัดในชิ้นส่วนผลลัพธ์นั้นที่มีคุณสมบัติที่ว่า ทุก ๆ จำนวนในแถวนั้นที่อยู่บนกระดาษชิ้นนั้น อยู่ในตำแหน่งเดียวกับที่อยู่ก่อนการสลับจะเริ่มต้น
ข้อมูลนำเข้า
บรรทัดแรกระบุจำนวนเต็ม N, A, B, C, และ D ในลำดับดังกล่าว (1 ≤ N ≤ 500 000, A ≤ B ≤ 10^12, 0 ≤ C, D ≤ N, C + D < N).
บรรทัดที่สองระบุลำดับการสลับ (shuffle sequence) ลำดับดังกล่าวระบุเป็นการเรียงสับเปลี่ยน (permutation) ของจำนวนเต็มตั้งแต่ 1 ถึง N ถ้าจำนวนที่ k มีค่าเท่ากับ x หลังการสลับทุกครั้ง จำนวนที่ k ในลำดับผลลัพธ์จะมีค่าเท่ากับจำนวนที่ x ในลำดับตั้งต้น
ALADIN
วันหนึ่ง ขณะที่อลาดินกำลังเดินอยู่ เขาเจอสิ่งที่แปลกที่สุดที่เคยเจอมา เขาเห็นกล่องว่าง N กล่องวางอยู่ข้างๆ เครื่องจักรต่างด้าวเครื่องหนึ่ง หลังจากอลาดินสำรวจเครื่องจักรนั้นพักหนึ่ง เขาก็สามารถใช้เครื่องจักรได้ เขาพบว่าเครื่องจักรนั้นรับจำนวนเต็มสี่ตัว L, R, A, และ B และหลังจากที่เขากดปุ่มเรืองแสงสีแดงที่มีข้อความเขียนไว้ว่า "NEDIRAJ" แล้ว เครื่องจักรก็จะเริ่มทำงานอย่างบ้าคลั่ง ตามขั้นตอนต่อไปนี้
- มันทำให้กล่องหมายเลข L มีก้อนหินอยู่ A mod B ก้อน
- จากนั้นมันจึงบินไปที่กล่องหมายเลข L+1 และทำให้กล่องนั้นมีก้อนหินอยู่ (2*A) mod B
- จากนั้นมันจึงบินไปที่กล่องหมายเลข L+2 และทำให้กล่องนั้นมีก้อนหินอยู่ (3*A) mod B
- โดยทั่วไปแล้ว มันจะบินไปยังกล่องทุกกล่องที่มีหมายเลขอยู่ระหว่าง L และ R และทำให้กล่องนั้นมีหินปรากฎอยู่เป็นจำนวนเท่ากับ ((X - L + 1) * A) mod B เมื่อ X เป็นหมายเลขของกล่อง
- หลังจากทำงานที่กล่องหมายเลข R เสร็จแล้ว มันจะหยุดการทำงานและรอคอยคำสั่งต่อไป
ระหว่างที่กำลังเล่นกับเครื่องจักรนี้อยู่ อลาดินสงสัยว่าในกล่องที่อยู่ติดกันกลุ่มหนึ่งมีหินอยู่จำนวนทั้งหมดเท่าใด?
จงเขียนโปรแกรมเพื่อจำลองการทำงานของเครื่องจักรและตอบคำถามของอลาดิน
ข้อมูลนำเข้า
บรรทัดแรกมีจำนวนเต็ม N และ Q (1 <= N <= 1,000,000,000) และ (1 <= Q <= 50,000) ซึ่งแสดงจำนวนกล่องและจำนวนคำถาม ตามลำดับ
หลังจากนั้น Q บรรทัดจะมีข้อมูลเกี่ยวกับการจำลองการทำงานของเครื่องจักรนั้น
ถ้าหากบรรทัดใดในบรรทัด Q บรรทัดนี้เริ่มต้นด้วยเลข 1 มันจะมีรูปแบบ "1 L R A B" (1 <= L <= R <= N) (1 <= A, B <= 1,000,000) ซึ่งมีความหมายว่าอลาดินใส่เลข L, R, A, B แล้วกดปุ่มเพื่อสั่งให้เครื่องจักรเริ่มทำงาน
แต่ถ้าหากบรรทัดใดในบรรทัด Q บรรทัดนี้เริ่มต้นด้วยเลข 2 มันจะมีรูปแบบ "2 L R" (1 <= L <= R <= N) หมายความว่าอลาดินต้องการทราบว่ามีหินอยู่จำนวนเท่าไหร่ในกล่องตั้งแต่หมายเลข L ถึง R (รวมขอบด้วย)
ข้อมูลส่งออก
สำหรับคำถามที่ขึ้นต้นด้วย 2 ให้พิมพ์คำตอบของคำถามนั้นในบรรทัดบรรทัดหนึ่ง คำตอบของคำถามจะต้องเรียงตามลำดับที่คำถามปรากฏในข้อมูลนำเข้า
การให้คะแนน
ในข้อมูลทดสอบที่มีค่า 30% ของคะแนนทั้งหมด N และ Q จะมีค่าไม่เกิน 1,000
ในข้อมูลทดสอบที่มีค่า 70% ของคะแนนทั้งหมด Q จะมีค่าไม่เกิน 1,000
