There are n ribbons of lengths a₁, …, aₙ. You want to cut them into at least k pieces that all have the same positive integer length L. Ribbons cannot be joined, and leftovers are thrown away (a ribbon of length a yields the quotient of a divided by L pieces). Print the largest possible L. If even L = 1 cannot give k pieces, print 0.
Input
The first line has n and k, the second line a₁ … aₙ. 1 ≤ n ≤ 10,000, 1 ≤ aᵢ ≤ 2,000,000,000, 1 ≤ k ≤ 20,000,000,000,000
Output
The largest L, or 0
Example 1 · stdin
3 4
5 5 5
stdout
2
Example 2 · stdin
2 7
3 3
stdout
0
main.py
Error List00F8 ↓ · ⇧F8 ↑
Input (stdin)
When you run, these lines are fed to input()/stdin in order (the program doesn't stop to ask).
$ Ready
Open this on a computer to write and run code. On mobile you can read the problem and the solutions.
In other languagesShow solutions by language · 8 languages
Trying L = 1, 2, 3, … can take up to 2 billion steps. Larger L gives fewer pieces, so 'are there at least k pieces?' is true at the front and false at the back, and binary search finds the boundary in 31 steps. A search function that takes the condition as a function can be reused in other problems: Python passes the function name as is, JavaScript/TypeScript use an arrow function (x: number) => boolean, Java IntPredicate with ok.test(mid), C# Func<int, bool>, C++ std::function<bool(int)> with a lambda, C a function pointer int (*ok)(int), and Craykon passes the function name as a value and calls it as ok(mid). The trap is overflow. (1) The midpoint (lo + hi) / 2: even though each length fits in int (about 2.1 billion), lo + hi reaches 4 billion and overflows in Java, C#, C and C++ — write lo + (hi - lo) / 2. JavaScript's (lo + hi) >> 1 also converts to a 32-bit integer and breaks the same way (use Math.floor). Python and Craykon do not overflow. (2) The piece count reaches 2×10¹³, so it needs long/long long. Finally, if even L = 1 is not enough the answer is 0, not 1.
Pythonmain.py · 22 lines
def last_true(lo, hi, ok): """lo..hi 에서 ok(x)가 참인 가장 큰 x. ok는 앞쪽이 참, 뒤쪽이 거짓이어야 한다. 없으면 lo - 1.""" answer = lo - 1 while lo <= hi: mid = (lo + hi) // 2 if ok(mid): answer = mid lo = mid + 1 else: hi = mid - 1 return answern, k = map(int, input().split())a = list(map(int, input().split()))def enough(length): return sum(x // length for x in a) >= kprint(last_true(1, max(a), enough))
JavaScriptmain.js · 18 lines
// lo..hi 에서 ok(x)가 참인 가장 큰 x. ok는 앞쪽이 참, 뒤쪽이 거짓이어야 한다. 없으면 lo - 1.function lastTrue(lo, hi, ok) { let answer = lo - 1; while (lo <= hi) { const mid = Math.floor((lo + hi) / 2); if (ok(mid)) { answer = mid; lo = mid + 1; } else { hi = mid - 1; } } return answer;}const [n, k, ...a] = require("fs").readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const enough = (length) => a.reduce((sum, x) => sum + Math.floor(x / length), 0) >= k;console.log(lastTrue(1, Math.max(...a), enough));
TypeScriptmain.ts · 20 lines
import { readFileSync } from "node:fs";// lo..hi 에서 ok(x)가 참인 가장 큰 x. ok는 앞쪽이 참, 뒤쪽이 거짓이어야 한다. 없으면 lo - 1.function lastTrue(lo: number, hi: number, ok: (x: number) => boolean): number { let answer = lo - 1; while (lo <= hi) { const mid = Math.floor((lo + hi) / 2); if (ok(mid)) { answer = mid; lo = mid + 1; } else { hi = mid - 1; } } return answer;}const [n, k, ...a]: number[] = readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const enough = (length: number): boolean => a.reduce((sum, x) => sum + Math.floor(x / length), 0) >= k;console.log(lastTrue(1, Math.max(...a), enough));
JavaMain.java · 42 lines
import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer;import java.util.function.IntPredicate;public class Main { // lo..hi 에서 ok(x)가 참인 가장 큰 x. 없으면 lo - 1. static int lastTrue(int lo, int hi, IntPredicate ok) { int answer = lo - 1; while (lo <= hi) { int mid = lo + (hi - lo) / 2; // (lo + hi) / 2 는 int를 넘칠 수 있다 if (ok.test(mid)) { answer = mid; lo = mid + 1; } else { hi = mid - 1; } } return answer; } public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(in.readLine()); int n = Integer.parseInt(st.nextToken()); long k = Long.parseLong(st.nextToken()); int[] a = new int[n]; int longest = 0; st = new StringTokenizer(in.readLine()); for (int i = 0; i < n; i++) { a[i] = Integer.parseInt(st.nextToken()); longest = Math.max(longest, a[i]); } IntPredicate enough = length -> { long pieces = 0; for (int x : a) pieces += x / length; return pieces >= k; }; System.out.println(lastTrue(1, longest, enough)); }}
C#Main.cs · 33 lines
using System;using System.Linq;class Program{ // lo..hi 에서 ok(x)가 참인 가장 큰 x. 없으면 lo - 1. static int LastTrue(int lo, int hi, Func<int, bool> ok) { int answer = lo - 1; while (lo <= hi) { int mid = lo + (hi - lo) / 2; // (lo + hi) / 2 는 int를 넘칠 수 있다 if (ok(mid)) { answer = mid; lo = mid + 1; } else { hi = mid - 1; } } return answer; } static void Main() { long k = long.Parse(Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries)[1]); int[] a = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries).Select(int.Parse).ToArray(); Func<int, bool> enough = length => a.Sum(x => (long)(x / length)) >= k; Console.WriteLine(LastTrue(1, a.Max(), enough)); }}
C++main.cpp · 33 lines
#include <algorithm>#include <functional>#include <iostream>#include <vector>// lo..hi 에서 ok(x)가 참인 가장 큰 x. 없으면 lo - 1.int lastTrue(int lo, int hi, const std::function<bool(int)>& ok) { int answer = lo - 1; while (lo <= hi) { int mid = lo + (hi - lo) / 2; // (lo + hi) / 2 는 int를 넘칠 수 있다 if (ok(mid)) { answer = mid; lo = mid + 1; } else { hi = mid - 1; } } return answer;}int main() { int n; long long k; std::cin >> n >> k; std::vector<int> a(n); for (int& x : a) std::cin >> x; auto enough = [&](int length) { long long pieces = 0; for (int x : a) pieces += x / length; return pieces >= k; }; std::cout << lastTrue(1, *std::max_element(a.begin(), a.end()), enough) << "\n";}
Cmain.c · 37 lines
#include <stdio.h>static int n;static long long k;static int a[10000];/* lo..hi 에서 ok(x)가 참인 가장 큰 x. 없으면 lo - 1. ok는 함수 포인터로 받는다. */static int last_true(int lo, int hi, int (*ok)(int)) { int answer = lo - 1; while (lo <= hi) { int mid = lo + (hi - lo) / 2; /* (lo + hi) / 2 는 int를 넘칠 수 있다 */ if (ok(mid)) { answer = mid; lo = mid + 1; } else { hi = mid - 1; } } return answer;}static int enough(int length) { long long pieces = 0; for (int i = 0; i < n; i++) pieces += a[i] / length; return pieces >= k;}int main(void) { int longest = 0; scanf("%d %lld", &n, &k); for (int i = 0; i < n; i++) { scanf("%d", &a[i]); if (a[i] > longest) longest = a[i]; } printf("%d\n", last_true(1, longest, enough)); return 0;}
Craykonmain.cray · 40 lines
// lo..hi 에서 ok(x)가 참인 가장 큰 x. ok는 앞쪽이 참, 뒤쪽이 거짓이어야 한다. 없으면 lo - 1.가장큰참(lo, hi, ok){ answer = lo - 1; while (lo <= hi) { mid = Mathf.Quot(lo + hi, 2); if (ok(mid)) { answer = mid; lo = mid + 1; } else { hi = mid - 1; } } return answer;}// 길이 length로 자르면 k조각 이상 나오나충분한가(length){ pieces = 0; foreach (x in a) { pieces += Mathf.Quot(x, length); } return pieces >= k;}첫줄 = Console.ReadNumbers();k = 첫줄[1];a = Console.ReadNumbers();longest = 0;foreach (x in a){ longest = Mathf.Max(longest, x);}Console.WriteLine(가장큰참(1, longest, 충분한가));