import Text.Printf (printf)
import Data.List.Split (splitOn)
invites audience =
let aux [] _ _ inv = inv
aux (p:ps) shy acc inv = aux ps (shy+1) (acc+p+more) (inv+more)
where more = max 0 (shy-acc)
in aux audience 0 0 0
test t = do
it <- getLine
let [_, ps] = splitOn " " it
printf "Case #%d: %d\n" t $ invites [read [p] :: Integer | p <- ps]
main = do
loop <- getLine
sequence_ [test t | t <- [1..read loop :: Integer]]
ส่วนข้อสามนี่สนุกดี ถ้ายังจำเนื้อหาม.ปลายได้ เราจะมีเลขมหัศจรรย์ตัวนึงเรียกว่า i ซึ่งมีนิยามที่สวยงามเรียบง่าย คือ
i^2 = -1
สังเกตเพิ่มอีกหน่อยก็จะเห็นว่า
i^4 = 1 (multiplicative identity)
โจทย์เพิ่มความสนุกโดยให้ตัวเลขมหัศจรรย์ j และ k มาด้วย ทั้งสองตัวที่เพิ่มเข้ามานี้ มีนิยามแบบเดียวกันกะ i เด๊ะๆ เลย เพียงแต่มันไม่ใช่ i เพราะเรานิยามการคูณระหว่างตัวเลขเหล่านี้ว่า
จาก X, LS ที่โจทย์ให้ การแก้ปัญหาแบบตรงๆ ก็คือวิ่งผ่านชุดตัวเลข LS เป็นจำนวน X ครั้ง โดยเลขแต่ละตัวเลข s ∈ LS ที่วิ่งผ่าน ก็จัดการคูณเก็บไว้ในใจไปเรื่อยๆ ถ้าเจอตัวเลขครบทั้ง i, j, k และหางที่เหลือคูณกันออกมาเป็น 1 ก็ตอบว่าถูกได้เลย
ถ้าวิ่งคูณหา i, j, k แต่ละตัวเกิน 4 รอบแล้วยังไม่เจอ ไม่ต้องวิ่งต่อ เพราะแต่ละรอบที่วิ่งเพิ่ม จะไม่ได้ผลลัพธ์ใหม่แล้ว
หลังจากหา i, j, k ได้ครบแล้ว หางที่เหลือสามารถ mod 4 ได้
ดังนั้น เราจะวิ่งผ่านชุดตัวเลขนี้ 3 ครั้ง (เพื่อหา i, j, k) โดยแต่ละครั้งวิ่งไม่เกิน 4 รอบ ซึ่งก็เท่ากับวิ่ง 12 รอบ แล้วรอบที่เหลือก็จับ mod 4 ได้เลย
หรือพูดจาภาษา code ก็คือ
def correct_misspelling(ijks, x):
x = min(x, 12+(x%4))
accumulate = Quaternion('+1')
searching = [Quaternion(it) for it in 'kji']
for _ in range(x):
for it in ijks:
accumulate *= Quaternion(it)
if searching and searching[-1] == accumulate:
accumulate = Quaternion('+1')
searching.pop()
return not searching and accumulate == Quaternion('+1')
for case in range(int(input())):
_, x = [int(n) for n in input().split()]
ijks = input().strip()
ans = 'YES' if correct_misspelling(ijks, x) else 'NO'
print('Case #{}: {}'.format(case+1, ans))
