結果

問題 No.3557 KCPC or KUPC 2
コンテスト
ユーザー ID 21712
提出日時 2026-05-30 04:25:39
言語 Go
(1.26.1)
コンパイル:
env GOCACHE=/tmp go build _filename_
実行:
./Main
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 4,479 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 13,778 ms
コンパイル使用メモリ 284,696 KB
実行使用メモリ 7,972 KB
最終ジャッジ日時 2026-05-30 04:26:06
合計ジャッジ時間 19,238 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge3_0
純コード判定待ち
このコードへのチャレンジ
（要ログイン）
サブタスク 配点 結果
部分点1 10 % AC * 30
部分点2 40 % AC * 30
部分点3 50 % AC * 30
合計 100 点
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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))

*/
0