A mill has n sticks of rice cake, and the length of each is given as an integer.
The owner wants to cut k times.
For each cut, the owner picks one of the longest sticks there are now and splits it into two pieces. If several sticks are the longest, any of them may be picked.
A stick of length x is split into a piece whose length is the quotient of x divided by 2, and a piece with the rest of the length. So if x is even the two pieces are equally long, and if x is odd one piece is longer by 1.
The two pieces go back to the pile, and at the next cut their lengths are compared just like those of the other sticks.
If the longest stick has length 1, it cannot be cut any more, so the owner stops there even if cuts remain.
For each cut, print on one line the lengths of the two pieces, shorter first, separated by one space.
On the last line print the number of sticks when everything is over and the length of the longest stick, separated by one space.
Input
The first line has n and k separated by one space. The second line has the n lengths separated by single spaces. 1 ≤ n ≤ 1,000, 1 ≤ k ≤ 1,000, and each length is an integer from 1 to 1,000
Output
One line per cut made with the lengths of the two pieces, shorter first, then a last line with the number of sticks and the length of the longest stick
Example 1 · stdin
3 4
7 4 1
stdout
3 4
2 2
2 2
1 2
7 2
Example 2 · stdin
2 5
2 1
stdout
1 1
3 1
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
The tool that fits 'take out the longest, put new values back in' over and over is a heap (priority queue). But which end comes out first differs by language. Trap one: Python heapq, Java PriorityQueue and C# PriorityQueue<element, priority> give the smallest first. Used as they are, they take out the shortest stick: in example 1 the program sees length 1 and stops at once, printing only the line 3 1, and example 2 becomes 2 1. In Python push -x and flip the sign again when you take it out; in Java write new PriorityQueue<>(Collections.reverseOrder()); in C# write Enqueue(x, -x). Only C++ priority_queue<int> gives the largest first, so it is used as it is. JS, TS, C and Craykon have no heap, so you build one on an array: the parent is at (i - 1) / 2, and the two children are at 2 * i + 1 and 2 * i + 2. Trap two: in C++ top() only looks and pop() returns nothing. If you leave out pop(), the stick you cut stays in the pile, and example 1 prints 3 4 four times and ends with 11 7. Python heappop, Java poll and C# Dequeue return the value as they remove it. Trap three: if you make both pieces x / 2, then for an odd length the 1 thrown away by integer division disappears from the rice cake. The first line of example 1 becomes 3 3. Get the longer piece as x - quotient. In JS, TS and Craykon / goes the other way and gives a decimal, printing 3.5 3.5, so write Math.floor(x / 2) and Mathf.Quot(x, 2); in Python use //. Trap four: if you do not ask whether the longest stick is 1, a stick of length 1 gets cut into 0 and 1. Example 2 prints 1 1, then 0 1 four times, and ends with 7 1. In this problem there are at most 2,000 sticks, so even searching the whole list for the largest value every time finishes in time. A heap does that one step with about twenty comparisons at this size instead of one per stick. Measured with 200,000 sticks and 200,000 cuts, scanning the whole list every time took tens of seconds or more in C, while the heap finished within 0.1 seconds.
Pythonmain.py · 21 lines
import sysimport heapqdata = sys.stdin.read().split()n, k = int(data[0]), int(data[1])# heapq는 가장 작은 값이 먼저 나온다. 가장 긴 떡이 먼저 나오도록 부호를 뒤집어 넣는다heap = [-int(x) for x in data[2:2 + n]]heapq.heapify(heap)out = []for _ in range(k): if -heap[0] == 1: # 가장 긴 떡이 1이면 더 썰 수 없다 break x = -heapq.heappop(heap) # 가장 긴 떡을 꺼낸다 a = x // 2 # 짧은 도막 b = x - a # 긴 도막: x가 홀수면 1만큼 더 길다 out.append(f"{a} {b}") heapq.heappush(heap, -a) heapq.heappush(heap, -b)out.append(f"{len(heap)} {-heap[0]}")print("\n".join(out))
JavaScriptmain.js · 52 lines
const data = require("fs").readFileSync(0, "utf8").split(/\s+/).filter((s) => s !== "").map(Number);const n = data[0];const k = data[1];// JS에는 힙이 없어서 배열로 직접 만든다. heap[0]이 언제나 가장 긴 떡이다const heap = [];function push(v) { heap.push(v); let i = heap.length - 1; while (i > 0) { const parent = (i - 1) >> 1; if (heap[parent] >= heap[i]) break; [heap[i], heap[parent]] = [heap[parent], heap[i]]; i = parent; }}function pop() { const top = heap[0]; const last = heap.pop(); if (heap.length > 0) { heap[0] = last; let i = 0; while (true) { const l = 2 * i + 1; const r = l + 1; let big = i; if (l < heap.length && heap[l] > heap[big]) big = l; if (r < heap.length && heap[r] > heap[big]) big = r; if (big === i) break; [heap[i], heap[big]] = [heap[big], heap[i]]; i = big; } } return top;}for (let i = 0; i < n; i++) push(data[2 + i]);const out = [];for (let i = 0; i < k; i++) { if (heap[0] === 1) break; // 가장 긴 떡이 1이면 더 썰 수 없다 const x = pop(); // 가장 긴 떡을 꺼낸다 const a = Math.floor(x / 2); // 짧은 도막. JS의 /는 3.5 같은 소수를 내므로 내림한다 const b = x - a; // 긴 도막: x가 홀수면 1만큼 더 길다 out.push(`${a} ${b}`); push(a); push(b);}out.push(`${heap.length} ${heap[0]}`);console.log(out.join("\n"));
TypeScriptmain.ts · 54 lines
import { readFileSync } from "node:fs";const data: number[] = readFileSync(0, "utf8").split(/\s+/).filter((s: string): boolean => s !== "").map(Number);const n: number = data[0];const k: number = data[1];// TS에도 힙이 없어서 배열로 직접 만든다. heap[0]이 언제나 가장 긴 떡이다const heap: number[] = [];function push(v: number): void { heap.push(v); let i = heap.length - 1; while (i > 0) { const parent = (i - 1) >> 1; if (heap[parent] >= heap[i]) break; [heap[i], heap[parent]] = [heap[parent], heap[i]]; i = parent; }}function pop(): number { const top: number = heap[0]; const last = heap.pop() as number; if (heap.length > 0) { heap[0] = last; let i = 0; while (true) { const l = 2 * i + 1; const r = l + 1; let big = i; if (l < heap.length && heap[l] > heap[big]) big = l; if (r < heap.length && heap[r] > heap[big]) big = r; if (big === i) break; [heap[i], heap[big]] = [heap[big], heap[i]]; i = big; } } return top;}for (let i = 0; i < n; i++) push(data[2 + i]);const out: string[] = [];for (let i = 0; i < k; i++) { if (heap[0] === 1) break; // 가장 긴 떡이 1이면 더 썰 수 없다 const x: number = pop(); // 가장 긴 떡을 꺼낸다 const a: number = Math.floor(x / 2); // 짧은 도막. /는 3.5 같은 소수를 내므로 내림한다 const b: number = x - a; // 긴 도막: x가 홀수면 1만큼 더 길다 out.push(`${a} ${b}`); push(a); push(b);}out.push(`${heap.length} ${heap[0]}`);console.log(out.join("\n"));
JavaMain.java · 34 lines
import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Collections;import java.util.PriorityQueue;import java.util.StringTokenizer;public class Main { 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()); int k = Integer.parseInt(st.nextToken()); // PriorityQueue는 가장 작은 값이 먼저 나온다. reverseOrder()를 넘겨 가장 긴 떡이 먼저 나오게 한다 PriorityQueue<Integer> heap = new PriorityQueue<>(Collections.reverseOrder()); st = new StringTokenizer(in.readLine()); for (int i = 0; i < n; i++) { heap.add(Integer.parseInt(st.nextToken())); } StringBuilder out = new StringBuilder(); for (int i = 0; i < k; i++) { if (heap.peek() == 1) break; // 가장 긴 떡이 1이면 더 썰 수 없다 int x = heap.poll(); // 가장 긴 떡을 꺼낸다 int a = x / 2; // 짧은 도막 int b = x - a; // 긴 도막: x가 홀수면 1만큼 더 길다 out.append(a).append(' ').append(b).append('\n'); heap.add(a); heap.add(b); } out.append(heap.size()).append(' ').append(heap.peek()); System.out.println(out); }}
C#Main.cs · 36 lines
using System;using System.Collections.Generic;using System.Text;class Program{ static void Main() { string[] first = Console.ReadLine().Trim().Split(' '); int n = int.Parse(first[0]); int k = int.Parse(first[1]); string[] parts = Console.ReadLine().Trim().Split(' '); // PriorityQueue<값, 우선순위>는 우선순위가 가장 작은 것이 먼저 나온다. // 우선순위를 -길이로 주어 가장 긴 떡이 먼저 나오게 한다 var heap = new PriorityQueue<int, int>(); for (int i = 0; i < n; i++) { int len = int.Parse(parts[i]); heap.Enqueue(len, -len); } var sb = new StringBuilder(); for (int i = 0; i < k; i++) { if (heap.Peek() == 1) break; // 가장 긴 떡이 1이면 더 썰 수 없다 int x = heap.Dequeue(); // 가장 긴 떡을 꺼낸다 int a = x / 2; // 짧은 도막 int b = x - a; // 긴 도막: x가 홀수면 1만큼 더 길다 sb.Append(a).Append(' ').Append(b).Append('\n'); heap.Enqueue(a, -a); heap.Enqueue(b, -b); } sb.Append(heap.Count).Append(' ').Append(heap.Peek()); Console.WriteLine(sb); }}
C++main.cpp · 28 lines
#include <iostream>#include <queue>using namespace std;int main() { int n, k; cin >> n >> k; // priority_queue는 다른 언어와 달리 가장 큰 값이 먼저 나온다. 그대로 쓰면 된다 priority_queue<int> heap; for (int i = 0; i < n; i++) { int len; cin >> len; heap.push(len); } for (int i = 0; i < k; i++) { if (heap.top() == 1) break; // 가장 긴 떡이 1이면 더 썰 수 없다 int x = heap.top(); // top()은 보기만 한다 heap.pop(); // 꺼내는 것은 pop()이고, 값을 돌려주지 않는다 int a = x / 2; // 짧은 도막 int b = x - a; // 긴 도막: x가 홀수면 1만큼 더 길다 cout << a << ' ' << b << '\n'; heap.push(a); heap.push(b); } cout << heap.size() << ' ' << heap.top() << '\n'; return 0;}
Cmain.c · 53 lines
#include <stdio.h>/* C에는 힙이 없어서 배열로 직접 만든다. heap[0]이 언제나 가장 긴 떡이다 */static int heap[2000]; /* 처음 1,000개 + 썰 때마다 하나씩 늘어 1,000개 */static int size = 0;static void push(int v) { int i = size++; heap[i] = v; while (i > 0) { int parent = (i - 1) / 2; if (heap[parent] >= heap[i]) break; int t = heap[i]; heap[i] = heap[parent]; heap[parent] = t; i = parent; }}static int pop(void) { int top = heap[0]; heap[0] = heap[--size]; int i = 0; for (;;) { int l = 2 * i + 1, r = l + 1, big = i; if (l < size && heap[l] > heap[big]) big = l; if (r < size && heap[r] > heap[big]) big = r; if (big == i) break; int t = heap[i]; heap[i] = heap[big]; heap[big] = t; i = big; } return top;}int main(void) { int n, k; scanf("%d %d", &n, &k); for (int i = 0; i < n; i++) { int len; scanf("%d", &len); push(len); } for (int i = 0; i < k; i++) { if (heap[0] == 1) break; /* 가장 긴 떡이 1이면 더 썰 수 없다 */ int x = pop(); /* 가장 긴 떡을 꺼낸다 */ int a = x / 2; /* 짧은 도막 */ int b = x - a; /* 긴 도막: x가 홀수면 1만큼 더 길다 */ printf("%d %d\n", a, b); push(a); push(b); } printf("%d %d\n", size, heap[0]); return 0;}
Craykonmain.cray · 77 lines
// 크레이콘에는 힙이 없어서 목록으로 직접 만든다. heap[0]이 언제나 가장 긴 떡이다첫줄 = Console.ReadNumbers();n = 첫줄[0];k = 첫줄[1];길이들 = Console.ReadNumbers();heap = [];힙넣기(v){ heap.Add(v); i = heap.Count - 1; while (i > 0) { 부모 = Mathf.Quot(i - 1, 2); if (heap[부모] >= heap[i]) { break; } t = heap[i]; heap[i] = heap[부모]; heap[부모] = t; i = 부모; }}힙빼기(){ top = heap[0]; heap[0] = heap[heap.Count - 1]; heap.RemoveAt(heap.Count - 1); i = 0; while (true) { l = 2 * i + 1; r = l + 1; big = i; if (l < heap.Count && heap[l] > heap[big]) { big = l; } if (r < heap.Count && heap[r] > heap[big]) { big = r; } if (big == i) { break; } t = heap[i]; heap[i] = heap[big]; heap[big] = t; i = big; } return top;}foreach (len in 길이들){ 힙넣기(len);}out = [];for (i = 0; i < k; i++){ if (heap[0] == 1) { break; } x = 힙빼기(); // 가장 긴 떡을 꺼낸다 a = Mathf.Quot(x, 2); // 짧은 도막. /는 3.5 같은 소수를 내므로 몫을 구한다 b = x - a; // 긴 도막: x가 홀수면 1만큼 더 길다 out.Add(a + " " + b); 힙넣기(a); 힙넣기(b);}out.Add(heap.Count + " " + heap[0]);Console.WriteLine(out.Join("\n"));