1029.html

<span style="font-family: Courier New;">มหาวิทยาลัยชื่อดังแห่งหนึ่งได้คิดค้นเครื่องสลายพลังแม่เหล็กขึ้น เมื่อนำาแม่เหล็กใดๆ เข้าไปในเครื่องสลายพลังนี้แล้วแม่เหล็กเหล่านั้น จะสูญเสียพลังแม่เหล็กไปชั่ว ขณะหนึ่ง จนกว่าจะหยุดการทำางานของเครื่องสลายพลัง นอกจากนี้ศาสตราจารย์เอ็กซ์ยังได้สร้างแขนกลพลังลมเพื่อใช้ในการพลิกแม่เหล็กไปมา เพื่อใช้ในการพลิกแม่เหล็กเพื่อทดสอบ ภายในเครื่องสลายพลังนี้อีกด้วย<br />
<br />
เริ่มต้นมีแม่เหล็กทั้งสิ้น N ชิ้นวางเป็นแถวในแนวตั้ง ภายในเครื่องสลายพลังแม่เหล็ก โดยแม่เหล็กแผ่นบนสุดจะเรียกว่าแผ่นที่ 1 และเรียกแผ่นล่างสุดเรียกว่าแผ่นที่ N กำหนดให้ แม่เหล็กแต่ละชิ้นมีลักษณะเป็นแผ่น โดยด้านหนึ่งของแผ่นแม่เหล็กจะเป็นขั้ว เหนือและอีกด้านหนึ่งของแผ่นจะเป็นขั้ว ใต้ ขณะเริ่มต้นแม่เหล็กทุกชิ้นหันด้านขั้ว เหนือขึ้นด้านบน ดังแสดงในรูป 1 ก) ต่อมาศาสตราจารย์เอ็กซ์ได้พลิกแม่เหล็กไปมาด้วยความสนุกสนานสักพักหนึ่ง จากนั้น ศาสตราจารย์เอ็กซ์ก็จะปิดการทำางานของเครื่องสลายพลังแม่เหล็ก เมื่อเครื่องสลายพลังหยุดทำางาน แม่เหล็กที่วางตัวเรียงกันอยู่นั้น ก็จะเริ่มมีพลังแม่เหล็กอีกครั้ง ทำาให้เกิดแรงดึงดูดกันและแรงผลักระหว่างแม่เหล็กที่ติดกันอีกครั้ง งานของคุณคือหาว่าเมื่อคุณหยิบแม่เหล็กชิ้นหนึ่งออกมาจะมีแม่เหล็กทั้งหมดติดออกมากี่อัน (แม่เหล็กที่อยู่ติดกันและดึงดูดกันจะติดกันออกมาทั้งหมด หมายเหตุ: แม่เหล็กต่างขั้ว กันจะดึงดูดกัน)<br />
<br />
สำหรับการสั่ง ให้แขนกลพลังลมทำาการพลิกแม่เหล็กนั้น ศาสตราจารย์เอ็กซ์ได้ออกแบบไว้ดังนี้คือ เราสามารถสั่ง ให้แขนกลพลิกแม่เหล็กจากแผ่นที่ a ไปจำนวน k แผ่นได้  โดยจะทำให้แม่เหล็กทุกแผ่นตั้งแต่แผ่นที่ a จนถึงแผ่นที่ a + k - 1 ถูกพลิก ซึ่งมีผลคือแผ่นแม่เหล็กที่เคยหันขั้วเหนือขึ้นด้านบนก็จะหันขั้วใต้ขึ้นด้านบนแทน และแม่เหล็กแผ่นที่หันขั้วใต้ขึ้นด้านบนก็จะกลับมาหันด้านเหนือขึ้นด้านบนแทน และทำานองเดียวกันในกรณีกลับกัน นอกจากนี้การพลิกแม่เหล็กจะไม่ทำให้ตำาแหน่งของแม่เหล็กเปลี่ยนไป<br />
<br />
ตัวอย่างการการพลิกแม่เหล็กสามารถแสดงได้ดังรูปที่ 1 สมมติให้มีแม่เหล็กทั้งสิ้น 10 แผ่น และศาสตราจารย์เอ็กซ์ได้สั่งให้แขนกลพลังลมพลิกแม่เหล็กนี้ทั้งสิ้น 3 ครั้ง โดยครั้งที่ 1 จะพลิกแม่เหล็กจำานวน 4 แผ่นเริ่มต้นจากแผ่นที่ 2, ครั้งที่ 2 พลิกแม่เหล็กจำานวน 5 แผ่นเริ่มต้นจากแผ่นที่ 4, และครั้งสุดท้ายพลิกแม่เหล็กเริ่มต้นจากแผ่นที่ 3 เป็นจำานวน 7 แผ่น<br />
<br />
<img alt="" /><input type="image" align="middle" longdesc="undefined" src="http://www.programming.in.th/task/img/1029/1029-1.gif" /><br />
<br />
<u><strong>งานของคุณ</strong></u><br />
หน้าที่ของคุณคือ ให้หาว่าเมื่อหยุดการทำางานของเครื่องสลายพลังแม่เหล็ก ภายหลังจากการพลิกแม่เหล็กไปมาแล้วนั้น ถ้าต้องการหยิบแม่เหล็กขึ้นมาแผ่นหนึ่งจะมีแม่เหล็กที่ติดกับมันออกมาด้วยกี่ชิ้น<br />
<br />
<u><strong>ข้อมูลนำเข้า<br />
</strong></u><strong>บรรทัดแรก</strong> รับจำานวนเต็ม 3 จำนวน คือ จำานวนแม่เหล็กทั้งหมด N (1 &lt;= N &lt;=100,000,000), จำนวนครั้ง ที่พลิก M (1 &lt;= M &lt;= 100,000) และจำานวนคำาถาม Q (1 &lt;= Q &lt;= 100,000)<br />
<strong>ต่อมาอีก M บรรทัด </strong>จะรับข้อมูลการพลิกแม่เหล็ก กล่าวคือ บรรทัดที่ 1+i จะเป็นข้อมูลการพลิกแม่เหล็กครั้งที่ i โดยแต่ละบรรทัดจะรับข้อมูลจำนวนเต็มสองจำนวน ได้แก่ ตำแหน่งเริ่มต้นของแม่เหล็กที่จะพลิก a (1 &lt;= a &lt;=N) และจำนวนชิ้นของแม่เหล็กที่พลิก k (1 &lt;= k &lt;= N) ทั้งนี้  รับประกันว่าจะไม่พลิกแม่เหล็กเกินขอบเขตที่เป็นไปได้ กล่าวคือ รับประกันว่า 1 &lt;= a+k-1 &lt;= N<br />
<strong>ต่อมาอีก Q บรรทัด </strong>จะรับข้อมูลคำถาม กล่าวคือในบรรทัดที่ 1+M+i จะรับข้อมูล คำถามที่ i โดยในแต่ละบรรทัดจะรับข้อมูลตัวเลขเพียงจำานวนเดียว x (1 &lt;= x &lt;= N) ที่แสดงถึงหมายเลขของแม่เหล็กที่ต้องการถาม<br />
<br />
<u><strong>ข้อมูลส่งออก</strong></u><br />
<strong>ให้แสดงคำตอบทั้งสิ้น Q บรรทัด</strong> โดยข้อมูลในแต่ละบรรทัดให้แสดงจำานวนของแม่เหล็กทั้งหมดที่จะถูกหยิบออกมาเมื่อคุณหยิบแม่เหล็กแผ่นที่ถาม<br />
<br />
<u><strong>ที่มา</strong></u><strong>: Young Thai Online Programming Competition 2008</strong> </span>
		<table>
			<tr>
				<th>ข้อมูลนำเข้า</th>
				<th>ข้อมูลส่งออก</th>
			</tr>	
		
			<tr>
				<td>10 3 2
<br />2 4
<br />4 5
<br />3 7
<br />7
<br />5</td>
				<td>3
<br />2</td>
			</tr></table>