In a treasure hunt, n children dug cells of a sandpit.
A cell of the sandpit is written as (row, column), and the treasure is buried in cell (a, b).
For each child, the cells they dug are given in the order they dug them.
Some children dug the same cell several times, and some dug no cell at all.
The distance between cell (r, c) and the treasure is |r - a| + |c - b|.
For each child, in input order, print one line with the name, the number of different cells that child dug, and the distance of the cell closest to the treasure among the cells that child dug.
For a child who dug no cell, write - in place of the distance.
On the next line print the number of different cells among all the cells dug by all the children.
On the last line print the names of the careful children in input order.
A careful child is one who dug at least one cell and whose cells are all at distance d or less from the treasure.
Instead of counting one by one in loops, try solving it with a query pipeline that chains removing duplicates, picking the smallest value, asking whether all items satisfy something, and joining lists together.
Input
The first line has n, a, b and d separated by single spaces. Each of the next n lines has a child's name, the number of cells dug k, and then k pairs of row and column of the dug cells, all separated by single spaces. 1 ≤ n ≤ 100, 1 ≤ a, b ≤ 1000, 0 ≤ d ≤ 2000, 0 ≤ k ≤ 50, 1 ≤ r, c ≤ 1000. Names are 1 to 10 lowercase English letters and are all different
Output
n + 2 lines. For each child print "name cell-count distance" separated by single spaces. On the next line print one number. On the last line print the names of the careful children separated by single spaces, or only - if there is no careful child
Example 1 · stdin
4 3 3 2
ann 4 3 4 2 2 3 4 3 3
bo 2 1 1 5 5
cy 0
dee 3 2 2 2 2 2 2
stdout
ann 3 0
bo 2 4
cy 0 -
dee 1 2
5
ann dee
Example 2 · stdin
2 5 5 1
zed 2 1 11 11 1
yo 1 5 7
stdout
zed 2 10
yo 1 2
3
-
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 · 6 languages
This problem accepts only Python, JavaScript, TypeScript, Java (streams), C# (LINQ) and C++ (C++20 std::ranges), whose languages come with tools for filtering and transforming lists. C and Craykon have no list tools that take a function to filter and transform. The same jobs have different names. Removing duplicates is set(cells) in Python, new Set(...) in JS/TS, distinct() in Java, Distinct() in C# and std::set in C++. Joining each child's list into one is a nested comprehension in Python, flatMap in JS/TS and Java, SelectMany in C# and std::views::join in C++. Asking whether all items satisfy something is all, every, allMatch, All and std::ranges::all_of, and the smallest value is min, Math.min(...), mapToInt(...).min(), Min and std::ranges::min. The point is what decides that two cells are 'the same'. A Python tuple, a Java record, a C# value tuple (int R, int C) and a C++ pair are compared by value. A JS/TS Set tells objects and arrays apart by 'is it the same object', so the solutions turn a cell into the string key r + "," + c before putting it in. Trap one: in JS, putting cells into a Set as [r, c] arrays does not merge equal cells. The first example becomes ann 4, dee 3 and a total of 9. Making the cell an ordinary class without equals in Java, or a class in C#, gives exactly the same answer. Trap two: building the key as ${r}${c} with no separator makes both (1, 11) and (11, 1) into 111. The second example becomes zed 1 10 and 2. Trap three: C++ std::unique removes only equal values that are next to each other. Without sorting, the first example becomes ann 4 and a total of 7. Trap four: 'do all satisfy it' is true for an empty list (Python all, JS every). If you do not ask separately whether any cell was dug, the last line of the first example becomes ann cy dee. Trap five: the smallest value of an empty list differs by language. Python min stops with ValueError, Java getAsInt() with NoSuchElementException, and C# Min with InvalidOperationException. JS Math.min() with no arguments is Infinity without any error, so the third line of the first example becomes cy 0 Infinity.
Pythonmain.py · 25 lines
import syslines = sys.stdin.read().split("\n")n, a, b, d = map(int, lines[0].split())kids = []for i in range(1, n + 1): p = lines[i].split() nums = [int(x) for x in p[2:]] # 칸은 (행, 열) 튜플: 값이 같으면 같은 것으로 친다 kids.append((p[0], list(zip(nums[0::2], nums[1::2]))))def dist(cell): return abs(cell[0] - a) + abs(cell[1] - b)for name, cells in kids: closest = min(map(dist, cells)) if cells else "-" # 빈 것의 min은 ValueError print(name, len(set(cells)), closest)print(len({cell for _, cells in kids for cell in cells}))# all은 빈 것에 참이므로 판 칸이 있는지를 따로 묻는다careful = [name for name, cells in kids if cells and all(dist(cell) <= d for cell in cells)]print(" ".join(careful) if careful else "-")
JavaScriptmain.js · 29 lines
const lines = require("fs").readFileSync(0, "utf8").split("\n");const [n, a, b, d] = lines[0].trim().split(/\s+/).map(Number);const kids = [];for (let i = 1; i <= n; i++) { const p = lines[i].trim().split(/\s+/); const nums = p.slice(2).map(Number); const cells = []; for (let j = 0; j < nums.length; j += 2) cells.push({ r: nums[j], c: nums[j + 1] }); kids.push({ name: p[0], cells });}const dist = (cell) => Math.abs(cell.r - a) + Math.abs(cell.c - b);// Set은 객체·배열을 값이 아니라 '같은 객체인가'로 가리므로 문자열 열쇠로 바꿔 넣는다const key = (cell) => cell.r + "," + cell.c;const out = kids.map((kid) => { const distinct = new Set(kid.cells.map(key)).size; const closest = kid.cells.length ? Math.min(...kid.cells.map(dist)) : "-"; // 빈 것의 Math.min은 Infinity return `${kid.name} ${distinct} ${closest}`;});out.push(String(new Set(kids.flatMap((kid) => kid.cells.map(key))).size));// every는 빈 배열에 참이므로 판 칸이 있는지를 따로 묻는다const careful = kids .filter((kid) => kid.cells.length > 0 && kid.cells.every((cell) => dist(cell) <= d)) .map((kid) => kid.name);out.push(careful.length ? careful.join(" ") : "-");console.log(out.join("\n"));
TypeScriptmain.ts · 40 lines
import { readFileSync } from "node:fs";interface Cell { r: number; c: number;}interface Kid { name: string; cells: Cell[];}const lines: string[] = readFileSync(0, "utf8").split("\n");const [n, a, b, d] = lines[0].trim().split(/\s+/).map(Number);const kids: Kid[] = [];for (let i = 1; i <= n; i++) { const p = lines[i].trim().split(/\s+/); const nums = p.slice(2).map(Number); const cells: Cell[] = []; for (let j = 0; j < nums.length; j += 2) cells.push({ r: nums[j], c: nums[j + 1] }); kids.push({ name: p[0], cells });}const dist = (cell: Cell): number => Math.abs(cell.r - a) + Math.abs(cell.c - b);// Set은 객체·배열을 값이 아니라 '같은 객체인가'로 가리므로 문자열 열쇠로 바꿔 넣는다const key = (cell: Cell): string => cell.r + "," + cell.c;const out: string[] = kids.map((kid) => { const distinct = new Set(kid.cells.map(key)).size; const closest = kid.cells.length ? String(Math.min(...kid.cells.map(dist))) : "-"; // 빈 것의 Math.min은 Infinity return `${kid.name} ${distinct} ${closest}`;});out.push(String(new Set(kids.flatMap((kid) => kid.cells.map(key))).size));// every는 빈 배열에 참이므로 판 칸이 있는지를 따로 묻는다const careful: string[] = kids .filter((kid) => kid.cells.length > 0 && kid.cells.every((cell) => dist(cell) <= d)) .map((kid) => kid.name);out.push(careful.length ? careful.join(" ") : "-");console.log(out.join("\n"));
JavaMain.java · 46 lines
import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.List;import java.util.OptionalInt;import java.util.stream.Collectors;public class Main { // record는 필드 값으로 equals·hashCode를 만들어 준다: distinct()가 값으로 가린다 record Cell(int r, int c) {} record Kid(String name, List<Cell> cells) {} public static void main(String[] args) throws Exception { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); String[] first = in.readLine().trim().split(" "); int n = Integer.parseInt(first[0]), a = Integer.parseInt(first[1]); int b = Integer.parseInt(first[2]), d = Integer.parseInt(first[3]); List<Kid> kids = new ArrayList<>(); for (int i = 0; i < n; i++) { String[] p = in.readLine().trim().split(" "); List<Cell> cells = new ArrayList<>(); for (int j = 2; j < p.length; j += 2) cells.add(new Cell(Integer.parseInt(p[j]), Integer.parseInt(p[j + 1]))); kids.add(new Kid(p[0], cells)); } StringBuilder out = new StringBuilder(); for (Kid kid : kids) { long distinct = kid.cells().stream().distinct().count(); // 빈 스트림의 min은 빈 OptionalInt다 OptionalInt closest = kid.cells().stream().mapToInt(c -> Math.abs(c.r() - a) + Math.abs(c.c() - b)).min(); out.append(kid.name()).append(' ').append(distinct).append(' ') .append(closest.isPresent() ? String.valueOf(closest.getAsInt()) : "-").append('\n'); } out.append(kids.stream().flatMap(kid -> kid.cells().stream()).distinct().count()).append('\n'); // allMatch는 빈 스트림에 참이므로 판 칸이 있는지를 따로 묻는다 String careful = kids.stream() .filter(kid -> !kid.cells().isEmpty() && kid.cells().stream().allMatch(c -> Math.abs(c.r() - a) + Math.abs(c.c() - b) <= d)) .map(Kid::name) .collect(Collectors.joining(" ")); out.append(careful.isEmpty() ? "-" : careful).append('\n'); System.out.print(out); }}
C#Main.cs · 43 lines
using System;using System.Collections.Generic;using System.Linq;using System.Text;class Program{ static void Main() { var lines = Console.In.ReadToEnd().Split('\n'); var first = lines[0].Trim().Split(' ').Select(int.Parse).ToArray(); int n = first[0], a = first[1], b = first[2], d = first[3]; // 칸은 값 튜플 (R, C): 값이 같으면 같은 것으로 친다 var kids = new List<(string Name, List<(int R, int C)> Cells)>(); for (int i = 1; i <= n; i++) { var p = lines[i].Trim().Split(' '); var nums = p.Skip(2).Select(int.Parse).ToArray(); var cells = Enumerable.Range(0, nums.Length / 2).Select(j => (R: nums[2 * j], C: nums[2 * j + 1])).ToList(); kids.Add((p[0], cells)); } Func<(int R, int C), int> dist = cell => Math.Abs(cell.R - a) + Math.Abs(cell.C - b); var sb = new StringBuilder(); foreach (var kid in kids) { int distinct = kid.Cells.Distinct().Count(); // 빈 것의 Min()은 InvalidOperationException string closest = kid.Cells.Any() ? kid.Cells.Min(dist).ToString() : "-"; sb.Append($"{kid.Name} {distinct} {closest}\n"); } sb.Append(kids.SelectMany(kid => kid.Cells).Distinct().Count()).Append('\n'); // All은 빈 것에 참이므로 판 칸이 있는지를 따로 묻는다 var careful = kids.Where(kid => kid.Cells.Any() && kid.Cells.All(cell => dist(cell) <= d)) .Select(kid => kid.Name) .ToList(); sb.Append(careful.Count > 0 ? string.Join(" ", careful) : "-").Append('\n'); Console.Write(sb); }}
C++main.cpp · 55 lines
#include <algorithm>#include <cstdlib>#include <iostream>#include <ranges>#include <set>#include <string>#include <utility>#include <vector>using Cell = std::pair<int, int>; // (행, 열): pair는 값으로 견준다struct Kid { std::string name; std::vector<Cell> cells;};int main() { int n, a, b, d; std::cin >> n >> a >> b >> d; std::vector<Kid> kids(n); for (Kid& kid : kids) { int k; std::cin >> kid.name >> k; kid.cells.resize(k); for (Cell& cell : kid.cells) std::cin >> cell.first >> cell.second; } auto dist = [&](const Cell& cell) { return std::abs(cell.first - a) + std::abs(cell.second - b); }; for (const Kid& kid : kids) { // set에 넣으면 같은 칸은 하나만 남는다 std::set<Cell> distinct(kid.cells.begin(), kid.cells.end()); std::cout << kid.name << ' ' << distinct.size() << ' '; // 빈 범위에는 ranges::min을 쓸 수 없다 if (kid.cells.empty()) std::cout << "-\n"; else std::cout << std::ranges::min(kid.cells | std::views::transform(dist)) << '\n'; } // 아이마다의 칸 목록을 하나로 이어 붙인다 std::set<Cell> all; for (const Cell& cell : kids | std::views::transform(&Kid::cells) | std::views::join) all.insert(cell); std::cout << all.size() << '\n'; // all_of는 빈 범위에 참이므로 판 칸이 있는지를 따로 묻는다 auto careful = kids | std::views::filter([&](const Kid& kid) { return !kid.cells.empty() && std::ranges::all_of(kid.cells, [&](const Cell& cell) { return dist(cell) <= d; }); }); bool any = false; for (const Kid& kid : careful) { std::cout << (any ? " " : "") << kid.name; any = true; } std::cout << (any ? "\n" : "-\n");}