宅配の箱を届いた順にトラックに積む。 トラック一台には重さの合計が C になるまで積める。 箱ごとに伝票番号、行き先、重さがある。 箱が届いたら、次の規則でトラックを選ぶ。 - まだ出発していないトラックのうち、行き先がこの箱と同じで、この箱を積んでも重さの合計が C 以下のトラックを探す。 - そのようなトラックが複数あれば、番号がいちばん小さいトラックに積む。 残りの空きがいちばん大きい・小さいトラックではない。 - そのようなトラックがなければ、新しいトラックを一台呼んで積む。 トラックの番号は呼ばれた順に 1, 2, 3, … で、新しいトラックの行き先はこの箱の行き先である。 - 箱を積んだあと、そのトラックの重さの合計がちょうど C になったら、トラックはすぐに出発する。 出発したトラックにはもう積まない。 すべての箱を積んだあと、まだ出発していないトラックは番号順に出発する。 一行目に C と箱の数 n、続く n 行に「伝票番号 行き先 重さ」が空白一つで区切られて、届いた順に与えられる。 一行目にトラックの台数を出力せよ。 続いて出発した順に、トラックごとに一行で「番号 行き先 重さの合計 箱の数」と、そのトラックに積んだ伝票番号を積んだ順に、すべて空白一つで区切って出力せよ。 箱一つとトラック一台をそれぞれレコード（構造体）にまとめ、トラックのレコードのリストを扱ってみよう。
入力
1 ≤ n ≤ 1,000、1 ≤ C ≤ 1,000,000、1 ≤ 重さ ≤ C（整数）。 伝票番号は英大文字と数字からなる 1～8 文字で、互いに異なる。 行き先は英小文字 1～10 文字。
出力
トラックの台数を一行、続いてトラックごとに一行
例 1 · stdin
10 7
P1 seoul 6
P2 busan 4
P3 seoul 5
P4 busan 6
P5 seoul 4
P6 seoul 3
P7 seoul 5
stdout
4
2 busan 10 2 P2 P4
1 seoul 10 2 P1 P5
3 seoul 8 2 P3 P6
4 seoul 5 1 P7
main.py
エラー一覧00F8 ↓ · ⇧F8 ↑
入力(stdin)
実行すると、これらの行が順に input()・標準入力に渡されます(実行中に入力を求めません)。
$ 準備完了
コードを入力して解くにはパソコンで開いてください。モバイルでは問題と解答を見られます。
ほかの言語では？言語別の解答を見る · 8 言語の解答
トラック一台（番号、行き先、重さの合計、伝票のリスト）をまとめる方法：Python @dataclass（リストのフィールドは field(default_factory=list)）、Java はフィールドを変えられる class（record はフィールドを変えられません）、C# class、C・C++ struct、JS・TS のオブジェクト { no, dest, load, codes: [] }（TS は interface Truck で形を書きます）。 Craykon にはクラスがないので、トラックごとに 辞書() を一つ（t["load"]、t["codes"]）作って waiting.追加(t) でリストに入れます。 肝心なのは選んだトラックを書き換えるときです。 Python・JS・TS・Java・C# の class・Craykon の辞書では、リストから取り出した値が同じトラックを指すので、truck.load += w がリストの中のトラックを変えます。 C は Truck *t = &trucks[k] のようにポインタで、C++ は Truck &t = trucks[k] のように参照で持つ必要があり、C++ の vector は大きくなるときに要素を移すので持っていた参照が壊れます。 reserve しておくか、位置でもう一度探します。 出発したトラックは待っているトラックのリストから外します：Python remove、JS・TS splice、Java・C# Remove、Craykon 位置で取り除く。 落とし穴は五つ：① load + w < C と書くと、ちょうど C になるトラックを選べず新しいトラックを呼んでしまいます。 ② Python で def __init__(self, no, dest, codes=[]) のように既定値を [] にすると、その一つのリストを全トラックが共有して伝票番号が混ざります（@dataclass はこういう既定値をはじめから拒みます）。 ③ C# でトラックを struct にすると Truck truck = waiting[at]; はコピーなので、Load を変えてもリストの中はそのままです（C の Truck t = trucks[k]; も同じ）。 ④ トラックの番号順に出力すると間違いです。 満杯になって先に出発したトラックが先です。 ⑤ 行き先が同じ最後のトラック一台だけを見る（next-fit）と、前のトラックに残った空きを見落とします。
Pythonmain.py · 38 行
import sysfrom dataclasses import dataclass, field@dataclassclass Truck: no: int dest: str load: int = 0 codes: list[str] = field(default_factory=list) # 트럭마다 새 목록def main(): data = sys.stdin.read().split() cap, n = int(data[0]), int(data[1]) trucks = 0 waiting: list[Truck] = [] # 아직 떠나지 않은 트럭(번호 순) departed: list[Truck] = [] # 떠난 차례 for i in range(n): code, dest, w = data[2 + 3 * i], data[3 + 3 * i], int(data[4 + 3 * i]) truck = next((t for t in waiting if t.dest == dest and t.load + w <= cap), None) if truck is None: trucks += 1 truck = Truck(trucks, dest) waiting.append(truck) truck.load += w truck.codes.append(code) if truck.load == cap: # 꽉 차면 곧바로 떠난다 waiting.remove(truck) departed.append(truck) departed.extend(waiting) # 남은 트럭은 번호 순으로 out = [str(len(departed))] for t in departed: out.append(f"{t.no} {t.dest} {t.load} {len(t.codes)} " + " ".join(t.codes)) print("\n".join(out))main()
JavaScriptmain.js · 27 行
const data = require("fs").readFileSync(0, "utf8").trim().split(/\s+/);const cap = Number(data[0]);const n = Number(data[1]);let count = 0;const waiting = []; // 아직 떠나지 않은 트럭(번호 순)const departed = []; // 떠난 차례for (let i = 0; i < n; i++) { const code = data[2 + 3 * i]; const dest = data[3 + 3 * i]; const w = Number(data[4 + 3 * i]); let truck = waiting.find((t) => t.dest === dest && t.load + w <= cap); if (truck === undefined) { count++; truck = { no: count, dest, load: 0, codes: [] }; // 트럭마다 새 객체·새 배열 waiting.push(truck); } truck.load += w; truck.codes.push(code); if (truck.load === cap) { waiting.splice(waiting.indexOf(truck), 1); departed.push(truck); }}departed.push(...waiting);const out = [String(departed.length)];for (const t of departed) out.push(`${t.no} ${t.dest} ${t.load} ${t.codes.length} ${t.codes.join(" ")}`);console.log(out.join("\n"));
TypeScriptmain.ts · 34 行
interface Truck { no: number; dest: string; load: number; codes: string[];}const data: string[] = require("fs").readFileSync(0, "utf8").trim().split(/\s+/);const cap = Number(data[0]);const n = Number(data[1]);let count = 0;const waiting: Truck[] = []; // 아직 떠나지 않은 트럭(번호 순)const departed: Truck[] = []; // 떠난 차례for (let i = 0; i < n; i++) { const code = data[2 + 3 * i]; const dest = data[3 + 3 * i]; const w = Number(data[4 + 3 * i]); let truck: Truck | undefined = waiting.find((t) => t.dest === dest && t.load + w <= cap); if (truck === undefined) { count++; truck = { no: count, dest, load: 0, codes: [] }; waiting.push(truck); } truck.load += w; truck.codes.push(code); if (truck.load === cap) { waiting.splice(waiting.indexOf(truck), 1); departed.push(truck); }}departed.push(...waiting);const out: string[] = [String(departed.length)];for (const t of departed) out.push(`${t.no} ${t.dest} ${t.load} ${t.codes.length} ${t.codes.join(" ")}`);console.log(out.join("\n"));
JavaMain.java · 59 行
import java.io.*;import java.util.*;public class Main { // 트럭 하나: 실은 상자가 늘어나니 record가 아니라 필드를 바꿀 수 있는 클래스 static class Truck { final int no; final String dest; int load = 0; final List<String> codes = new ArrayList<>(); Truck(int no, String dest) { this.no = no; this.dest = dest; } } public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); int cap = Integer.parseInt(st.nextToken()); int n = Integer.parseInt(st.nextToken()); int count = 0; List<Truck> waiting = new ArrayList<>(); List<Truck> departed = new ArrayList<>(); for (int i = 0; i < n; i++) { st = new StringTokenizer(br.readLine()); String code = st.nextToken(); String dest = st.nextToken(); int w = Integer.parseInt(st.nextToken()); Truck truck = null; for (Truck t : waiting) { if (t.dest.equals(dest) && t.load + w <= cap) { truck = t; break; } } if (truck == null) { truck = new Truck(++count, dest); waiting.add(truck); } truck.load += w; truck.codes.add(code); if (truck.load == cap) { waiting.remove(truck); departed.add(truck); } } departed.addAll(waiting); StringBuilder sb = new StringBuilder(); sb.append(departed.size()).append('\n'); for (Truck t : departed) { sb.append(t.no).append(' ').append(t.dest).append(' ').append(t.load).append(' ').append(t.codes.size()); for (String c : t.codes) sb.append(' ').append(c); sb.append('\n'); } System.out.print(sb); }}
C#Main.cs · 56 行
using System;using System.Collections.Generic;using System.Text;// class라서 목록에서 꺼낸 t는 같은 트럭을 가리킨다(struct였다면 복사본)class Truck{ public int No; public string Dest; public int Load; public List<string> Codes = new List<string>(); public Truck(int no, string dest) { No = no; Dest = dest; }}class Program{ static void Main() { var data = Console.In.ReadToEnd().Split((char[])null, StringSplitOptions.RemoveEmptyEntries); int cap = int.Parse(data[0]); int n = int.Parse(data[1]); int count = 0; var waiting = new List<Truck>(); var departed = new List<Truck>(); for (int i = 0; i < n; i++) { string code = data[2 + 3 * i]; string dest = data[3 + 3 * i]; int w = int.Parse(data[4 + 3 * i]); Truck truck = waiting.Find(t => t.Dest == dest && t.Load + w <= cap); if (truck == null) { truck = new Truck(++count, dest); waiting.Add(truck); } truck.Load += w; truck.Codes.Add(code); if (truck.Load == cap) { waiting.Remove(truck); departed.Add(truck); } } departed.AddRange(waiting); var sb = new StringBuilder(); sb.Append(departed.Count).Append('\n'); foreach (var t in departed) sb.Append($"{t.No} {t.Dest} {t.Load} {t.Codes.Count} {string.Join(" ", t.Codes)}\n"); Console.Write(sb); }}
C++main.cpp · 57 行
#include <iostream>#include <string>#include <vector>struct Truck { int no; std::string dest; int load = 0; std::vector<std::string> codes;};int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int cap, n; std::cin >> cap >> n; std::vector<Truck> trucks; trucks.reserve(n); // 상자마다 많아야 한 대: 자리를 미리 잡아 옮겨지지 않게 std::vector<int> waiting; // 아직 떠나지 않은 트럭의 자리(번호 순) std::vector<int> departed; // 떠난 차례 for (int i = 0; i < n; i++) { std::string code, dest; int w; std::cin >> code >> dest >> w; int pick = -1, at = -1; for (int k = 0; k < (int)waiting.size(); k++) { const Truck &t = trucks[waiting[k]]; if (t.dest == dest && t.load + w <= cap) { pick = waiting[k]; at = k; break; } } if (pick < 0) { trucks.push_back(Truck{(int)trucks.size() + 1, dest}); pick = (int)trucks.size() - 1; waiting.push_back(pick); at = (int)waiting.size() - 1; } Truck &t = trucks[pick]; // 참조라서 목록 안의 트럭이 바뀐다 t.load += w; t.codes.push_back(code); if (t.load == cap) { waiting.erase(waiting.begin() + at); departed.push_back(pick); } } departed.insert(departed.end(), waiting.begin(), waiting.end()); std::cout << departed.size() << '\n'; for (int k : departed) { const Truck &t = trucks[k]; std::cout << t.no << ' ' << t.dest << ' ' << t.load << ' ' << t.codes.size(); for (const auto &c : t.codes) std::cout << ' ' << c; std::cout << '\n'; } return 0;}
Cmain.c · 69 行
#include <stdio.h>#include <string.h>#define MAXN 1000typedef struct { char code[9]; char dest[11]; int w; int next; /* 같은 트럭에 다음으로 실린 상자(없으면 -1) */} Parcel;typedef struct { int no; char dest[11]; int load; int count; int first, last; /* 실은 상자들의 첫·마지막 번호 */ int gone; /* 떠났으면 1 */} Truck;static Parcel parcels[MAXN];static Truck trucks[MAXN]; /* 상자마다 많아야 한 대 새로 생긴다 */static int order[MAXN]; /* 떠난 차례 */int main(void) { int cap, n, nt = 0, nd = 0; scanf("%d %d", &cap, &n); for (int i = 0; i < n; i++) { Parcel *p = &parcels[i]; scanf("%8s %10s %d", p->code, p->dest, &p->w); p->next = -1; Truck *t = NULL; /* 고른 트럭을 포인터로 쥐어야 목록 안의 트럭이 바뀐다 */ for (int k = 0; k < nt; k++) { if (!trucks[k].gone && strcmp(trucks[k].dest, p->dest) == 0 && trucks[k].load + p->w <= cap) { t = &trucks[k]; break; } } if (t == NULL) { t = &trucks[nt]; t->no = ++nt; strcpy(t->dest, p->dest); t->load = 0; t->count = 0; t->first = -1; t->gone = 0; } t->load += p->w; t->count++; if (t->first < 0) t->first = i; else parcels[t->last].next = i; t->last = i; if (t->load == cap) { t->gone = 1; order[nd++] = t->no - 1; } } for (int k = 0; k < nt; k++) if (!trucks[k].gone) order[nd++] = k; printf("%d\n", nd); for (int j = 0; j < nd; j++) { const Truck *t = &trucks[order[j]]; printf("%d %s %d %d", t->no, t->dest, t->load, t->count); for (int i = t->first; i >= 0; i = parcels[i].next) printf(" %s", parcels[i].code); printf("\n"); } return 0;}
Craykonmain.cray · 51 行
// 크레이콘에는 클래스가 없어서 트럭 한 대를 사전 하나로 묶는다(no, dest, load, codes)첫줄 = コンソール.数読み();cap = 첫줄[0];n = 첫줄[1];count = 0;waiting = []; // 아직 떠나지 않은 트럭(번호 순)departed = []; // 떠난 차례繰り返す (i = 0; i < n; i++){ p = コンソール.行読み().空白除去().分ける(" "); code = p[0]; dest = p[1]; w = p[2].数に(); at = -1; 繰り返す (k = 0; k < waiting.個数; k++) { もし (waiting[k]["dest"] == dest && waiting[k]["load"] + w <= cap) { at = k; 抜ける; } } もし (at < 0) { count++; t = 辞書(); // 트럭마다 새 사전, 새 목록 t["no"] = count; t["dest"] = dest; t["load"] = 0; t["codes"] = []; waiting.追加(t); at = waiting.個数 - 1; } truck = waiting[at]; // 같은 사전을 가리킨다: 고치면 목록 안의 트럭이 바뀐다 truck["load"] = truck["load"] + w; truck["codes"].追加(code); もし (truck["load"] == cap) { waiting.位置で取り除く(at); departed.追加(truck); }}それぞれ (t の中 waiting){ departed.追加(t);}コンソール.書く(departed.個数);それぞれ (t の中 departed){ コンソール.書く(t["no"] + " " + t["dest"] + " " + t["load"] + " " + t["codes"].個数 + " " + t["codes"].つなぐ(" "));}