結果

問題 No.3557 KCPC or KUPC 2
コンテスト
ユーザー 37zigen
提出日時 2026-05-29 19:44:00
言語 Java
(openjdk 25.0.2)
コンパイル:
javac -encoding UTF8 _filename_
実行:
java -ea -Xmx700m -Xss256M -DONLINE_JUDGE=true _class_
結果
AC  
実行時間 56 ms / 2,000 ms
コード長 11,775 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,282 ms
コンパイル使用メモリ 101,612 KB
実行使用メモリ 39,524 KB
最終ジャッジ日時 2026-05-29 19:44:11
合計ジャッジ時間 9,913 ms
ジャッジサーバーID
（参考情報） 		judge1_1 / judge2_0
純コード判定待ち
このコードへのチャレンジ
（要ログイン）
サブタスク 配点 結果
部分点1 10 % AC * 30
部分点2 40 % AC * 30
部分点3 50 % AC * 30
合計 100 点
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintStream;
import java.io.PrintWriter;
import java.lang.annotation.ElementType;
import java.lang.annotation.Retention;
import java.lang.annotation.RetentionPolicy;
import java.lang.annotation.Target;
import java.math.BigInteger;
import java.nio.file.Files;
import java.nio.file.LinkOption;
import java.nio.file.OpenOption;
import java.nio.file.Path;
import java.nio.file.Paths;
import java.nio.file.attribute.FileAttribute;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.Deque;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Map.Entry;
import java.util.Map;
import java.util.NoSuchElementException;
import java.util.Optional;
import java.util.Queue;
import java.util.Random;
import java.util.Set;
import java.util.TreeMap;
import java.util.TreeSet;
import java.util.function.BiFunction;
import java.util.function.Consumer;
import java.util.function.DoubleUnaryOperator;
import java.util.function.LongToDoubleFunction;
import java.util.function.Predicate;
import java.util.function.Supplier;
import java.util.random.RandomGenerator;
import java.util.regex.Pattern;
import java.util.stream.Stream;

public class Main {
    static MyPrintWriter pw = MyPrintWriter.getInstance();

    static FastScanner sc = FastScanner.getInstance();

    public static void main(String[] args) throws IOException {
        Thread.setDefaultUncaughtExceptionHandler((t, e) -> System.exit(1));
        new Main().run();
        pw.flush();
    }

    void run() {
        // for (int a = 0; a < 3; a++) {
        // for (int b = 1; b < 3; b++) {
        // for (int c = 0; c < 3; c++) {
        // for (int m = 0; m < 10; m++) {
        // long v1=f(a, b, c, m);
        // long v2=f2(a, b, c, m);
        // if(v1!=v2) {
        // tr(v1,v2,a,b,c,m);
        // throw new AssertionError();
        // } else {
        // tr("OK");
        // }
        // }
        // }
        // }
        // }
        // 
        long N = sc.nextLong();
        long A = sc.nextLong();
        long B = sc.nextLong();
        long C = sc.nextLong();
        long D = sc.nextLong();
        long E = sc.nextLong();
        long F = sc.nextLong();
        long ans1 = solve(A, B, C, N);
        long ans2 = solve(D, E, F, N);
        if (ans1 == ans2) {
            pw.println("Same");
        } else if (ans1 < ans2) {
            pw.println("KCPC");
        } else {
            pw.println("KUPC");
        }
    }

    long solve(long a, long b, long c, long N) {
        // k日目に稼ぐお金
        // a + c * floor(k/b)
        // k日目終了までに稼ぐお金(0-indexed)
        // q=floor(k/b)として
        // a(k+1) + c *
        long ok = MathUtils.pow(10, 16);
        long ng = -1;
        while (Math.abs(ok - ng) != 1) {
            long m = (ok + ng) / 2;
            long v = f(a, b, c, m);
            if (v >= N) {
                ok = m;
            } else {
                ng = m;
            }
        } 
        return ok;
    }

    long f(long a, long b, long c, long m) {
        long v = MathUtils.saturatingMul(a, m + 1);
        long q = m / b;
        v = MathUtils.saturatingAdd(v, MathUtils.saturatingMul(MathUtils.saturatingMul(b, c), MathUtils.saturatingPow1Sum(0, q)));
        v = MathUtils.saturatingAdd(v, MathUtils.saturatingMul((m + 1) - (q * b), m / b, c));
        return v;
    }
}

class FastScanner {
    private static FastScanner instance = null;

    private final InputStream in = System.in;

    private final byte[] buffer = new byte[1 << 16];

    private int ptr = 0;

    private int buflen = 0;

    private FastScanner() {
    }

    public static FastScanner getInstance() {
        if (instance == null) {
            instance = new FastScanner();
        }
        return instance;
    }

    private boolean hasNextByte() {
        if (this.ptr < this.buflen) {
            return true;
        }
        this.ptr = 0;
        try {
            this.buflen = this.in.read(this.buffer);
        } catch (IOException e) {
            e.printStackTrace();
        }
        return this.buflen > 0;
    }

    private int readByte() {
        if (hasNextByte()) {
            return this.buffer[this.ptr++];
        } else {
            return -1;
        }
    }

    private boolean isPrintableChar(int c) {
        return (33 <= c) && (c <= 126);
    }

    public boolean hasNext() {
        while (hasNextByte() && (!isPrintableChar(this.buffer[this.ptr]))) {
            this.ptr++;
        } 
        return hasNextByte();
    }

    public long nextLong() {
        if (!hasNext()) {
            throw new NoSuchElementException();
        }
        long n = 0;
        boolean minus = false;
        int b = readByte();
        if (b == '-') {
            minus = true;
            b = readByte();
        }
        while ((b >= '0') && (b <= '9')) {
            // n = n * 10 + (b - '0');
            n = ((n << 1) + (n << 3)) + (b - '0');
            b = readByte();
        } 
        return minus ? -n : n;
    }
}

class MathUtils {
    public static long pow(long a, long n) {
        if (n == 0) {
            return 1;
        }
        return pow(a * a, n / 2) * ((n % 2) == 1 ? a : 1);
    }

    /**
     * Long.MIN_VALUEを-∞, Long.MAX_VALUEを+∞として演算
     *
     * @param a
     * @param b
     * @return  */
    public static long saturatingAdd(long a, long b) {
        // https://atcoder.jp/contests/abc303/submissions/73659954
        if ((a == Long.MAX_VALUE) && (b == Long.MIN_VALUE)) {
            throw new AssertionError();
        }
        if ((a == Long.MIN_VALUE) && (b == Long.MAX_VALUE)) {
            throw new AssertionError();
        }
        if (a == Long.MAX_VALUE) {
            return Long.MAX_VALUE;
        }
        if (b == Long.MAX_VALUE) {
            return Long.MAX_VALUE;
        }
        if (a == Long.MIN_VALUE) {
            return Long.MIN_VALUE;
        }
        if (b == Long.MIN_VALUE) {
            return Long.MIN_VALUE;
        }
        if ((a > 0) && (b > 0)) {
            // a + b <= INF
            if (a <= (Long.MAX_VALUE - b)) {
                return a + b;
            } else {
                return Long.MAX_VALUE;
            }
        } else if ((a < 0) && (b < 0)) {
            if (a >= (Long.MIN_VALUE - b)) {
                // a + b >= -INF
                // a >= -INF - b
                return a + b;
            } else {
                return Long.MIN_VALUE;
            }
        }
        return a + b;
    }

    public static long saturatingMul(long a, long b, long c) {
        return saturatingMul(saturatingMul(a, b), c);
    }

    /**
     * Long.MIN_VALUEを-∞, Long.MAX_VALUEを+∞として演算
     *
     * @param a
     * @param b
     * @return  */
    public static long saturatingMul(long a, long b) {
        // https://atcoder.jp/contests/abc303/submissions/73659954
        if ((a == 0) || (b == 0)) {
            return 0;
        }
        if ((a < 0) && (b < 0)) {
            if ((a == Long.MIN_VALUE) || (b == Long.MIN_VALUE)) {
                return Long.MAX_VALUE;
            }
            return saturatingMul(-a, -b);
        }
        if ((a > 0) && (b > 0)) {
            if (a <= (Long.MAX_VALUE / b)) {
                return a * b;
            }
            return Long.MAX_VALUE;
        }
        if ((a < 0) && (b > 0)) {
            if ((a == Long.MIN_VALUE) || (b == Long.MAX_VALUE)) {
                return Long.MIN_VALUE;
            }
            if (a >= (Long.MIN_VALUE / b)) {
                return a * b;
            }
            return Long.MIN_VALUE;
        }
        if ((a > 0) && (b < 0)) {
            if ((a == Long.MAX_VALUE) || (b == Long.MIN_VALUE)) {
                return Long.MIN_VALUE;
            }
            if (b >= (Long.MIN_VALUE / a)) {
                return a * b;
            }
            return Long.MIN_VALUE;
        }
        throw new AssertionError();
    }

    public static long saturatingPow1Sum(long start, long length) {
        // https://atcoder.jp/contests/abc303/submissions/73659954
        if (length <= 0) {
            return 0;
        }
        long a;
        long b;
        if ((length % 2) == 0) {
            a = length / 2;
            b = saturatingAdd(length - 1, saturatingMul(2, start));
        } else {
            a = length;
            b = saturatingAdd((length - 1) / 2, start);
        }
        return saturatingMul(a, b);
    }
}

class MergeFiles {}

class MyPrintWriter extends PrintWriter {
    private static MyPrintWriter instance = null;

    private MyPrintWriter() {
        super(System.out);
    }

    public static MyPrintWriter getInstance() {
        if (instance == null) {
            instance = new MyPrintWriter();
        }
        return instance;
    }
}


// --- Original Code ---
// import java.io.IOException;
// import java.util.Arrays;
// 
// import library.tools.FastScanner;
// import library.tools.MergeFiles;
// import library.tools.MyPrintWriter;
// import library.util.ArrayUtils;
// import library.util.MathUtils;
// import library.util.polynomial.PolynomialFpDynamic;
// import library.util.polynomial.PolynomialFpDynamic2D;
// import library.util.polynomial.PolynomialFpDynamic3D;
// import library.util.polynomial.PolynomialLong2D;
// import library.util.polynomial.PolynomialLong3D;
// 
// public class Main {
// 	static MyPrintWriter pw = MyPrintWriter.getInstance();
// 	static FastScanner sc = FastScanner.getInstance();
// 
// 	public static void main(String[] args) throws IOException {
// 		new Main().run();
// 		pw.flush();
// 		MergeFiles.export();
// 	}
// 
// 	void run() {
// //		for (int a = 0; a < 3; a++) {
// //			for (int b = 1; b < 3; b++) {
// //				for (int c = 0; c < 3; c++) {
// //					for (int m = 0; m < 10; m++) {
// //						long v1=f(a, b, c, m);
// //						long v2=f2(a, b, c, m);
// //						if(v1!=v2) {
// //							tr(v1,v2,a,b,c,m);
// //							throw new AssertionError();
// //						} else {
// ////							tr("OK");
// //						}
// //					}
// //				}
// //			}
// //		}
// 		//
// 		long N=sc.nextLong();
// 		long A=sc.nextLong();
// 		long B=sc.nextLong();
// 		long C=sc.nextLong();
// 		long D=sc.nextLong();
// 		long E=sc.nextLong();
// 		long F=sc.nextLong();
// 		long ans1=solve(A,B,C,N);
// 		long ans2=solve(D,E,F,N);
// 		if(ans1==ans2) {
// 			pw.println("Same");
// 		} else if (ans1<ans2) {
// 			pw.println("KCPC");
// 		} else {
// 			pw.println("KUPC");
// 		}
// 	}
// 	
// 	long solve(long a, long b, long c, long N) {
// 		//k日目に稼ぐお金
// 		//a + c * floor(k/b)
// 		
// 		//k日目終了までに稼ぐお金(0-indexed)
// 		// q=floor(k/b)として
// 		//a(k+1) + c * 
// 		
// 		long ok=MathUtils.pow(10, 16);
// 		long ng=-1;
// 		while(Math.abs(ok-ng)!=1) {
// 			long m=(ok+ng)/2;
// 			long v=f(a,b,c,m);
// 			if (v >= N) ok=m;
// 			else ng=m;
// 		}
// 		return ok;
// 	}
// 	
// 	long f(long a, long b, long c, long m) {
// 		long v=MathUtils.saturatingMul(a, m+1);
// 		long q=m/b;
// 		v=MathUtils.saturatingAdd(v, MathUtils.saturatingMul(MathUtils.saturatingMul(b, c)
// 				, MathUtils.saturatingPow1Sum(0, q)));
// 		v=MathUtils.saturatingAdd(v, MathUtils.saturatingMul((m+1-q*b), m/b, c));
// 		return v;
// 	}
// 	
// 	long f2(long a, long b, long c, long m) {
// 		long ret=0;
// 		for (int i = 0; i <= m; i++) {
// 			ret+=a+c*(i/b);
// 		}
// 		return ret;
// 	}
// 	
// 
// 	void tr(Object... objects) {
// 		System.out.println(Arrays.deepToString(objects));
// 	}
// }
0