23dfcca431 2011-02-23 kinaba: ///////////////////////////////////////////////////////////////////////////// 23dfcca431 2011-02-23 kinaba: // Writte in 23dfcca431 2011-02-23 kinaba: // Claire v3.3.37 23dfcca431 2011-02-23 kinaba: // http://www.claire-language.com/ 23dfcca431 2011-02-23 kinaba: ///////////////////////////////////////////////////////////////////////////// 23dfcca431 2011-02-23 kinaba: 23dfcca431 2011-02-23 kinaba: D :: 1000000000 23dfcca431 2011-02-23 kinaba: 23dfcca431 2011-02-23 kinaba: long <: ephemeral_object(hi:integer, lo:integer) 23dfcca431 2011-02-23 kinaba: 23dfcca431 2011-02-23 kinaba: [long!(x: integer) : long -> 23dfcca431 2011-02-23 kinaba: long(hi = x / D, lo = x mod D) 23dfcca431 2011-02-23 kinaba: ] 23dfcca431 2011-02-23 kinaba: 23dfcca431 2011-02-23 kinaba: [+(x:long, y:long) : long -> 23dfcca431 2011-02-23 kinaba: let lolo := x.lo - D + y.lo in 23dfcca431 2011-02-23 kinaba: ( 23dfcca431 2011-02-23 kinaba: if ( lolo < 0 ) 23dfcca431 2011-02-23 kinaba: long(hi = x.hi + y.hi, lo = lolo + D) 23dfcca431 2011-02-23 kinaba: else 23dfcca431 2011-02-23 kinaba: long(hi = x.hi + y.hi + 1, lo = lolo) 23dfcca431 2011-02-23 kinaba: ) 23dfcca431 2011-02-23 kinaba: ] 23dfcca431 2011-02-23 kinaba: 23dfcca431 2011-02-23 kinaba: [-(x:long, y:long) : long -> 23dfcca431 2011-02-23 kinaba: let lolo := x.lo - y.lo in 23dfcca431 2011-02-23 kinaba: ( 23dfcca431 2011-02-23 kinaba: if ( lolo < 0 ) 23dfcca431 2011-02-23 kinaba: long(hi = x.hi - y.hi - 1, lo = lolo + D) 23dfcca431 2011-02-23 kinaba: else 23dfcca431 2011-02-23 kinaba: long(hi = x.hi - y.hi, lo = lolo) 23dfcca431 2011-02-23 kinaba: ) 23dfcca431 2011-02-23 kinaba: ] 23dfcca431 2011-02-23 kinaba: 23dfcca431 2011-02-23 kinaba: [*(x:long, y:integer) : long -> 23dfcca431 2011-02-23 kinaba: let r := long!(0) in 23dfcca431 2011-02-23 kinaba: let c := x in 23dfcca431 2011-02-23 kinaba: (while (y > 0) ( 23dfcca431 2011-02-23 kinaba: (if (y mod 2 = 1) r :+ c), 23dfcca431 2011-02-23 kinaba: c := c + c, 23dfcca431 2011-02-23 kinaba: y :/ 2 23dfcca431 2011-02-23 kinaba: ), 23dfcca431 2011-02-23 kinaba: r) 23dfcca431 2011-02-23 kinaba: ] 23dfcca431 2011-02-23 kinaba: 23dfcca431 2011-02-23 kinaba: [+(x:long, y:integer) : long -> 23dfcca431 2011-02-23 kinaba: x + long!(y) 23dfcca431 2011-02-23 kinaba: ] 23dfcca431 2011-02-23 kinaba: 23dfcca431 2011-02-23 kinaba: [<(x:long, y:long) : boolean -> 23dfcca431 2011-02-23 kinaba: if (x.hi < y.hi) 23dfcca431 2011-02-23 kinaba: true 23dfcca431 2011-02-23 kinaba: else if (x.hi > y.hi) 23dfcca431 2011-02-23 kinaba: false 23dfcca431 2011-02-23 kinaba: else 23dfcca431 2011-02-23 kinaba: x.lo < y.lo 23dfcca431 2011-02-23 kinaba: ] 23dfcca431 2011-02-23 kinaba: [>=(x:long, y:long) : boolean -> not(x < y)] 23dfcca431 2011-02-23 kinaba: [<=(x:long, y:long) : boolean -> not(y < x)] 23dfcca431 2011-02-23 kinaba: [>(x:long, y:long) : boolean -> (y < x)] 23dfcca431 2011-02-23 kinaba: 23dfcca431 2011-02-23 kinaba: [>=(x:long, y:integer) : boolean -> not(x < long!(y))] 23dfcca431 2011-02-23 kinaba: [<=(x:long, y:integer) : boolean -> not(long!(y) < x)] 23dfcca431 2011-02-23 kinaba: [<(x:long, y:integer) : boolean -> (x < long!(y))] 23dfcca431 2011-02-23 kinaba: [>(x:long, y:integer) : boolean -> (long!(y) < x)] 23dfcca431 2011-02-23 kinaba: 23dfcca431 2011-02-23 kinaba: [>=(x:integer, y:long) : boolean -> not(long!(x) < y)] 23dfcca431 2011-02-23 kinaba: [<=(x:integer, y:long) : boolean -> not(y < long!(x))] 23dfcca431 2011-02-23 kinaba: [<(x:integer, y:long) : boolean -> (long!(x) < y)] 23dfcca431 2011-02-23 kinaba: [>(x:integer, y:long) : boolean -> (y < long!(x))] 23dfcca431 2011-02-23 kinaba: 23dfcca431 2011-02-23 kinaba: 23dfcca431 2011-02-23 kinaba: [string!(x: long) : string -> 23dfcca431 2011-02-23 kinaba: if (x.hi > 0) 23dfcca431 2011-02-23 kinaba: let los := string!(x.lo) in 23dfcca431 2011-02-23 kinaba: string!(x.hi) /+ make_string(9 - length(los), '0') /+ los 23dfcca431 2011-02-23 kinaba: else 23dfcca431 2011-02-23 kinaba: string!(x.lo) 23dfcca431 2011-02-23 kinaba: ] 23dfcca431 2011-02-23 kinaba: 23dfcca431 2011-02-23 kinaba: ///////////////////////////////////////////////////////////////////////////// 23dfcca431 2011-02-23 kinaba: 23dfcca431 2011-02-23 kinaba: [readLine() : list<integer> -> 23dfcca431 2011-02-23 kinaba: list<integer>{integer!(s) | s in explode(freadline(stdin), " ")} 23dfcca431 2011-02-23 kinaba: ] 23dfcca431 2011-02-23 kinaba: 23dfcca431 2011-02-23 kinaba: [solve(R:integer, k:integer, N:integer, g:list<integer>) -> 23dfcca431 2011-02-23 kinaba: let dest := make_list(N, 0) in 23dfcca431 2011-02-23 kinaba: let earn := make_list(N, long!(0)) in 23dfcca431 2011-02-23 kinaba: ( 23dfcca431 2011-02-23 kinaba: for s in (0 .. N - 1) ( 23dfcca431 2011-02-23 kinaba: let ride := long!(0) in 23dfcca431 2011-02-23 kinaba: let i := 0 in 23dfcca431 2011-02-23 kinaba: ( 23dfcca431 2011-02-23 kinaba: while (i < N) 23dfcca431 2011-02-23 kinaba: ( 23dfcca431 2011-02-23 kinaba: let ride2 := ride + g[((s + i) mod N) + 1] in 23dfcca431 2011-02-23 kinaba: (if (ride2 > k) 23dfcca431 2011-02-23 kinaba: break() 23dfcca431 2011-02-23 kinaba: else 23dfcca431 2011-02-23 kinaba: (ride := ride2, i :+ 1)) 23dfcca431 2011-02-23 kinaba: ), 23dfcca431 2011-02-23 kinaba: earn[s + 1] := ride, 23dfcca431 2011-02-23 kinaba: dest[s + 1] := ((s + i) mod N) + 1 23dfcca431 2011-02-23 kinaba: ) 23dfcca431 2011-02-23 kinaba: ), 23dfcca431 2011-02-23 kinaba: let firstVisitTime := make_list(N, -1) in 23dfcca431 2011-02-23 kinaba: let firstVisitEarn := make_list(N, long!(0)) in 23dfcca431 2011-02-23 kinaba: let q := 1 in 23dfcca431 2011-02-23 kinaba: let totalEarn := long!(0) in 23dfcca431 2011-02-23 kinaba: let i := 0 in 23dfcca431 2011-02-23 kinaba: ( 23dfcca431 2011-02-23 kinaba: (while (i < R) ( 23dfcca431 2011-02-23 kinaba: if (firstVisitTime[q] = -1) 23dfcca431 2011-02-23 kinaba: ( 23dfcca431 2011-02-23 kinaba: firstVisitTime[q] := i, 23dfcca431 2011-02-23 kinaba: firstVisitEarn[q] := totalEarn, 23dfcca431 2011-02-23 kinaba: totalEarn :+ earn[q], 23dfcca431 2011-02-23 kinaba: q := dest[q], 23dfcca431 2011-02-23 kinaba: i :+ 1 23dfcca431 2011-02-23 kinaba: ) 23dfcca431 2011-02-23 kinaba: else 23dfcca431 2011-02-23 kinaba: ( 23dfcca431 2011-02-23 kinaba: let loopSize := i - firstVisitTime[q] in 23dfcca431 2011-02-23 kinaba: let loopEarn := totalEarn - firstVisitEarn[q] in 23dfcca431 2011-02-23 kinaba: let rest := R - i in 23dfcca431 2011-02-23 kinaba: ( 23dfcca431 2011-02-23 kinaba: totalEarn :+ loopEarn * (rest / loopSize), 23dfcca431 2011-02-23 kinaba: // clear 23dfcca431 2011-02-23 kinaba: firstVisitTime := make_list(N, -1), 23dfcca431 2011-02-23 kinaba: i := R - (rest mod loopSize) 23dfcca431 2011-02-23 kinaba: ) 23dfcca431 2011-02-23 kinaba: ) 23dfcca431 2011-02-23 kinaba: )), 23dfcca431 2011-02-23 kinaba: princ(string!(totalEarn)) 23dfcca431 2011-02-23 kinaba: ) 23dfcca431 2011-02-23 kinaba: ) 23dfcca431 2011-02-23 kinaba: ] 23dfcca431 2011-02-23 kinaba: 23dfcca431 2011-02-23 kinaba: [main() -> 23dfcca431 2011-02-23 kinaba: let T := readLine()[1] in 23dfcca431 2011-02-23 kinaba: for C in (1 .. T) 23dfcca431 2011-02-23 kinaba: ( 23dfcca431 2011-02-23 kinaba: printf("Case #~A: ", C), 23dfcca431 2011-02-23 kinaba: let RkN := readLine() in solve(RkN[1], RkN[2], RkN[3], readLine()), 23dfcca431 2011-02-23 kinaba: princ("\n") 23dfcca431 2011-02-23 kinaba: ) 23dfcca431 2011-02-23 kinaba: ] 23dfcca431 2011-02-23 kinaba: 23dfcca431 2011-02-23 kinaba: (main())