Race

#include <cassert>
#include <cstdio>
#include <iostream>
#include <vector>
 
// sum(n) = 1 + 2 + ... + n = n * (n + 1) / 2
long long sum(int n) { return 1LL * n * (n + 1) / 2; }
 
// a + (a + 1) + (a + 2) + ... + b = \sum_{i = a}^b i
long long sum(int a, int b) { return a <= b ? sum(b) - sum(a - 1) : 0; }
 
// Dado que empezamos a velocidad s, ¿podemos bajar a velocidad x en a lo sumo l
// metros? ¿Cuántos metros toma parar si la velocidad actual es s y
// el objetivo es x? (s - 1) + (s - 2) + ... + x metros. Se nos permite pasarnos, así que
// mientras tengamos (s - 1) + (s - 2) + ... + (x + 1) + 1 metros, estamos bien.
bool ok(int speed, int x, int l) {
	if (speed <= x) { return true; }
 
	long long need = sum(x + 1, speed - 1) + 1;
	return (need <= l);
}
 
int main() {
	freopen("race.in", "r", stdin);
	freopen("race.out", "w", stdout);
 
	int k, n;
	std::cin >> k >> n;
	std::vector<int> arr(n);
 
	for (int &x : arr) { std::cin >> x; }
 
	for (int i = 0; i < n; i++) {
		// Voraz. Vamos lo más rápido que podamos pero asegurándonos de poder parar a tiempo.
		int x = arr[i];
		int speed = 0;
		int left = k;
		int res = 0;
 
		while (left > 0) {
			if (ok(speed + 1, x, left - (speed + 1))) {
				// aceleramos si podemos
				speed++;
			} else if (ok(speed, x, left - speed)) {
				// si no, mantenemos la misma velocidad si podemos
			} else if (ok(speed - 1, x, left - (speed - 1))) {
				// frenamos si tenemos que
				// comprobamos que nos queda espacio suficiente para parar a tiempo.
				speed--;
			}
 
			left -= speed;
			res++;
		}
		std::cout << res << '\n';
	}
}

import java.io.*;
import java.util.*;
 
public class race {
	// S(n) = 1+2+...+n = n*(n+1)/2
	static long S(long n) { return n * (n + 1) / 2; }
	// A+(A+1)+(A+2)+...+B = \sum_{i=A}^B i
	static long sum(long A, long B) { return A <= B ? S(B) - S(A - 1) : 0; }
 
	// Dado que empezamos a velocidad S, ¿podemos bajar a velocidad X en a lo sumo L
	// metros? ¿Cuántos metros toma parar si la velocidad actual es S y
	// el objetivo es X? (S-1) + (S-2) + ... + X metros. Se nos permite pasarnos, así
	// que mientras tengamos (S-1)+(S-2)+...+(X+1)+1 m estamos bien.
	static boolean ok(long S, long X, long L) {
		if (S <= X) { return true; }
		long need = sum(X + 1, S - 1) + 1;
		return need <= L;
	}
	static long solve(long k, long x) {
		// Voraz. Vamos lo más rápido que podamos pero asegurándonos de poder parar a tiempo.
		long speed = 0;
		long left = k;
		long t = 0;
		while (left > 0) {
			if (ok(speed + 1, x, left - (speed + 1))) {
				// aceleramos si podemos
				speed += 1;
			} else if (ok(speed, x, left - speed)) {
				// si no, mantenemos la misma velocidad si podemos
			} else {
				// frenamos si tenemos que
				// comprobamos que nos queda espacio suficiente para parar a tiempo.
				assert (ok(speed - 1, x, left - (speed - 1)));
				speed -= 1;
			}
			assert (speed >= 1);
			left -= speed;
			t++;
		}
		return t;
	}
	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new FileReader("race.in"));
		PrintWriter out =
		    new PrintWriter(new BufferedWriter(new FileWriter("race.out")));
		String[] nk = in.readLine().split(" ");
		long k = Long.parseLong(nk[0]);
		int n = Integer.parseInt(nk[1]);
		for (int i = 0; i < n; i++) {
			long x = Long.parseLong(in.readLine());
			out.println(solve(k, x));
			out.flush();
		}
	}
}

# S(n) = 1+2+...+n = n*(n+1)/2
def S(n: int) -> int:
	return n * (n + 1) // 2
 
 
# A+(A+1)+(A+2)+...+B = \sum_{i=A}^B i
def sum_(A: int, B: int) -> int:
	return S(B) - S(A - 1) if A <= B else 0
 
 
# Dado que empezamos a velocidad S, ¿podemos bajar a velocidad X en a lo sumo L metros?
# ¿Cuántos metros toma parar si la velocidad actual es S y el objetivo es X?
# (S-1) + (S-2) + ... + X metros
# Se nos permite pasarnos, así que mientras tengamos (S-1)+(S-2)+...+(X+1)+1 m estamos bien.
def ok(S: int, X: int, L: int) -> bool:
	if S <= X:
		return True
	need = sum_(X + 1, S - 1) + 1
	return need <= L
 
 
line1, *rest = open("race.in").readlines()
k, n = [int(v) for v in line1.split()]
X = []
for line in rest:
	X.append(int(line))
 
 
def solve(k, x):
	# Voraz. Vamos lo más rápido que podamos pero asegurándonos de poder parar a tiempo.
	speed = 0
	left = k
	t = 0
	while left > 0:
		if ok(speed + 1, x, left - (speed + 1)):
			# aceleramos si podemos
			speed += 1
		elif ok(speed, x, left - speed):
			# si no, mantenemos la misma velocidad si podemos
			pass
		else:
			# frenamos si tenemos que
			# comprobamos que nos queda espacio suficiente para parar a tiempo.
			assert ok(speed - 1, x, left - (speed - 1))
			speed -= 1
		assert speed >= 1
		left -= speed
		t += 1
	return t
 
 
with open("race.out", "w") as fout:
	for x in X:
		print(solve(k, x), file=fout)

#include <fstream>
#include <iostream>
 
 
using std::cout;
using std::endl;
 
int fastest_time(int dist, int max_speed) {
	int speed_up_dist = 0;   // Distancia en la que Bessie está acelerando
	int slow_down_dist = 0;  // y frenando, respectivamente
	int time = 0;
 
	// Aceleramos de a poco hasta alcanzar nuestra distancia
	for (int curr_speed = 1;; curr_speed++) {
		speed_up_dist += curr_speed;
		time++;
		if (speed_up_dist + slow_down_dist >= dist) { return time; }
 
		/*
		 * Si estamos por encima del límite de velocidad, sumamos la velocidad actual
		 * también a la parte en la que frenamos.
		 */
		if (curr_speed >= max_speed) {
			slow_down_dist += curr_speed;
			time++;
			// Comprobamos de nuevo si llegamos o pasamos la línea de llegada
			if (speed_up_dist + slow_down_dist >= dist) { return time; }
		}
	}
}
 
int main() {
	std::ifstream read("race.in");
	int dist;
	int query_num;
	read >> dist >> query_num;
 
	std::ofstream written("race.out");
	for (int q = 0; q < query_num; q++) {
		int max_speed;
		read >> max_speed;
		written << fastest_time(dist, max_speed) << '\n';
	}
}

import java.io.*;
import java.util.*;
 
class Race {
	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner(new File("race.in"));
		int dist = sc.nextInt();
		int queryNum = sc.nextInt();
 
		PrintWriter pw = new PrintWriter(new File("race.out"));
		for (int q = 0; q < queryNum; q++) {
			int maxSpeed = sc.nextInt();
			pw.println(fastestTime(dist, maxSpeed));
		}
		pw.close();
	}
 
	private static int fastestTime(int dist, int maxSpeed) {
		int speedUpDist = 0;   // Distancia en la que Bessie está acelerando
		int slowDownDist = 0;  // y frenando, respectivamente
		int time = 0;
 
		// Aceleramos de a poco hasta alcanzar nuestra distancia
		for (int currSpeed = 1;; currSpeed++) {
			speedUpDist += currSpeed;
			time++;
			if (speedUpDist + slowDownDist >= dist) { return time; }
 
			/*
			 * Si estamos por encima del límite de velocidad, sumamos la velocidad actual
			 * también a la parte en la que frenamos.
			 */
			if (currSpeed >= maxSpeed) {
				slowDownDist += currSpeed;
				time++;
				// Comprobamos de nuevo si alcanzamos nuestra distancia
				if (speedUpDist + slowDownDist >= dist) { return time; }
			}
		}
	}
}

import math
 
 
def fastest_time(dist: int, max_speed: int) -> int:
	# Calculamos el tiempo que toma si solo aceleramos
	no_slow_time = int(math.ceil((math.sqrt(8 * dist + 1) - 1) / 2))
	if no_slow_time <= max_speed:
		return no_slow_time
 
	# Hay que acelerar más allá del límite, así que por ahora empezamos en la velocidad máxima
	speed_up_dist = max_speed * (max_speed - 1) // 2
	slow_down_dist = 0
	time = max_speed - 1
 
	curr_speed = max_speed
	while True:
		speed_up_dist += curr_speed
		time += 1
		if speed_up_dist + slow_down_dist >= dist:
			return time
 
		slow_down_dist += curr_speed
		time += 1
		if speed_up_dist + slow_down_dist >= dist:
			return time
 
		curr_speed += 1
 
 
with open("race.in") as read:
	dist, query_num = map(int, read.readline().split())
 
	with open("race.out", "w") as write:
		for _ in range(query_num):
			max_speed = int(read.readline())
			write.write(str(fastest_time(dist, max_speed)) + "\n")