1128 : รหัสลับ (cipher)
Problem type : Batch
Time limit : 1.0 second(s)
Memory limit : 32 megabyte(s)
สำนักงานถอดรหัสแห่งชาติได้ค้นพบรหัสลับจำนวน N ตัว ที่แก๊งมาเฟียใช้ในการติดต่อสื่อสารกัน ทางสำนักงานต้องการที่จะถอดรหัสนี้ให้ได้เพื่อให้ทราบถึงแผนการของแก๊งมาเฟียดังกล่าว และได้คิดค้นโปรแกรมสำหรับถอดรหัสขึ้น โปรแกรมนี้จะรับข้อมูลนำเข้าเป็นจำนวนเต็ม N แทนจำนวนของรหัส และรหัสอีก N ตัวที่เก็บในอาร์เรย์ a[0], a[1], a[2], …, a[N-1] จากนั้นโปรแกรมจะทำการคำนวณเพื่อถอดรหัสจนได้ผลลัพธ์ออกมาเป็นค่า val ซึ่งการถอดรหัสมีซูโดโค้ดดังนี้

val = 0
for i = 0 to N-1
     for j = 0 to i
          for k = 0 to j
              val += a[k]
val %= 2553
return val

สังเกตว่าในโปรแกรมมีส่วนที่เป็นลูป for ซ้อนกันถึง 3 ชั้น ทำให้โปรแกรมใช้เวลาในการทำงานนานมาก โดยเฉพาะเมื่อ N มีค่ามากๆ เช่น ถ้า N = 1,000,000 โปรแกรมจะต้องใช้เวลาในการทำงานนานถึง 11 ปี ทางสำนักงานจึงต้องการให้คุณช่วยเขียนโปรแกรมใหม่ที่ให้ผลลัพธ์เหมือนกับโปรแกรมเดิมทุกประการ แต่ต้องใช้เวลาในการทำงานไม่เกิน 1 วินาที

งานของคุณ
จงเขียนโปรแกรมสำหรับถอดรหัสที่ให้ผลลัพธ์เหมือนกับโปรแกรมเดิมทุกประการ

ข้อมูลนำเข้า
บรรทัดแรกระบุจำนวนเต็ม N (1 ≤ N ≤ 1,000,000) แทนจำนวนของรหัส

บรรทัดต่อมาระบุจำนวนเต็มทั้งหมด N จำนวน แทนรหัสแต่ละตัว จำนวนเต็มแต่ละจำนวนจะมีค่าอยู่ในช่วงตั้งแต่ 1 ถึง 1,000

ข้อมูลส่งออก
มีบรรทัดเดียว แสดงผลลัพธ์ที่ได้จากการถอดรหัส

การให้คะแนน
30% ของข้อมูลทดสอบ จะมี N ≤ 100

ที่มา

การแข่งขัน IOI Thailand League เดือนสิงหาคม 2553
โจทย์โดย: สุธี เรืองวิเศษ

ตัวอย่างข้อมูลนำเข้า ตัวอย่างข้อมูลส่งออก
4
1 4 2 3
43
5
6 12 7 6 10
280

ความช่วยเหลือ: ไม่มีคำใบ้สำหรับปัญหานี้

กำลังออนไลน์: 20 ผู้เยี่ยมชมและ 1 สมาชิก (0 บอท)