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 行
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 行
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 行
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 行
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 行
#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 行
#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 行
// 크레이콘에는 힙이 없어서 목록으로 직접 만든다. heap[0]이 언제나 가장 긴 떡이다첫줄 = コンソール.数読み();n = 첫줄[0];k = 첫줄[1];길이들 = コンソール.数読み();heap = [];힙넣기(v){ heap.追加(v); i = heap.個数 - 1; 間 (i > 0) { 부모 = 数学.商(i - 1, 2); もし (heap[부모] >= heap[i]) { 抜ける; } t = heap[i]; heap[i] = heap[부모]; heap[부모] = t; i = 부모; }}힙빼기(){ top = heap[0]; heap[0] = heap[heap.個数 - 1]; heap.位置で取り除く(heap.個数 - 1); i = 0; 間 (真) { l = 2 * i + 1; r = l + 1; big = i; もし (l < heap.個数 && heap[l] > heap[big]) { big = l; } もし (r < heap.個数 && heap[r] > heap[big]) { big = r; } もし (big == i) { 抜ける; } t = heap[i]; heap[i] = heap[big]; heap[big] = t; i = big; } 返す top;}それぞれ (len の中 길이들){ 힙넣기(len);}out = [];繰り返す (i = 0; i < k; i++){ もし (heap[0] == 1) { 抜ける; } x = 힙빼기(); // 가장 긴 떡을 꺼낸다 a = 数学.商(x, 2); // 짧은 도막. /는 3.5 같은 소수를 내므로 몫을 구한다 b = x - a; // 긴 도막: x가 홀수면 1만큼 더 길다 out.追加(a + " " + b); 힙넣기(a); 힙넣기(b);}out.追加(heap.個数 + " " + heap[0]);コンソール.書く(out.つなぐ("\n"));