9762번 - โรงงานลูกกวาด (Candy Factory) 다국어

โรงงานผลิตลูกกวาดแห่งหนึ่ง มีห้องส าหรับผลิตลูกกวาดอยู่ n ห้อง (โดยที่ n เป็นเลขคี่ และ 3 ≤ n ≤ 1001) ซึ่งหนึ่งห้องจะผลิตลูกกวาดได้ 1 ชนิดเท่านั้น หมายเลขห้องส าหรับการผลิต เริ่มตั้งแต่ห้องที่ 1 ถึง n โดยห้องที่ 1 จะผลิต “สุดยอดลูกกวาด” ซึ่งลูกกวาดชนิดพิเศษสุดนี้แต่ละเม็ดเกิดจากการผสมของลูกกวาดจากห้องที่ 2 จ านวน 1 เม็ดและจากห้องที่ 3 จ านวน 1 เม็ด (ซึ่งลูกกวาดแต่ละเม็ดจากห้องที่ 2 ก็เป็นส่วนผสมของลูกกวาดจากห้องที่ 4 กับห้องที่ 5 และลูกกวาดจากห้องที่ 3 ก็ผสมมาจากลูกกวาดจากห้องที่ 6 กับ ห้องที่ 7 อย่างละ 1 เม็ดด้วยเช่นกัน) กล่าวโดยสรุปคือ ลูกกวาดที่ผลิตที่ห้องที่ i จะน าส่วนผสมมาจากห้องที่ 2i กับห้องที่ 2i+1 (1 ≤ i ≤ ⌊n/2⌋) ดังนั้นสุดยอดลูกกวาดที่ผลิตที่ห้องที่ 1 จึงมีส่วนผสมของลูกกวาดทุกชนิดผสมกัน

ในการผลิตลูกกวาดที่ห้องที่ i จะผลิตเท่ากับจ านวนสูงสุดที่ห้องนั้นจะผลิตลูกกวาดได้ ซึ่งจะต้องดูจากจ านวนวัตถุดิบ ที่มาจากห้องที่ 2i กับห้องที่ 2i+1 เช่น สมมุติว่าโรงงานมีห้องผลิตลูกกวาด 3 ห้อง การที่จะผลิตสุดยอดลูกกวาดที่ ห้องที่ 1 ต้องดูว่ามีลูกกวาดที่ผลิตได้จากห้องที่ 2 และ 3 เท่าไหร่ สมมุติว่าห้องที่ 2 ผลิตได้ 5 เม็ด ห้องที่ 3 ผลิตได้ 7 เม็ด โรงงานแห่งนี้จะผลิต “สุดยอดลูกกวาด” ได้ 5 เม็ด และจะเหลือลูกกวาดจากห้องที่ 3 จ านวน 2 เม็ด ส่วน ห้องที่ 2 จะไม่เหลือลูกกวาดเลย ดังนั้นโรงงานแห่งนี้จะผลิตลูกกวาดรวมทั้งสิ้นได้ 7 เม็ด

หากทราบว่าห้องที่ ⌊n/2⌋ + 1 ถึงห้องที่ n ผลิตลูกกวาดได้ห้องละกี่เม็ด อยากทราบว่าโรงงานแห่งนี้ผลิตลูกกวาด ได้ทั้งหมดกี่เม็ด (รวมจ านวนลูกกวาดทั้งหมดที่ผลิตได้ในแต่ละห้อง โดยต้องหักวัตถุดิบจากห้องที่ 2i กับห้องที่ 2i+1 ที่ใช้เป็นส่วนผสมลูกกวาดในห้องที่ i)

บรรทัดแรกเป็นจ านวนกรณีทดสอบ ข้อมูลบรรทัดที่สองและสามเป็นข้อมูลของกรณีทดสอบที่ 1 โดยบรรทัดที่สอง เป็นจ านวนห้องผลิตลูกกวาดในโรงงานแห่งนี้(n) ข้อมูลบรรทัดที่สาม เป็นจ านวนลูกกวาดที่ผลิตได้ในห้องที่ ⌊n/2⌋ + 1 ถึงห้องที่ n ตามล าดับ (มีจ านวนทั้งสิ้น ⌊n/2⌋ + 1 ค่า) อีกทุกๆ 2 บรรทัดถัดไปเป็นข้อมูลกรณีทดสอบตัว ต่อไป

มีจ านวนบรรทัดเท่ากับจ านวนกรณีทดสอบ แต่ละบรรทัดแสดงค าตอบของกรณีทดสอบต่างๆ ว่าโรงงานผลิต ลูกกวาดได้ทั้งหมดกี่เม็ด