{ }codelper
sorted keyssumP0229

Find stock by part-code range

Every time parts arrive at a factory warehouse, one line "partCode quantity" is written. The first line gives the number of records n, the next n lines give the records, and the last line gives the start lo and end hi of a range, separated by one space. The quantities of the same part code are all added together. Part codes are compared as strings exactly.
So "a7" and "A7" are different codes. Codes are ordered by character code (ASCII).
Compare from the first character; the one whose first differing character has the smaller code comes first, and if one is the beginning of the other, the shorter comes first. The codes are 48-57 for digits 0-9, 65-90 for uppercase A-Z and 97-122 for lowercase a-z, so "B10" comes before "B9" and "Z" comes before "a". In this order, print every part code that is at least lo and at most hi, one per line as "partCode totalQuantity". lo and hi may be codes that are not in the records. If there is no such code, print "none".

Input
1 ≤ n ≤ 5,000, 1 ≤ quantity ≤ 1,000 (integers).
Part codes, lo and hi are 1 to 6 characters of uppercase and lowercase English letters and digits, and lo does not come after hi in the order above
Output
One line per code in range (code, total quantity), in code order.
If none, one line none
Example 1 · stdin
6
B9 4
a7 2
B10 5
A3 1
B9 6
b1 3
B b
stdout
B10 5
B9 10
a7 2
main.py
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

Languages split into those with a map that keeps its keys sorted and those without.
Java TreeMap cuts out a range including both ends with subMap(lo, true, hi, true), and with C++ std::map you loop from lower_bound(lo) up to just before upper_bound(hi).
C# SortedDictionary keeps keys sorted too but has no range method, so filter while looping.
Python dict, JS/TS Map and Craykon dicts keep insertion order, so take the keys out and sort them: Python sorted(d), JS/TS [...m.keys()].sort(), Craykon Keys then Sort().
The trap in this problem is that 'dictionary order' does not mean the same thing everywhere.
Python </sorted, JS/TS </sort(), Java compareTo, C++ std::string <, C strcmp and Craykon </Sort() use character-code order.
But JS localeCompare uses human reading order, so "a7" comes before "B10".
In C#, string.Compare and a SortedDictionary or List.Sort without a comparer use culture rules by default, so always pass StringComparer.Ordinal or use string.CompareOrdinal (only when .NET runs without culture data, in InvariantGlobalization mode, does it happen to be character-code order).
Sorting case-insensitively (key=str.lower) is wrong too.
And the range includes both ends, and "ABC" comes after "AB".

Pythonmain.py · 13 lines
n = int(input())total = {}for _ in range(n):    code, qty = input().split()    total[code] = total.get(code, 0) + int(qty)lo, hi = input().split()# 문자열의 <, sorted는 글자 코드 순이다(숫자 < 대문자 < 소문자)found = [code for code in sorted(total) if lo <= code <= hi]if found:    for code in found:        print(code, total[code])else:    print("none")
JavaScriptmain.js · 11 lines
const lines = require("fs").readFileSync(0, "utf8").split("\n");const n = Number(lines[0]);const total = new Map();for (let i = 1; i <= n; i++) {  const [code, qty] = lines[i].trim().split(" ");  total.set(code, (total.get(code) ?? 0) + Number(qty));}const [lo, hi] = lines[n + 1].trim().split(" ");// sort()는 기준 없이 쓰면 글자 코드 순이다. localeCompare는 사람이 읽는 순(a < B)이라 쓰지 않는다const found = [...total.keys()].filter((code) => lo <= code && code <= hi).sort();console.log(found.length ? found.map((code) => `${code} ${total.get(code)}`).join("\n") : "none");
TypeScriptmain.ts · 12 lines
import { readFileSync } from "node:fs";const lines: string[] = readFileSync(0, "utf8").split("\n");const n: number = Number(lines[0]);const total = new Map<string, number>();for (let i = 1; i <= n; i++) {  const [code, qty]: string[] = lines[i].trim().split(" ");  total.set(code, (total.get(code) ?? 0) + Number(qty));}const [lo, hi]: string[] = lines[n + 1].trim().split(" ");// sort()는 기준 없이 쓰면 글자 코드 순이다const found: string[] = [...total.keys()].filter((code) => lo <= code && code <= hi).sort();console.log(found.length ? found.map((code) => `${code} ${total.get(code)}`).join("\n") : "none");
JavaMain.java · 29 lines
import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.Map;import java.util.NavigableMap;import java.util.StringTokenizer;import java.util.TreeMap; public class Main {    public static void main(String[] args) throws Exception {        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));        int n = Integer.parseInt(br.readLine().trim());        // TreeMap은 열쇠를 compareTo 순(글자 코드 순)으로 늘 정렬해 둔다        TreeMap<String, Integer> total = new TreeMap<>();        for (int i = 0; i < n; i++) {            StringTokenizer st = new StringTokenizer(br.readLine());            total.merge(st.nextToken(), Integer.parseInt(st.nextToken()), Integer::sum);        }        StringTokenizer st = new StringTokenizer(br.readLine());        String lo = st.nextToken();        String hi = st.nextToken();        // 양 끝을 포함하는 범위        NavigableMap<String, Integer> range = total.subMap(lo, true, hi, true);        StringBuilder out = new StringBuilder();        for (Map.Entry<String, Integer> e : range.entrySet()) {            out.append(e.getKey()).append(' ').append(e.getValue()).append('\n');        }        System.out.print(range.isEmpty() ? "none\n" : out);    }}
C#Main.cs · 28 lines
using System;using System.Collections.Generic;using System.Text; class Program{    static void Main()    {        int n = int.Parse(Console.ReadLine().Trim());        // 문자열 비교는 문화권 규칙(a < B)이 기본이라, 글자 코드 순인 Ordinal을 꼭 준다        var total = new SortedDictionary<string, int>(StringComparer.Ordinal);        for (int i = 0; i < n; i++)        {            string[] p = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries);            total.TryGetValue(p[0], out int t);            total[p[0]] = t + int.Parse(p[1]);        }        string[] r = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries);        string lo = r[0], hi = r[1];        var sb = new StringBuilder();        foreach (var e in total)        {            if (string.CompareOrdinal(e.Key, lo) >= 0 && string.CompareOrdinal(e.Key, hi) <= 0)                sb.Append(e.Key).Append(' ').Append(e.Value).Append('\n');        }        Console.Write(sb.Length > 0 ? sb.ToString() : "none\n");    }}
C++main.cpp · 24 lines
#include <iostream>#include <map>#include <string> int main() {    std::ios::sync_with_stdio(false);    int n;    std::cin >> n;    // std::map은 열쇠를 글자 코드 순으로 정렬해 둔다    std::map<std::string, int> total;    for (int i = 0; i < n; i++) {        std::string code;        int qty;        std::cin >> code >> qty;        total[code] += qty;    }    std::string lo, hi;    std::cin >> lo >> hi;    // lower_bound(lo): lo 이상인 첫 열쇠, upper_bound(hi): hi보다 큰 첫 열쇠    auto first = total.lower_bound(lo);    auto last = total.upper_bound(hi);    if (first == last) std::cout << "none\n";    for (auto it = first; it != last; ++it) std::cout << it->first << ' ' << it->second << '\n';}
Cmain.c · 45 lines
#include <stdio.h>#include <stdlib.h>#include <string.h> /* C에는 사전이 없다. 코드와 합계를 배열에 모으고, strcmp(글자 코드 순)로 정렬한다 */typedef struct {    char code[8];    int total;} Item; static Item items[5000]; static int by_code(const void *a, const void *b) {    return strcmp(((const Item *)a)->code, ((const Item *)b)->code);} int main(void) {    int n, m = 0;    scanf("%d", &n);    for (int i = 0; i < n; i++) {        char code[16];        int qty;        scanf("%15s %d", code, &qty);        int j = 0;        while (j < m && strcmp(items[j].code, code) != 0) j++;        if (j == m) {            strcpy(items[m].code, code);            items[m].total = 0;            m++;        }        items[j].total += qty;    }    char lo[16], hi[16];    scanf("%15s %15s", lo, hi);    qsort(items, m, sizeof(Item), by_code);    int shown = 0;    for (int j = 0; j < m; j++) {        if (strcmp(items[j].code, lo) >= 0 && strcmp(items[j].code, hi) <= 0) {            printf("%s %d\n", items[j].code, items[j].total);            shown++;        }    }    if (shown == 0) puts("none");    return 0;}
Craykonmain.cray · 30 lines
n = Console.ReadLine().ToNumber();total = Dict();for (i = 0; i < n; i++){    p = Console.ReadLine().Trim().Split(" ");    if (!total.Contains(p[0]))    {        total[p[0]] = 0;    }    total[p[0]] = total[p[0]] + p[1].ToNumber();}r = Console.ReadLine().Trim().Split(" ");lo = r[0];hi = r[1];// 열쇠목록은 넣은 차례다. 정렬()은 문자열을 글자 코드 순으로 늘어놓는다codes = total.Keys;codes.Sort();shown = 0;foreach (code in codes){    if (lo <= code && code <= hi)    {        Console.WriteLine(code + " " + total[code]);        shown++;    }}if (shown == 0){    Console.WriteLine("none");}