Parcels are loaded onto trucks in the order they arrive. One truck can be loaded until its total weight reaches C.
Each parcel has a tracking code, a destination and a weight.
When a parcel arrives, pick a truck by these rules.
- Among trucks that have not left yet, look for one whose destination is the same as the parcel's and whose total weight stays at most C after loading this parcel.
- If there are several, load it onto the one with the smallest number. It is not the one with the most or least room left.
- If there is none, call a new truck and load it. Trucks are numbered 1, 2, 3, … in the order they are called, and a new truck's destination is this parcel's destination.
- If after loading the truck's total weight is exactly C, the truck leaves at once. Nothing more is loaded onto a truck that has left.
After all parcels are loaded, the trucks that have not left leave in order of number.
The first line gives C and the number of parcels n, and the next n lines give "code destination weight", separated by single spaces, in arrival order.
Print the number of trucks on the first line.
Then, in the order the trucks left, print one line per truck: "number destination total count" followed by the tracking codes loaded on it in loading order, all separated by single spaces.
Try bundling one parcel and one truck each into a record (struct), and work with a list of truck records.
Input
1 ≤ n ≤ 1,000, 1 ≤ C ≤ 1,000,000, 1 ≤ weight ≤ C (integers). Tracking codes are 1 to 8 uppercase English letters and digits and are distinct. Destinations are 1 to 10 lowercase English letters.
Output
One line with the number of trucks, then one line per truck
Example 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
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
Bundling one truck (number, destination, total, list of codes): Python @dataclass (a list field needs field(default_factory=list)), Java a class with mutable fields (a record's fields cannot change), C# a class, C and C++ a struct, JS/TS an object { no, dest, load, codes: [] } (TS describes its shape with interface Truck). Craykon has no classes, so each truck is one Dict() (t["load"], t["codes"]) added to a list with waiting.Add(t). The key moment is changing the chosen truck. In Python, JS, TS, Java, a C# class and a Craykon dict, the value taken out of the list refers to the same truck, so truck.load += w changes the truck inside the list. In C you hold it through a pointer as in Truck *t = &trucks[k], and in C++ through a reference as in Truck &t = trucks[k]; a C++ vector moves its elements when it grows, which breaks a reference you are holding, so reserve first or find it again by position. A truck that leaves is removed from the list of waiting trucks: Python remove, JS/TS splice, Java/C# Remove, Craykon RemoveAt. Five traps: (1) Writing load + w < C never picks a truck that would become exactly C and calls a new one instead. (2) In Python, giving a default [] as in def __init__(self, no, dest, codes=[]) makes every truck share that one list, so the codes get mixed (@dataclass refuses such a default outright). (3) In C#, if the truck is a struct, Truck truck = waiting[at]; is a copy, so changing Load leaves the list unchanged (Truck t = trucks[k]; in C is the same). (4) Printing in order of truck number is wrong: a truck that filled up and left earlier comes first. (5) Looking only at the last truck with the same destination (next-fit) misses room left in earlier trucks.
Pythonmain.py · 38 lines
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 lines
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 lines
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 lines
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 lines
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 lines
#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 lines
#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 lines
// 크레이콘에는 클래스가 없어서 트럭 한 대를 사전 하나로 묶는다(no, dest, load, codes)첫줄 = Console.ReadNumbers();cap = 첫줄[0];n = 첫줄[1];count = 0;waiting = []; // 아직 떠나지 않은 트럭(번호 순)departed = []; // 떠난 차례for (i = 0; i < n; i++){ p = Console.ReadLine().Trim().Split(" "); code = p[0]; dest = p[1]; w = p[2].ToNumber(); at = -1; for (k = 0; k < waiting.Count; k++) { if (waiting[k]["dest"] == dest && waiting[k]["load"] + w <= cap) { at = k; break; } } if (at < 0) { count++; t = Dict(); // 트럭마다 새 사전, 새 목록 t["no"] = count; t["dest"] = dest; t["load"] = 0; t["codes"] = []; waiting.Add(t); at = waiting.Count - 1; } truck = waiting[at]; // 같은 사전을 가리킨다: 고치면 목록 안의 트럭이 바뀐다 truck["load"] = truck["load"] + w; truck["codes"].Add(code); if (truck["load"] == cap) { waiting.RemoveAt(at); departed.Add(truck); }}foreach (t in waiting){ departed.Add(t);}Console.WriteLine(departed.Count);foreach (t in departed){ Console.WriteLine(t["no"] + " " + t["dest"] + " " + t["load"] + " " + t["codes"].Count + " " + t["codes"].Join(" "));}