結果
問題 | No.1651 Removing Cards |
ユーザー |
![]() |
提出日時 | 2021-09-01 12:49:54 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 378 ms / 2,000 ms |
コード長 | 4,178 bytes |
コンパイル時間 | 2,711 ms |
コンパイル使用メモリ | 84,232 KB |
実行使用メモリ | 62,704 KB |
最終ジャッジ日時 | 2024-11-27 13:55:17 |
合計ジャッジ時間 | 14,811 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 32 |
ソースコード
import java.io.IOException;import java.io.InputStream;import java.io.PrintWriter;import java.math.BigDecimal;import java.math.RoundingMode;import java.util.*;public class Main {static final long MOD=1000000007;static final long MOD1=998244353;static int ans=0;public static void main(String[] args){PrintWriter out = new PrintWriter(System.out);InputReader sc=new InputReader(System.in);long K = sc.nextLong();int Q = sc.nextInt();long max = 1000000000000000000l;ArrayList<Long> list = new ArrayList<>();list.add(1l);o:while (list.get(list.size()-1)<max) {long X_i = list.get(list.size()-1);long C = X_i/(K-1) + X_i;for (long i = -2; i <= 2; i++) {long X_ii = C + i;if(X_ii<=0)continue;if (X_i <= X_ii - ceil(X_ii, K)){list.add(X_ii);continue o;}}}long[] X = new long[list.size()];Arrays.setAll(X, n->list.get(n));for (int i = 0; i < Q; i++) {long N = sc.nextLong();int k = upper_bound(X, 0, X.length-1, N);out.println(X[k-1]);}out.flush();}public static int upper_bound(long[] a, int fromIndex, int toIndex, long val) {if (val >= a[toIndex])return toIndex + 1;if (val < a[fromIndex])return fromIndex;int lb = fromIndex - 1, ub = toIndex;while (ub - lb > 1) {int mid = (ub - lb)/2+lb;if (a[mid] > val) {ub = mid;} else {lb = mid;}}return ub;}static long ceil(long a,long b){return a%b==0?a/b:a/b+1;}static class InputReader {private InputStream in;private byte[] buffer = new byte[1024];private int curbuf;private int lenbuf;public InputReader(InputStream in) {this.in = in;this.curbuf = this.lenbuf = 0;}public boolean hasNextByte() {if (curbuf >= lenbuf) {curbuf = 0;try {lenbuf = in.read(buffer);} catch (IOException e) {throw new InputMismatchException();}if (lenbuf <= 0)return false;}return true;}private int readByte() {if (hasNextByte())return buffer[curbuf++];elsereturn -1;}private boolean isSpaceChar(int c) {return !(c >= 33 && c <= 126);}private void skip() {while (hasNextByte() && isSpaceChar(buffer[curbuf]))curbuf++;}public boolean hasNext() {skip();return hasNextByte();}public String next() {if (!hasNext())throw new NoSuchElementException();StringBuilder sb = new StringBuilder();int b = readByte();while (!isSpaceChar(b)) {sb.appendCodePoint(b);b = readByte();}return sb.toString();}public int nextInt() {if (!hasNext())throw new NoSuchElementException();int c = readByte();while (isSpaceChar(c))c = readByte();boolean minus = false;if (c == '-') {minus = true;c = readByte();}int res = 0;do {if (c < '0' || c > '9')throw new InputMismatchException();res = res * 10 + c - '0';c = readByte();} while (!isSpaceChar(c));return (minus) ? -res : res;}public long nextLong() {if (!hasNext())throw new NoSuchElementException();int c = readByte();while (isSpaceChar(c))c = readByte();boolean minus = false;if (c == '-') {minus = true;c = readByte();}long res = 0;do {if (c < '0' || c > '9')throw new InputMismatchException();res = res * 10 + c - '0';c = readByte();} while (!isSpaceChar(c));return (minus) ? -res : res;}public double nextDouble() {return Double.parseDouble(next());}public int[] nextIntArray(int n) {int[] a = new int[n];for (int i = 0; i < n; i++)a[i] = nextInt();return a;}public double[] nextDoubleArray(int n) {double[] a = new double[n];for (int i = 0; i < n; i++)a[i] = nextDouble();return a;}public long[] nextLongArray(int n) {long[] a = new long[n];for (int i = 0; i < n; i++)a[i] = nextLong();return a;}public char[][] nextCharMap(int n, int m) {char[][] map = new char[n][m];for (int i = 0; i < n; i++)map[i] = next().toCharArray();return map;}}}