1029 : Magnet
Problem type : Batch
Time limit : 1.0 second(s)
Memory limit : 64 megabyte(s)
Problem type : Batch
Time limit : 1.0 second(s)
Memory limit : 64 megabyte(s)
มหาวิทยาลัยชื่อดังแห่งหนึ่งได้คิดค้นเครื่องสลายพลังแม่เหล็กขึ้น เมื่อนำาแม่เหล็กใดๆ เข้าไปในเครื่องสลายพลังนี้แล้วแม่เหล็กเหล่านั้น จะสูญเสียพลังแม่เหล็กไปชั่ว ขณะหนึ่ง จนกว่าจะหยุดการทำางานของเครื่องสลายพลัง นอกจากนี้ศาสตราจารย์เอ็กซ์ยังได้สร้างแขนกลพลังลมเพื่อใช้ในการพลิกแม่เหล็กไปมา เพื่อใช้ในการพลิกแม่เหล็กเพื่อทดสอบ ภายในเครื่องสลายพลังนี้อีกด้วย
เริ่มต้นมีแม่เหล็กทั้งสิ้น N ชิ้นวางเป็นแถวในแนวตั้ง ภายในเครื่องสลายพลังแม่เหล็ก โดยแม่เหล็กแผ่นบนสุดจะเรียกว่าแผ่นที่ 1 และเรียกแผ่นล่างสุดเรียกว่าแผ่นที่ N กำหนดให้ แม่เหล็กแต่ละชิ้นมีลักษณะเป็นแผ่น โดยด้านหนึ่งของแผ่นแม่เหล็กจะเป็นขั้ว เหนือและอีกด้านหนึ่งของแผ่นจะเป็นขั้ว ใต้ ขณะเริ่มต้นแม่เหล็กทุกชิ้นหันด้านขั้ว เหนือขึ้นด้านบน ดังแสดงในรูป 1 ก) ต่อมาศาสตราจารย์เอ็กซ์ได้พลิกแม่เหล็กไปมาด้วยความสนุกสนานสักพักหนึ่ง จากนั้น ศาสตราจารย์เอ็กซ์ก็จะปิดการทำางานของเครื่องสลายพลังแม่เหล็ก เมื่อเครื่องสลายพลังหยุดทำางาน แม่เหล็กที่วางตัวเรียงกันอยู่นั้น ก็จะเริ่มมีพลังแม่เหล็กอีกครั้ง ทำาให้เกิดแรงดึงดูดกันและแรงผลักระหว่างแม่เหล็กที่ติดกันอีกครั้ง งานของคุณคือหาว่าเมื่อคุณหยิบแม่เหล็กชิ้นหนึ่งออกมาจะมีแม่เหล็กทั้งหมดติดออกมากี่อัน (แม่เหล็กที่อยู่ติดกันและดึงดูดกันจะติดกันออกมาทั้งหมด หมายเหตุ: แม่เหล็กต่างขั้ว กันจะดึงดูดกัน)
สำหรับการสั่ง ให้แขนกลพลังลมทำาการพลิกแม่เหล็กนั้น ศาสตราจารย์เอ็กซ์ได้ออกแบบไว้ดังนี้คือ เราสามารถสั่ง ให้แขนกลพลิกแม่เหล็กจากแผ่นที่ a ไปจำนวน k แผ่นได้ โดยจะทำให้แม่เหล็กทุกแผ่นตั้งแต่แผ่นที่ a จนถึงแผ่นที่ a + k - 1 ถูกพลิก ซึ่งมีผลคือแผ่นแม่เหล็กที่เคยหันขั้วเหนือขึ้นด้านบนก็จะหันขั้วใต้ขึ้นด้านบนแทน และแม่เหล็กแผ่นที่หันขั้วใต้ขึ้นด้านบนก็จะกลับมาหันด้านเหนือขึ้นด้านบนแทน และทำานองเดียวกันในกรณีกลับกัน นอกจากนี้การพลิกแม่เหล็กจะไม่ทำให้ตำาแหน่งของแม่เหล็กเปลี่ยนไป
ตัวอย่างการการพลิกแม่เหล็กสามารถแสดงได้ดังรูปที่ 1 สมมติให้มีแม่เหล็กทั้งสิ้น 10 แผ่น และศาสตราจารย์เอ็กซ์ได้สั่งให้แขนกลพลังลมพลิกแม่เหล็กนี้ทั้งสิ้น 3 ครั้ง โดยครั้งที่ 1 จะพลิกแม่เหล็กจำานวน 4 แผ่นเริ่มต้นจากแผ่นที่ 2, ครั้งที่ 2 พลิกแม่เหล็กจำานวน 5 แผ่นเริ่มต้นจากแผ่นที่ 4, และครั้งสุดท้ายพลิกแม่เหล็กเริ่มต้นจากแผ่นที่ 3 เป็นจำานวน 7 แผ่น
![]()
งานของคุณ
หน้าที่ของคุณคือ ให้หาว่าเมื่อหยุดการทำางานของเครื่องสลายพลังแม่เหล็ก ภายหลังจากการพลิกแม่เหล็กไปมาแล้วนั้น ถ้าต้องการหยิบแม่เหล็กขึ้นมาแผ่นหนึ่งจะมีแม่เหล็กที่ติดกับมันออกมาด้วยกี่ชิ้น
ข้อมูลนำเข้า
บรรทัดแรก รับจำานวนเต็ม 3 จำนวน คือ จำานวนแม่เหล็กทั้งหมด N (1 <= N <=100,000,000), จำนวนครั้ง ที่พลิก M (1 <= M <= 100,000) และจำานวนคำาถาม Q (1 <= Q <= 100,000)
ต่อมาอีก M บรรทัด จะรับข้อมูลการพลิกแม่เหล็ก กล่าวคือ บรรทัดที่ 1+i จะเป็นข้อมูลการพลิกแม่เหล็กครั้งที่ i โดยแต่ละบรรทัดจะรับข้อมูลจำนวนเต็มสองจำนวน ได้แก่ ตำแหน่งเริ่มต้นของแม่เหล็กที่จะพลิก a (1 <= a <=N) และจำนวนชิ้นของแม่เหล็กที่พลิก k (1 <= k <= N) ทั้งนี้ รับประกันว่าจะไม่พลิกแม่เหล็กเกินขอบเขตที่เป็นไปได้ กล่าวคือ รับประกันว่า 1 <= a+k-1 <= N
ต่อมาอีก Q บรรทัด จะรับข้อมูลคำถาม กล่าวคือในบรรทัดที่ 1+M+i จะรับข้อมูล คำถามที่ i โดยในแต่ละบรรทัดจะรับข้อมูลตัวเลขเพียงจำานวนเดียว x (1 <= x <= N) ที่แสดงถึงหมายเลขของแม่เหล็กที่ต้องการถาม
ข้อมูลส่งออก
ให้แสดงคำตอบทั้งสิ้น Q บรรทัด โดยข้อมูลในแต่ละบรรทัดให้แสดงจำานวนของแม่เหล็กทั้งหมดที่จะถูกหยิบออกมาเมื่อคุณหยิบแม่เหล็กแผ่นที่ถาม
ที่มา: Young Thai Online Programming Competition 2008
ความช่วยเหลือ: ไม่มีคำใบ้สำหรับปัญหานี้
เริ่มต้นมีแม่เหล็กทั้งสิ้น N ชิ้นวางเป็นแถวในแนวตั้ง ภายในเครื่องสลายพลังแม่เหล็ก โดยแม่เหล็กแผ่นบนสุดจะเรียกว่าแผ่นที่ 1 และเรียกแผ่นล่างสุดเรียกว่าแผ่นที่ N กำหนดให้ แม่เหล็กแต่ละชิ้นมีลักษณะเป็นแผ่น โดยด้านหนึ่งของแผ่นแม่เหล็กจะเป็นขั้ว เหนือและอีกด้านหนึ่งของแผ่นจะเป็นขั้ว ใต้ ขณะเริ่มต้นแม่เหล็กทุกชิ้นหันด้านขั้ว เหนือขึ้นด้านบน ดังแสดงในรูป 1 ก) ต่อมาศาสตราจารย์เอ็กซ์ได้พลิกแม่เหล็กไปมาด้วยความสนุกสนานสักพักหนึ่ง จากนั้น ศาสตราจารย์เอ็กซ์ก็จะปิดการทำางานของเครื่องสลายพลังแม่เหล็ก เมื่อเครื่องสลายพลังหยุดทำางาน แม่เหล็กที่วางตัวเรียงกันอยู่นั้น ก็จะเริ่มมีพลังแม่เหล็กอีกครั้ง ทำาให้เกิดแรงดึงดูดกันและแรงผลักระหว่างแม่เหล็กที่ติดกันอีกครั้ง งานของคุณคือหาว่าเมื่อคุณหยิบแม่เหล็กชิ้นหนึ่งออกมาจะมีแม่เหล็กทั้งหมดติดออกมากี่อัน (แม่เหล็กที่อยู่ติดกันและดึงดูดกันจะติดกันออกมาทั้งหมด หมายเหตุ: แม่เหล็กต่างขั้ว กันจะดึงดูดกัน)
สำหรับการสั่ง ให้แขนกลพลังลมทำาการพลิกแม่เหล็กนั้น ศาสตราจารย์เอ็กซ์ได้ออกแบบไว้ดังนี้คือ เราสามารถสั่ง ให้แขนกลพลิกแม่เหล็กจากแผ่นที่ a ไปจำนวน k แผ่นได้ โดยจะทำให้แม่เหล็กทุกแผ่นตั้งแต่แผ่นที่ a จนถึงแผ่นที่ a + k - 1 ถูกพลิก ซึ่งมีผลคือแผ่นแม่เหล็กที่เคยหันขั้วเหนือขึ้นด้านบนก็จะหันขั้วใต้ขึ้นด้านบนแทน และแม่เหล็กแผ่นที่หันขั้วใต้ขึ้นด้านบนก็จะกลับมาหันด้านเหนือขึ้นด้านบนแทน และทำานองเดียวกันในกรณีกลับกัน นอกจากนี้การพลิกแม่เหล็กจะไม่ทำให้ตำาแหน่งของแม่เหล็กเปลี่ยนไป
ตัวอย่างการการพลิกแม่เหล็กสามารถแสดงได้ดังรูปที่ 1 สมมติให้มีแม่เหล็กทั้งสิ้น 10 แผ่น และศาสตราจารย์เอ็กซ์ได้สั่งให้แขนกลพลังลมพลิกแม่เหล็กนี้ทั้งสิ้น 3 ครั้ง โดยครั้งที่ 1 จะพลิกแม่เหล็กจำานวน 4 แผ่นเริ่มต้นจากแผ่นที่ 2, ครั้งที่ 2 พลิกแม่เหล็กจำานวน 5 แผ่นเริ่มต้นจากแผ่นที่ 4, และครั้งสุดท้ายพลิกแม่เหล็กเริ่มต้นจากแผ่นที่ 3 เป็นจำานวน 7 แผ่น
งานของคุณ
หน้าที่ของคุณคือ ให้หาว่าเมื่อหยุดการทำางานของเครื่องสลายพลังแม่เหล็ก ภายหลังจากการพลิกแม่เหล็กไปมาแล้วนั้น ถ้าต้องการหยิบแม่เหล็กขึ้นมาแผ่นหนึ่งจะมีแม่เหล็กที่ติดกับมันออกมาด้วยกี่ชิ้น
ข้อมูลนำเข้า
บรรทัดแรก รับจำานวนเต็ม 3 จำนวน คือ จำานวนแม่เหล็กทั้งหมด N (1 <= N <=100,000,000), จำนวนครั้ง ที่พลิก M (1 <= M <= 100,000) และจำานวนคำาถาม Q (1 <= Q <= 100,000)
ต่อมาอีก M บรรทัด จะรับข้อมูลการพลิกแม่เหล็ก กล่าวคือ บรรทัดที่ 1+i จะเป็นข้อมูลการพลิกแม่เหล็กครั้งที่ i โดยแต่ละบรรทัดจะรับข้อมูลจำนวนเต็มสองจำนวน ได้แก่ ตำแหน่งเริ่มต้นของแม่เหล็กที่จะพลิก a (1 <= a <=N) และจำนวนชิ้นของแม่เหล็กที่พลิก k (1 <= k <= N) ทั้งนี้ รับประกันว่าจะไม่พลิกแม่เหล็กเกินขอบเขตที่เป็นไปได้ กล่าวคือ รับประกันว่า 1 <= a+k-1 <= N
ต่อมาอีก Q บรรทัด จะรับข้อมูลคำถาม กล่าวคือในบรรทัดที่ 1+M+i จะรับข้อมูล คำถามที่ i โดยในแต่ละบรรทัดจะรับข้อมูลตัวเลขเพียงจำานวนเดียว x (1 <= x <= N) ที่แสดงถึงหมายเลขของแม่เหล็กที่ต้องการถาม
ข้อมูลส่งออก
ให้แสดงคำตอบทั้งสิ้น Q บรรทัด โดยข้อมูลในแต่ละบรรทัดให้แสดงจำานวนของแม่เหล็กทั้งหมดที่จะถูกหยิบออกมาเมื่อคุณหยิบแม่เหล็กแผ่นที่ถาม
ที่มา: Young Thai Online Programming Competition 2008
| ตัวอย่างข้อมูลนำเข้า | ตัวอย่างข้อมูลส่งออก |
| 10 3 2 2 4 4 5 3 7 7 5 | 3 2 |
ความช่วยเหลือ: ไม่มีคำใบ้สำหรับปัญหานี้
กำลังออนไลน์: 19 ผู้เยี่ยมชมและ 0 สมาชิก (1 บอท)