package main import . "fmt" import . "sort" import . "math" func main() { var n,a,b,c,d,e,f int Scan(&n,&a,&b,&c,&d,&e,&f) find := func(x, y, z int) int { kmax := int(min(1e18/float64(x), 1e9*Sqrt(2*float64(y)/float64(z)))) return Search(kmax+2, func(k int) bool { s := k/y t := k%y if s > 0 && t == 0 { s-- t = y } return s * y * x + y * z * (s-1)*s/2 + t * ( x + z * s ) >= n }) } k1 := find(a, b, c) k2 := find(d, e, f) println("k1=",k1) println("k2=",k2) switch { case k1 < k2: Println("KCPC") case k1 == k2: Println("Same") case k1 > k2: Println("KUPC") } } /* 考察 WAだったので考察しなおし 夕食時でなければコンテスト中に対処したかったZE s(i) = x + z * floor( (i - 1) / y ) f(k) = Σ{i=1..k}( s(i) ) = k * x + z * Σ{i=1..k}( floor( (i - 1) / y ) ) サンプル1より、y日間同じ日給が続く y日を考える f(y) = Σ{i=1..y}( s(i) ) = s(1) + s(2) + ... + s(y) = ( x + z * floor( (1 - 1) / y ) ) + ( x + z * floor( (2 - 1) / y ) ) + ... + ( x + z * floor( (y - 1) / y ) ) = y * ( x + z * 0 ) = y * x 2*y日を考える f(2*y) = Σ{i=1..2*y}( s(i) ) = ( x + z * floor( (1 - 1) / y ) ) + ( x + z * floor( (2 - 1) / y ) ) + ... + ( x + z * floor( (y - 1) / y ) ) + ( x + z * floor( ((y+1) - 1) / y ) ) + ( x + z * floor( ((y+2) - 1) / y ) ) + ... + ( x + z * floor( (2*y - 1) / y ) ) = y * ( x + z * 0 ) + y * ( x + z * 1 ) = 2 * y * x + y * z 3*y日を考える f(3*y) = Σ{i=1..3*y}( s(i) ) = ( x + z * floor( (1 - 1) / y ) ) + ( x + z * floor( (2 - 1) / y ) ) + ... + ( x + z * floor( (y - 1) / y ) ) + ( x + z * floor( ((y+1) - 1) / y ) ) + ( x + z * floor( ((y+2) - 1) / y ) ) + ... + ( x + z * floor( ((y+y) - 1) / y ) ) + ( x + z * floor( ((2*y+1) - 1) / y ) ) + ( x + z * floor( ((2*y+2) - 1) / y ) ) + ... + ( x + z * floor( ((2*y+y) - 1) / y ) ) = y * ( x + z * 0 ) + y * ( x + z * 1 ) + y * ( x + z * 2 ) = 3 * y * x + y * z * ( 1 + 2 ) 4*y日を考える f(4*y) = Σ{i=1..4*y}( s(i) ) = ( x + z * floor( (1 - 1) / y ) ) + ( x + z * floor( (2 - 1) / y ) ) + ... + ( x + z * floor( (y - 1) / y ) ) + ( x + z * floor( ((y+1) - 1) / y ) ) + ( x + z * floor( ((y+2) - 1) / y ) ) + ... + ( x + z * floor( ((y+y) - 1) / y ) ) + ( x + z * floor( ((2*y+1) - 1) / y ) ) + ( x + z * floor( ((2*y+2) - 1) / y ) ) + ... + ( x + z * floor( ((2*y+y) - 1) / y ) ) + ( x + z * floor( (3*y+1) / y ) ) + ( x + z * floor( ((3*y+2) - 1) / y ) ) + ... + ( x + z * floor( ((3*y+y) - 1) / y ) ) = y * ( x + z * 0 ) + y * ( x + z * 1 ) + y * ( x + z * 2 ) + y * ( x + z * 3 ) = 4 * y * x + y * z * ( 1 + 2 + 3 ) k = s * y + t (0 < t <= y) と置くと ( 1-indexed相当なので t は mod y の値ではない ) f(k) = Σ{i=1..k}( s(i) ) = Σ{i=1..s*y..s*y+t}( s(i) ) = ( x + z * floor( (1 - 1) / y ) ) + ( x + z * floor( (2 - 1) / y ) ) + ... + ( x + z * floor( (y - 1) / y ) ) + ( x + z * floor( ((y+1) - 1) / y ) ) + ( x + z * floor( ((y+2) - 1) / y ) ) + ... + ( x + z * floor( ((y+y) - 1) / y ) + ( x + z * floor( ((2*y+1) - 1) / y ) ) + ( x + z * floor( ((2*y+2) - 1) / y ) ) + ... + ( x + z * floor( ((2*y+y) - 1) / y ) ) ... + ( x + z * floor( (((s-2)*y+1) - 1) / y ) ) + ( x + z * floor( (((s-2)*y+2) - 1) / y ) ) + ... + ( x + z * floor( (((s-2)*y+y) - 1) / y ) ) + ( x + z * floor( (((s-1)*y+1) - 1) / y ) ) + ( x + z * floor( (((s-1)*y+2) - 1) / y ) ) + ... + ( x + z * floor( (((s-1)*y+y) - 1) / y ) ) + ( x + z * floor( ((s*y+1) - 1) / y ) ) + ( x + z * floor( ((s*y+2) - 1) / y ) ) + ... + ( x + z * floor( ((s*y+t) - 1) / y ) ) = y * ( x + z * 0 ) + y * ( x + z * 1 ) + y * ( x + z * 2 ) + ... + y * ( x + z * (s-2) ) + y * ( x + z * (s-1) ) + t * ( x + z * s ) = s * y * x + y * z * ( 1 + 2 + ... + (s-2) +(s-1) ) + t * ( x + z * s ) = s * y * x + y * z * (s-1)*s/2 + t * ( x + z * s ) まぁ、ひとまずこれで二分探索してN以上になるkを求めればいいか 算術オーバーフローに気を付ける必要があるかも k = s * y + t < 1e18 s * y * x = (k - t) * x < k * x < 1e18 y * z * (s-1)*s/2 = (k - t) * z * (s-1)/2 < k * z * (s-1)/2 < k * z * s/2 = k * z * (k - t)/y/2 < k*k*z/y/2 < 1e18 1e18で抑えるのが妥当か不明だが k < 1e18/x k*k < 2e18*y/z k < 1e9*sqrt(2*y/z) k < min(1e18/x, 1e9*sqrt(2*y/z)) */