結果

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

ソースコード

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() {
        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 = 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));
            if (v >= N) {
                ok = m;
            } else {
                ng = m;
            }
        } 
        return ok;
    }
}

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;
    }

    /**
     * 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() {
// 		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=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));
// 			if (v >= N) ok=m;
// 			else ng=m;
// 		}
// 		return ok;
// 	}
// 	
// 
// 	void tr(Object... objects) {
// 		System.out.println(Arrays.deepToString(objects));
// 	}
// }
0