cafelier のSRM参加記録です。コンテスト中に考えてたことを執拗に全部書き残すとどうなるだろうかという試み本番中にこういうコードが書きたかったなあ、という後で書いた反省コードを書き残す試み
スパムが来たのでしばらくコメント欄をはてなユーザ限定にしています、すみません、
GCJ | |
スコア・ソース (ID は kinaba) はこちら。AC/AC/AC/RE/AC/AC : かっこわる…
using System; using System.Linq; class C { static void Main() { long[] Ts = readLongArray(); long T = Ts[0]; for(long C=1; C<=T; ++C) { long[] RkN = readLongArray(); long R = RkN[0]; long k = RkN[1]; long N = RkN[2]; long[] g = readLongArray(); Console.WriteLine("Case #{0}: {1}", C, solveSmall(R,k,N,g)); } } static long[] readLongArray() { return (from s in Console.ReadLine().Split(' ') select long.Parse(s)).ToArray(); } static long solveSmall(long R, long k, long N, long[] g) { long totalEarn = 0; for(int i=0; i<R; ++i) { long ride = 0; for(int q=0; q<g.Length; ++q) if( ride + g[q] > k ) { g = rotate(g, q); break; } else { ride += g[q]; } totalEarn += ride; } return totalEarn; } static long[] rotate(long[] g, int s) { long[] g2 = new long[g.Length]; for(int i=s; i<g.Length; ++i) g2[i-s] = g[i]; for(int i=0; i<s; ++i) g2[i+g.Length-s] = g[i]; return g2; } }
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())
Function ReadLine()
Dim s
s = Split(WScript.StdIn.ReadLine, " ")
For i = LBound(s) To UBound(s)
s(i) = CLng(s(i))
Next
ReadLine = s
End Function
Function Gcd(a, b)
If a = 0 Then
Gcd = b
Else
Gcd = Gcd(b mod a, a)
End If
End Function
Function Solve(T)
Dim g, r
g = Abs(T(1) - T(2))
For i = 2 To UBound(T)
g = Gcd(g, Abs(T(1) - T(i)))
Next
r = T(1) mod g
If r = 0 Then
Solve = 0
Else
Solve = g - r
End If
End Function
C = ReadLine()(0)
For CaseID = 1 To C
WScript.StdOut.WriteLine "Case #" & CaseID & ": " & Solve(ReadLine)
Next
global FROM_STRING = func {
arg s;
a = [];
i = 0;
loop {
a = a.append( s.substr(i,i+1).num() );
(i=i+1) >= s.length() ? return;
};
return a;
};
global TO_STRING = func {
arg x;
lexical s = "";
x.map( func{ s = s + this; } );
return s;
};
global LESS = func {
arg x;
arg y;
xl = x.length();
yl = y.length();
(xl < yl) ? return 1;
(xl > yl) ? return 0;
i = 0;
return loop {
(i == xl) ? return 0;
(x[i] < y[i]) ? return 1;
(x[i] > y[i]) ? return 0;
i = i+1;
};
};
global SUB = func {
arg x;
arg y;
x.length() > y.length() ? (y = [].resize(x.length()-y.length(),0).merge(y));
z = [].resize(x.length(), 0);
i = x.length()-1;
carry = 0;
loop {
z[i] = x[i] - y[i] - carry;
carry = z[i] < 0 ? (z[i]=z[i]+10; 1) : 0;
(i=i-1) < 0 ? return;
};
head = 0;
loop {
head == z.length()-1 ? return;
z[head] != 0 ? return;
head = head + 1;
};
return z.slice(head, z.length());
};
global DBL = func {
arg x;
z = [].resize(x.length(), 0);
i = x.length()-1;
carry = 0;
loop {
z[i] = x[i] + x[i] + carry;
carry = z[i] > 9 ? (z[i]=z[i]-10; 1) : 0;
((i=i-1) < 0) ? return;
};
return (carry==1 ? [1].merge(z) : z);
};
global DIF = func {
arg x;
arg y;
return LESS(x, y) ? SUB(y, x) : SUB(x, y);
};
global MOD = func {
arg x;
arg y;
LESS(x,y) ? return x;
z = MOD(x, DBL(y));
LESS(z,y) ? return z;
return SUB(z,y);
};
global ISZERO = func {
arg x;
return x[0] == 0;
};
global GCD = func {
arg x;
arg y;
return ISZERO(x) ? y : GCD(MOD(y,x),x);
};
#############################################################################
solve = func {
arg N;
arg t;
t = t.map( func{return FROM_STRING(this);} );
lexical t0 = t[0];
lexical g = DIF(t0, t[1]);
t.slice(2, t.length()).map(func{
g = GCD(g, DIF(t0, this));
});
r = MOD(t[0], g);
return TO_STRING( ISZERO(r) ? r : DIF(g,r) );
};
input = sys.library("streams").stdio().read(1000000000).split("\n").map(func{return this.split(" ");});
C = input[0][0].num();
CaseID = (args.length() >= 2 ? args[1].num() : 1);
loop {
"Case #".print();
CaseID.print();
": ".print();
solve( input[CaseID][0].num(), input[CaseID].slice(1,input[CaseID].length()) ).print();
"\n".print();
((CaseID = CaseID+1) > C) ? return;
};
class A
{
static function main(mc)
{
var input_string = "<paste the input data here>";
var input = input_string.split("\n");
var T = Number(input[0]);
var output_string = ""
for(var C=1; C<=T; ++C)
{
var theCase = input[C].split(" ");
var N = Number(theCase[0]);
var K = Number(theCase[1]);
output_string += "Case #" + C + ": " + (solve(N,K)?"ON":"OFF") + "\n"
}
_root.createTextField("tf",0,0,0,800,600);
_root.tf.text = output_string;
}
static function solve(N, K)
{
var mask = (1<<N) - 1;
return (K & mask) == mask;
}
}
fun solve (n : int, k : int) : bool =
let
open Word
infix 5 << andb
val mask = (0wx1 << fromInt n) - 0wx1
in
(fromInt k) andb mask = mask
end
fun main () =
let
fun readLine () =
case TextIO.inputLine TextIO.stdIn of
| NONE => []
| SOME(s) => map Int.fromString (String.tokens (fn x => x = #" ") s)
fun parseOne c =
case readLine() of
| [SOME n, SOME k] => (c, (n, k))
| _ => assert false
fun spawn solveOne (c, inp) =
(c, solve inp)
fun printOne (c, ans) =
print ("Case #" ^ Int.toString (c+1) ^ ": " ^ (if ans then "ON" else "OFF") ^ "\n")
in
case readLine () of
| [SOME t] => List.app printOne (List.map solveOne (List.tabulate (t, parseOne)))
| _ => assert false
end
do main ()
do OS.Process.exit 0
presented by
cafelier/k.inaba
under
