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