Шляпа

@dmitrii2000 · Регистрация: 03.05.2020

Студворк — интернет-сервис помощи студентам

Шляпа
Летом Максим съездил в Летнюю Какую-то Школу, где, помимо учёбы, ему очень запомнилась игра «Шляпа», в которую он вместе с друзьями играл всю смену. Опишем правила игры, которых они придерживались. Обратите внимание: эти правила немного отличаются от общепринятых.

Изначально в шляпу помещают некоторое количество бумажек с написанными на них различными словами. После этого команды из двух человек по очереди и в случайном порядке начинают отгадывать слова — один член команды объясняет другому написанное на бумажке слово, не используя однокоренные. Если партнёр отгадывает его, то команде засчитывается одно очко, слово выкидывается, а команда достаёт из шляпы новое, если у неё ещё осталось время в этом раунде. Если команда не успевает отгадать очередное слово, то бумажка на которой оно написано, возвращается в шляпу, и ход передаётся какой-то случайной команде, возможно, той же самой. Игра продолжается, пока все слова из шляпы не будут отгаданы.

Теперь Максим провёл турнир для N команд из своей школы и должен определить победителя. Он неаккуратно вёл записи игры и не отмечал, сколько слов отгадала каждая из команд, зато он записывал в хронологическом порядке каждый раз, когда какая-либо команда доставала какую-либо бумажку из шляпы. Всего таких записей M, и они следуют в хронологическом порядке. Помогите Максиму восстановить по сделанным записям, сколько слов отгадала каждая из команд.

Входные данные

В первой строке дано количество команд N и количество попыток отгадать слова M (1 ≤ N ≤ 100000, 1 ≤ M ≤ 100000). В следующих M строках сначала указывается номер ni команды, пытавшейся отгадать слово, а через пробел дано слово wi, написанное на бумажке. Номера команд лежат в диапазоне от 1 до N. Все слова wi состоят из строчных латинских букв и имеют ненулевую длину, не превосходящую 10 букв.

Выходные данные

Выведите в одну строку N чисел, i-е число должно равняться количеству слов, отгаданному i-й командой.

Примеры
Ввод
Вывод
2 3
1 hat
1 shirt
2 hat
1 1
3 2
1 mom
3 dad
1 0 1

@eaa · 24.06.2020, 17:46

В чем конкретно вопрос?
Заводите словарь для ключ - слово, значение - номер команды и проверяйте было или нет слово.

@Alestrange · 25.06.2020, 23:47

Вот друг мой, в Сириусе это решение было зачтено.

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
n, m = [int(i) for i in input().split()]
w = {}
for i in range(m):
    s = input().split()
    if s[1] in w.keys():
        w[s[1]] = int(s[0])
    else:
        w.update({s[1]: int(s[0])})
res = [0 for i in range(n)]
for i in w.values():
    res[i - 1] += 1
res = [str(i) for i in res]
print(" ".join(res))

@1timchik1 · 27.06.2020, 12:38

Python
1
2
3
4
5
6
7
8
9
n, m = list(map(int, input().split()))
word = {}
scores = [0] *n
for _ in range(m):
    t, w = input().split()
    word[w] = t
for key in word:
    scores[int(word[key]) - 1] += 1
print(*scores)

@gurulTailan · 27.06.2020, 13:17

Уважаемый Alestrange, не могли бы Вы, пожалуйста объяснить, зачем использовать метод update к ассоциативному массиву:

Сообщение от Alestrange

w.update({s[1]: int(s[0])})

По-моему, можно обойтись без условия

Сообщение от Alestrange

if s[1] in w.keys():
w[s[1]] = int(s[0])
else:
w.update({s[1]: int(s[0])})

- просто написать вместо этого

Python
1
w[s[1]] = int(s[0])

Мой код:

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
n, m = map(int, input().split())
words = {}
for i in range(m):
    a = input().split()
    number, word = int(a[0]), a[1]
    if word in words.keys():
        words[word] = number
    else:
        words[word] = number
ans = [0 for i in range(n)]
for i in words.values():
    ans[i - 1] += 1
print(" ".join(list(map(str, ans))))

Добавлено через 10 минут
Или так:

Python
1
2
3
4
5
6
7
8
9
10
n, m = map(int, input().split())
words = {}
for i in range(m):
    a = input().split()
    number, word = int(a[0]), a[1]
    words[word] = number
ans = [0 for i in range(n)]
for i in words.values():
    ans[i - 1] += 1
print(" ".join(list(map(str, ans))))

Забыл if убрать!

@weatherReport · 28.06.2020, 10:53

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
n, m = map(int, input().split(' '))
team = dict()
words = dict()
 
for i in range(m):
    a = input().split(' ')
    if a[1] in words:
        team[words[a[1]]] -= 1
        words[a[1]] = int(a[0])
        team[int(a[0])] = team.get(int(a[0]), 0) + 1
    else:
        words[a[1]] = int(a[0])
        team[int(a[0])] = team.get(int(a[0]), 0) + 1
t = ''
for i in range(n):
    t += str(team.get(i + 1, 0)) + ' '
print(t[:-1])

@Ktd1231 · 11.09.2020, 21:34

Решение на c++

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
 
void solve(){
    ll n, m;
    cin>>n>>m;
    map<string,ll> mp;
    map<ll,ll> rating;
    for(int i = 1;i <= n;i++){
        rating[i] = 1;
    }
    for(ll i = 0;i < m;i++){
        ll team;
        string word;
        cin>>team>>word;
        if(mp[word] != 0){
                ll team_2 = mp[word];
                rating[team_2]--;
                mp[word] = team;
                rating[team]++;
        }else{
            rating[team]++;
            mp[word] = team;
        }
    }
 
    ll temp = 0;
    ll team_ans = 0;
    for(auto it = rating.begin();it != rating.end();it++){
            cout<<it->second - 1<<" ";
    }
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t;
    //cin>>t;
    //while(t--)
    solve();
    return 0;
}

@iSmokeJC · 12.09.2020, 08:49

Ktd1231, зачем решение на плюсах в разделе питона?

@fi_van · 04.08.2022, 00:12

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <string>
#include <deque>
using namespace std;
typedef long long ll;
 
int main() {
    int n, m;
    cin >> n >> m;
    map<int, int> team_cnt;
    map<string, int> cnt_words_last_team;
    for (int i = 0; i < m; ++i) {
        int team_num; string word;
        cin >> team_num >> word;
        if (cnt_words_last_team.find(word) != cnt_words_last_team.end()) {
            team_cnt[cnt_words_last_team[word]] -= 1;
        }
        cnt_words_last_team[word] = team_num;
        team_cnt[team_num] += 1;
    }
    for (int i = 1; i < n + 1; ++i) {
        cout << team_cnt[i] << " ";
    }
}

Вот попроще. Правда решение на плюсах в разделе питона по данной задаче действительно не целесообразно, так как проверка на содержание элемента в ассоциативном массиве в c++ занимает O(log n) времени, а в питоне O(n).

@yeggygyg · 01.05.2024, 16:25

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// Online C++ compiler to run C++ program online
#include <bits/stdc++.h>
using namespace std;
int main(){ 
    int n,m,cnt; 
    string s;
    cin >> n >> m;
    map< string , int> dict;
    vector < int > ans(n,0);
    for(int i = 0; i < m; i++) {
        cin >> cnt >> s;
        dict[s] = cnt; 
    }
    for (auto& item : dict)
        ans[item.second - 1]++;
    for(int i = 0; i < n; i++) 
        cout << ans[i] <<' '; 
}

c++

@Ilya_Av · 02.05.2024, 23:15

это какие курсы надо пройти, чтобы такого рода задачи решать?

Добавлено через 1 минуту
Alestrange, какой материал вы изучили? интересно, что надо пройти для решения таких задач?

@idealist · 03.05.2024, 02:25

Сообщение от Ilya_Av

Alestrange, какой материал вы изучили? интересно, что надо пройти для решения таких задач?

)) Он с 22-го года не заходит.

Сообщение от Ilya_Av

это какие курсы надо пройти, чтобы такого рода задачи решать?

Словарей достаточно:

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
from collections import Counter
 
team_of_word = Counter()
res_of_team = Counter()
n,m = map(int, input('n, m->').split())
for _ in range(m):
    team_num_s, word = input('номер команды, слово->').split()
    team_num = int(team_num_s)
    old_team_num = team_of_word[word]
    team_of_word[word] = team_num
    res_of_team[old_team_num] -= 1
    res_of_team[team_num] += 1
 
print(res_of_team)
for i in range(n):
    print(res_of_team[i+1], end=' ')

@idealist · 03.05.2024, 09:25

Пардон, отладочную строчку 14 забыл убрать. Вот так нужно:

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
from collections import Counter
 
team_of_word = Counter()
res_of_team = Counter()
n, m = map(int, input('n, m->').split())
for _ in range(m):
    team_num_s, word = input('номер команды, слово->').split()
    team_num = int(team_num_s)
    old_team_num = team_of_word[word]
    team_of_word[word] = team_num
    res_of_team[old_team_num] -= 1
    res_of_team[team_num] += 1
 
for i in range(n):
    print(res_of_team[i + 1], end=' ')

@mactraxer456 · 23.08.2025, 16:15

куча лишних действий у тебя
вот оптимизированный код:

Python
1
2
3
4
5
6
7
8
9
n, m = map(int,input().split())
name_num = {}
for i in range(m):
    s = input().split()
    name_num[s[1]] = int(s[0])
res = [0] * n
for i in name_num.values():
    res[i - 1] += 1
print(*res)

на сириусе прошел

Новые блоги и статьи Все статьи Все блоги /
Переходник USB-CAN-GPIO Eddy_Em 20.03.2026 Достаточно давно на работе возникла необходимость в переходнике CAN-USB с гальваноразвязкой, оный и был разработан. Однако, все меня терзала совесть, что аж 48-ногий МК используется так тупо: просто. . .	Оттенки серого Argus19 18.03.2026 Оттенки серого Нашёл в интернете 3 прекрасных модуля: Модуль класса открытия диалога открытия/ сохранения файла на Win32 API; Модуль класса быстрого перекодирования цветного изображения в оттенки. . .	SDL3 для Desktop (MinGW): Рисуем цветные прямоугольники с помощью рисовальщика SDL3 на Си и C++ 8Observer8 17.03.2026 Содержание блога Финальные проекты на Си и на C++: finish-rectangles-sdl3-c. zip finish-rectangles-sdl3-cpp. zip	Символические и жёсткие ссылки в Linux. algri14 15.03.2026 Существует два типа ссылок — символические и жёсткие. Ссылка в Linux — это запись в каталоге, которая может указывать либо на inode «файла-ИСТОЧНИКА», тогда это будет «жёсткая ссылка» (hard link),. . .
[Owen Logic] Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора ФедосеевПавел 14.03.2026 Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора ВВЕДЕНИЕ Выполняя задание на управление насосной группой заполнения резервуара,. . .	делаю науч статью по влиянию грибов на сукцессию anaschu 13.03.2026 прикрепляю статью	SDL3 для Desktop (MinGW): Создаём пустое окно с нуля для 2D-графики на SDL3, Си и C++ 8Observer8 10.03.2026 Содержание блога Финальные проекты на Си и на C++: hello-sdl3-c. zip hello-sdl3-cpp. zip Результат:	Установка CMake и MinGW 13.1 для сборки С и C++ приложений из консоли и из Qt Creator в EXE 8Observer8 10.03.2026 Содержание блога MinGW - это коллекция инструментов для сборки приложений в EXE. CMake - это система сборки приложений. Здесь описаны базовые шаги для старта программирования с помощью CMake и. . .

@dmitrii2000 2 / 2 / 0 Регистрация: 03.05.2020 Сообщений: 202

	Шляпа 24.06.2020, 14:22. Показов 25569. Ответов 13 Метки нет (Все метки) Шляпа Летом Максим съездил в Летнюю Какую-то Школу, где, помимо учёбы, ему очень запомнилась игра «Шляпа», в которую он вместе с друзьями играл всю смену. Опишем правила игры, которых они придерживались. Обратите внимание: эти правила немного отличаются от общепринятых. Изначально в шляпу помещают некоторое количество бумажек с написанными на них различными словами. После этого команды из двух человек по очереди и в случайном порядке начинают отгадывать слова — один член команды объясняет другому написанное на бумажке слово, не используя однокоренные. Если партнёр отгадывает его, то команде засчитывается одно очко, слово выкидывается, а команда достаёт из шляпы новое, если у неё ещё осталось время в этом раунде. Если команда не успевает отгадать очередное слово, то бумажка на которой оно написано, возвращается в шляпу, и ход передаётся какой-то случайной команде, возможно, той же самой. Игра продолжается, пока все слова из шляпы не будут отгаданы. Теперь Максим провёл турнир для N команд из своей школы и должен определить победителя. Он неаккуратно вёл записи игры и не отмечал, сколько слов отгадала каждая из команд, зато он записывал в хронологическом порядке каждый раз, когда какая-либо команда доставала какую-либо бумажку из шляпы. Всего таких записей M, и они следуют в хронологическом порядке. Помогите Максиму восстановить по сделанным записям, сколько слов отгадала каждая из команд. Входные данные В первой строке дано количество команд N и количество попыток отгадать слова M (1 ≤ N ≤ 100000, 1 ≤ M ≤ 100000). В следующих M строках сначала указывается номер ni команды, пытавшейся отгадать слово, а через пробел дано слово wi, написанное на бумажке. Номера команд лежат в диапазоне от 1 до N. Все слова wi состоят из строчных латинских букв и имеют ненулевую длину, не превосходящую 10 букв. Выходные данные Выведите в одну строку N чисел, i-е число должно равняться количеству слов, отгаданному i-й командой. Примеры Ввод Вывод 2 3 1 hat 1 shirt 2 hat 1 1 3 2 1 mom 3 dad 1 0 1 0

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	24.06.2020, 17:46
	В чем конкретно вопрос? Заводите словарь для ключ - слово, значение - номер команды и проверяйте было или нет слово. 0

@iSmokeJC 19530 / 11067 / 2931 Регистрация: 21.10.2017 Сообщений: 23,294
	12.09.2020, 08:49
	Ktd1231, зачем решение на плюсах в разделе питона? 2

@Ilya_Av 0 / 0 / 0 Регистрация: 02.05.2024 Сообщений: 1
	02.05.2024, 23:15
	это какие курсы надо пройти, чтобы такого рода задачи решать? Добавлено через 1 минуту Alestrange, какой материал вы изучили? интересно, что надо пройти для решения таких задач? 0