Artifact Content
Not logged in

Artifact 5615f7e126fc9cd7c328d1b4b021baed71df5c21


/////////////////////////////////////////////////////////////////////////////
// Writte in
//    Claire v3.3.37
//    http://www.claire-language.com/
/////////////////////////////////////////////////////////////////////////////

D :: 1000000000

long <: ephemeral_object(hi:integer, lo:integer)

[long!(x: integer) : long ->
	long(hi = x / D, lo = x mod D)
]

[+(x:long, y:long) : long ->
	let lolo := x.lo - D + y.lo in
	(
		if ( lolo < 0 )
			long(hi = x.hi + y.hi,     lo = lolo + D)
		else
			long(hi = x.hi + y.hi + 1, lo = lolo)
	)
]

[-(x:long, y:long) : long ->
	let lolo := x.lo - y.lo in
	(
		if ( lolo < 0 )
			long(hi = x.hi - y.hi - 1, lo = lolo + D)
		else
			long(hi = x.hi - y.hi,     lo = lolo)
	)
]

[*(x:long, y:integer) : long ->
	let r := long!(0) in
	let c := x in
		(while (y > 0) (
			(if (y mod 2 = 1) r :+ c),
			c := c + c,
			y :/ 2
		),
		r)
]

[+(x:long, y:integer) : long ->
	x + long!(y)
]

[<(x:long, y:long) : boolean ->
	if (x.hi < y.hi)
		true
	else if (x.hi > y.hi)
		false
	else
		x.lo < y.lo
]
[>=(x:long, y:long) : boolean -> not(x < y)]
[<=(x:long, y:long) : boolean -> not(y < x)]
[>(x:long, y:long) : boolean -> (y < x)]

[>=(x:long, y:integer) : boolean -> not(x < long!(y))]
[<=(x:long, y:integer) : boolean -> not(long!(y) < x)]
[<(x:long, y:integer) : boolean -> (x < long!(y))]
[>(x:long, y:integer) : boolean -> (long!(y) < x)]

[>=(x:integer, y:long) : boolean -> not(long!(x) < y)]
[<=(x:integer, y:long) : boolean -> not(y < long!(x))]
[<(x:integer, y:long) : boolean -> (long!(x) < y)]
[>(x:integer, y:long) : boolean -> (y < long!(x))]


[string!(x: long) : string ->
	if (x.hi > 0)
		let los := string!(x.lo) in
			string!(x.hi) /+ make_string(9 - length(los), '0') /+ los
	else
		string!(x.lo)
]

/////////////////////////////////////////////////////////////////////////////

[readLine() : list<integer> ->
	list<integer>{integer!(s) | s in explode(freadline(stdin), " ")}
]

[solve(R:integer, k:integer, N:integer, g:list<integer>) ->
	let dest := make_list(N, 0) in
	let earn := make_list(N, long!(0)) in
	(
		for s in (0 .. N - 1) (
			let ride := long!(0) in
			let i    := 0        in
			(
				while (i < N)
				(
					let ride2 := ride + g[((s + i) mod N) + 1] in
					(if (ride2 > k)
						break()
					else
						(ride := ride2, i :+ 1))
				),
				earn[s + 1] := ride,
				dest[s + 1] := ((s + i) mod N) + 1
			)
		),
		let firstVisitTime := make_list(N,       -1) in
		let firstVisitEarn := make_list(N, long!(0)) in
		let q         := 1        in
		let totalEarn := long!(0) in
		let i         := 0        in
		(
			(while (i < R) (
				if (firstVisitTime[q] = -1)
				(
					firstVisitTime[q] := i,
					firstVisitEarn[q] := totalEarn,
					totalEarn         :+ earn[q],
					q                 := dest[q],
					i                 :+ 1
				)
				else
				(
					let loopSize := i - firstVisitTime[q] in
					let loopEarn := totalEarn - firstVisitEarn[q] in
					let rest     := R - i in
					(
						totalEarn :+ loopEarn * (rest / loopSize),
						// clear
						firstVisitTime := make_list(N, -1),
						i              := R - (rest mod loopSize)
					)
				)
			)),
			princ(string!(totalEarn))
		)
	)
]

[main() ->
	let T := readLine()[1] in
		for C in (1 .. T)
		(
			printf("Case #~A: ", C),
			let RkN := readLine() in solve(RkN[1], RkN[2], RkN[3], readLine()),
			princ("\n")
		)
]

(main())