A game chat room filters spam, that is, people repeating the same thing.
The first line gives k, the number of messages that stay on screen, and s, the blocking threshold, separated by one space.
The second line gives the number of messages n, and each of the next n lines gives one message in the form "name word".
The room keeps a screen list and a blocked list, and both are empty at first.
Handle the messages one by one in the order received: check the three cases below from the top and do only the first one that applies.
1. If the sender's name is in the blocked list, ignore the message. Nothing else changes.
2. If the screen list has a message with the same name and the same word, the message is spam. It is not printed and not added to the screen list, and the warning count of that name goes up by 1. When the warning count of that name becomes s, add the name to the end of the blocked list.
3. Any other message is shown. Print "name word" exactly as received on one line and add the message to the end of the screen list. If the screen list then has more than k messages, remove the one that was added earliest.
Words are compared without distinguishing uppercase and lowercase letters, so hi and HI are the same word.
Names are the same only when every letter is the same.
If the names differ, the message is not spam even when the words are the same.
The warning count of each name starts at 0 and never goes down.
When a name is blocked, its messages already in the screen list are not removed.
After all messages, print the number of messages filtered as spam and the number of ignored messages on one line, separated by one space.
On the last line print the names in the blocked list in the order they were blocked, separated by single spaces. If no name was blocked, print "-".
Input
1 ≤ k ≤ 50, 1 ≤ s ≤ 5, 1 ≤ n ≤ 2,000. A name is 1 to 8 lowercase English letters, a word is 1 to 8 uppercase or lowercase English letters, and one space separates them
Output
One line per shown message (exactly as received), then one line "spam count ignored count", then a last line with the blocked names (or -)
Example 1 · stdin
2 2
10
mina hi
jun hi
mina HI
jun yo
mina hi
mina Hi
mina hi
jun yo
ab c
a bc
stdout
mina hi
jun hi
jun yo
mina hi
ab c
a bc
3 1
mina
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
This problem asks "is it in the list?" twice: a single name in the blocked list, and a (name, word) pair in the screen list. Finding one string is Python name in blocked, JS/TS blocked.includes(name), Java blocked.contains(name), C# blocked.Contains(name), C++ std::find(blocked.begin(), blocked.end(), name) != blocked.end(), Craykon blocked.Contains(name), and in C a loop that compares with strcmp. The languages part ways on the pair. A Python tuple (name, low) in screen, std::find over C++ std::pairs, Contains on a C# List<(string, string)> of tuples and contains on a Java list holding List.of(name, low) all compare the values inside. Trap one: JS/TS screen.includes([name, low]), Java contains(new String[] {name, low}) on a List<String[]> and Craykon screen.Contains([name, low]) are always false, because the freshly made array or list is a different object even when its contents match. No error appears and no spam is ever caught, so the third message of the example, mina HI, is printed. JS/TS compare the contents with screen.some(([a, b]) => a === name && b === low), and the Craykon solution keeps a list of names and a list of words side by side and compares position by position. Trap two: you can also join the pair into one string and search for that, but joining without a separator as name + low turns both ab + c and a + bc into abc, so the last message of the example, a bc, is filtered as spam. Put a space, which can appear in neither part, between them. Trap three: to ignore case, use the lowercased word both when adding and when searching (Python lower(), JS/TS toLowerCase(), Java toLowerCase(Locale.ROOT), C# ToLowerInvariant(), C/C++ tolower per character, Craykon ToLower()). Without it mina HI is not spam. The output is the message as received, so keep the original word as well. Trap four: searching for the word alone, without the name, treats the same word from someone else as spam, like the second message jun hi. Trap five: if a message filtered as spam is added to the screen list, messages on screen are pushed out or stay too long, and the fifth message of the example, mina hi, is wrongly filtered. Trap six: removing when the size is >= k after adding leaves only k − 1 messages on screen. Removing the front is Python pop(0), JS/TS shift(), Java remove(0), C# RemoveAt(0), C++ erase(begin()), Craykon RemoveAt(0), and in C you shift the array down by one. Trap seven: ask the blocked list first. If the screen list is checked first, the seventh message, sent by the already blocked mina, is counted as spam instead of ignored, and 3 1 becomes 4 0.
Pythonmain.py · 28 lines
import syslines = sys.stdin.read().split("\n")k, s = map(int, lines[0].split())n = int(lines[1])screen = [] # 화면에 남은 (이름, 소문자 낱말) 쌍, 오래된 것이 앞blocked = [] # 차단된 이름, 차단된 차례대로warn = {}repeats = ignored = 0out = []for i in range(n): name, word = lines[2 + i].split() key = (name, word.lower()) if name in blocked: ignored += 1 elif key in screen: # 튜플은 값으로 비교한다 repeats += 1 warn[name] = warn.get(name, 0) + 1 if warn[name] == s: blocked.append(name) else: out.append(f"{name} {word}") screen.append(key) if len(screen) > k: screen.pop(0)out.append(f"{repeats} {ignored}")out.append(" ".join(blocked) if blocked else "-")print("\n".join(out))
JavaScriptmain.js · 28 lines
const lines = require("fs").readFileSync(0, "utf8").split("\n");const [k, s] = lines[0].trim().split(/\s+/).map(Number);const n = Number(lines[1]);const screen = []; // 화면에 남은 [이름, 소문자 낱말] 쌍, 오래된 것이 앞const blocked = []; // 차단된 이름, 차단된 차례대로const warn = new Map();let repeats = 0;let ignored = 0;const out = [];for (let i = 0; i < n; i++) { const [name, word] = lines[2 + i].trim().split(/\s+/); const low = word.toLowerCase(); if (blocked.includes(name)) { ignored++; } else if (screen.some(([a, b]) => a === name && b === low)) { // includes([name, low])는 새 배열이라 늘 false다. 속을 하나씩 견준다 repeats++; warn.set(name, (warn.get(name) ?? 0) + 1); if (warn.get(name) === s) blocked.push(name); } else { out.push(`${name} ${word}`); screen.push([name, low]); if (screen.length > k) screen.shift(); }}out.push(`${repeats} ${ignored}`);out.push(blocked.length > 0 ? blocked.join(" ") : "-");console.log(out.join("\n"));
TypeScriptmain.ts · 30 lines
import { readFileSync } from "node:fs";const lines: string[] = readFileSync(0, "utf8").split("\n");const [k, s]: number[] = lines[0].trim().split(/\s+/).map(Number);const n: number = Number(lines[1]);const screen: [string, string][] = []; // 화면에 남은 [이름, 소문자 낱말] 쌍, 오래된 것이 앞const blocked: string[] = []; // 차단된 이름, 차단된 차례대로const warn = new Map<string, number>();let repeats = 0;let ignored = 0;const out: string[] = [];for (let i = 0; i < n; i++) { const [name, word]: string[] = lines[2 + i].trim().split(/\s+/); const low: string = word.toLowerCase(); if (blocked.includes(name)) { ignored++; } else if (screen.some(([a, b]) => a === name && b === low)) { // includes([name, low])는 새 배열이라 늘 false다. 속을 하나씩 견준다 repeats++; const count: number = (warn.get(name) ?? 0) + 1; warn.set(name, count); if (count === s) blocked.push(name); } else { out.push(`${name} ${word}`); screen.push([name, low]); if (screen.length > k) screen.shift(); }}out.push(`${repeats} ${ignored}`);out.push(blocked.length > 0 ? blocked.join(" ") : "-");console.log(out.join("\n"));
JavaMain.java · 44 lines
import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.HashMap;import java.util.List;import java.util.Locale;import java.util.Map;public class Main { public static void main(String[] args) throws Exception { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); String[] first = in.readLine().trim().split(" "); int k = Integer.parseInt(first[0]); int s = Integer.parseInt(first[1]); int n = Integer.parseInt(in.readLine().trim()); // List.of(이름, 낱말)은 equals가 속을 견주므로 contains로 찾을 수 있다(String[]는 안 된다) List<List<String>> screen = new ArrayList<>(); List<String> blocked = new ArrayList<>(); Map<String, Integer> warn = new HashMap<>(); int repeats = 0; int ignored = 0; StringBuilder out = new StringBuilder(); for (int i = 0; i < n; i++) { String[] parts = in.readLine().trim().split(" "); String name = parts[0]; String word = parts[1]; List<String> key = List.of(name, word.toLowerCase(Locale.ROOT)); if (blocked.contains(name)) { ignored++; } else if (screen.contains(key)) { repeats++; int count = warn.merge(name, 1, Integer::sum); if (count == s) blocked.add(name); } else { out.append(name).append(' ').append(word).append('\n'); screen.add(key); if (screen.size() > k) screen.remove(0); } } out.append(repeats).append(' ').append(ignored).append('\n'); out.append(blocked.isEmpty() ? "-" : String.join(" ", blocked)).append('\n'); System.out.print(out); }}
C#Main.cs · 45 lines
using System;using System.Collections.Generic;using System.Text;class Program{ static void Main() { string[] first = Console.ReadLine().Trim().Split(' '); int k = int.Parse(first[0]); int s = int.Parse(first[1]); int n = int.Parse(Console.ReadLine()); // 튜플 (string, string)은 값으로 비교하므로 Contains로 찾을 수 있다(string[]은 안 된다) var screen = new List<(string, string)>(); var blocked = new List<string>(); var warn = new Dictionary<string, int>(); int repeats = 0, ignored = 0; var sb = new StringBuilder(); for (int i = 0; i < n; i++) { string[] parts = Console.ReadLine().Trim().Split(' '); string name = parts[0], word = parts[1]; var key = (name, word.ToLowerInvariant()); if (blocked.Contains(name)) { ignored++; } else if (screen.Contains(key)) { repeats++; warn[name] = warn.GetValueOrDefault(name, 0) + 1; if (warn[name] == s) blocked.Add(name); } else { sb.Append(name).Append(' ').Append(word).Append('\n'); screen.Add(key); if (screen.Count > k) screen.RemoveAt(0); } } sb.Append(repeats).Append(' ').Append(ignored).Append('\n'); sb.Append(blocked.Count > 0 ? string.Join(" ", blocked) : "-").Append('\n'); Console.Write(sb); }}
C++main.cpp · 42 lines
#include <algorithm>#include <cctype>#include <iostream>#include <map>#include <string>#include <utility>#include <vector>using namespace std;int main() { int k, s, n; cin >> k >> s >> n; vector<pair<string, string>> screen; // 화면에 남은 (이름, 소문자 낱말), 오래된 것이 앞 vector<string> blocked; // 차단된 이름, 차단된 차례대로 map<string, int> warn; int repeats = 0, ignored = 0; for (int i = 0; i < n; i++) { string name, word; cin >> name >> word; string low = word; for (char &c : low) c = (char)tolower((unsigned char)c); pair<string, string> key{name, low}; if (find(blocked.begin(), blocked.end(), name) != blocked.end()) { ignored++; } else if (find(screen.begin(), screen.end(), key) != screen.end()) { // pair는 값으로 비교한다 repeats++; if (++warn[name] == s) blocked.push_back(name); } else { cout << name << ' ' << word << '\n'; screen.push_back(key); if ((int)screen.size() > k) screen.erase(screen.begin()); } } cout << repeats << ' ' << ignored << '\n'; if (blocked.empty()) { cout << "-\n"; } else { for (size_t i = 0; i < blocked.size(); i++) cout << (i ? " " : "") << blocked[i]; cout << '\n'; } return 0;}
Cmain.c · 68 lines
#include <ctype.h>#include <stdio.h>#include <string.h>#define MAXK 50#define MAXN 2000static char scr_name[MAXK][9], scr_word[MAXK][9]; /* 화면 목록, 오래된 것이 앞 */static char people[MAXN][9]; /* 도배한 적이 있는 이름 */static int warn[MAXN];static char blocked[MAXN][9];/* C에는 목록 찾기가 없다. strcmp로 하나씩 견준다 */static int find_name(char list[][9], int count, const char *name) { for (int i = 0; i < count; i++) if (strcmp(list[i], name) == 0) return i; return -1;}int main(void) { int k, s, n; if (scanf("%d %d %d", &k, &s, &n) != 3) return 1; int screen = 0, npeople = 0, nblocked = 0, repeats = 0, ignored = 0; for (int i = 0; i < n; i++) { char name[9], word[9], low[9]; if (scanf("%8s %8s", name, word) != 2) return 1; size_t len = strlen(word); for (size_t j = 0; j <= len; j++) low[j] = (char)tolower((unsigned char)word[j]); if (find_name(blocked, nblocked, name) >= 0) { ignored++; continue; } int on_screen = 0; for (int j = 0; j < screen; j++) if (strcmp(scr_name[j], name) == 0 && strcmp(scr_word[j], low) == 0) on_screen = 1; if (on_screen) { repeats++; int p = find_name(people, npeople, name); if (p < 0) { p = npeople++; strcpy(people[p], name); warn[p] = 0; } if (++warn[p] == s) strcpy(blocked[nblocked++], name); } else { printf("%s %s\n", name, word); if (screen == k) { /* 꽉 찼으면 가장 오래된 것을 빼고 한 칸씩 당긴다 */ for (int j = 1; j < screen; j++) { strcpy(scr_name[j - 1], scr_name[j]); strcpy(scr_word[j - 1], scr_word[j]); } screen--; } strcpy(scr_name[screen], name); strcpy(scr_word[screen], low); screen++; } } printf("%d %d\n", repeats, ignored); if (nblocked == 0) { printf("-\n"); } else { for (int i = 0; i < nblocked; i++) printf("%s%s", i ? " " : "", blocked[i]); printf("\n"); } return 0;}
Craykonmain.cray · 66 lines
first = Console.ReadNumbers();k = first[0];s = first[1];n = Console.ReadLine().ToNumber();names = []; // 화면에 남은 메시지의 이름, 오래된 것이 앞words = []; // 같은 자리의 소문자 낱말blocked = []; // 차단된 이름, 차단된 차례대로warn = Dict();repeats = 0;ignored = 0;for (i = 0; i < n; i++){ parts = Console.ReadLine().Split(); name = parts[0]; low = parts[1].ToLower(); if (blocked.Contains(name)) { ignored += 1; } else if (onScreen(names, words, name, low)) { repeats += 1; if (!warn.Contains(name)) { warn[name] = 0; } warn[name] += 1; if (warn[name] == s) { blocked.Add(name); } } else { Console.WriteLine(name + " " + parts[1]); names.Add(name); words.Add(low); if (names.Count > k) { names.RemoveAt(0); words.RemoveAt(0); } }}Console.WriteLine(repeats + " " + ignored);if (blocked.Count > 0){ Console.WriteLine(blocked.Join(" "));}else{ Console.WriteLine("-");}// 목록.있나([name, low])는 새 목록이라 늘 거짓이다. 이름과 낱말을 자리마다 견준다onScreen(names, words, name, low){ for (j = 0; j < names.Count; j++) { if (names[j] == name && words[j] == low) { return true; } } return false;}