Шляпа

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

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

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

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

Теперь Максим провёл турнир для 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

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

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

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

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

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++

#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++

#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++

// 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

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

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=' ')

Блоги программистов
Обновление сайта www.historian.by Reglage 05.01.2025 Обещал подвести итоги 2024 года для сайта. Однако начну с того, что изменилось за неделю. Добавил краткий урок по последовательности действий при анализе вредоносных файлов и значительно улучшил урок. . .	Как использовать GraphQL в C# с HotChocolate Programming 05.01.2025 GraphQL — это современный подход к разработке API, который позволяет клиентам запрашивать только те данные, которые им необходимы. Это делает взаимодействие с API более гибким и эффективным по. . .	Модель полного двоичного суматора с помощью логических операций (python) AlexSky-coder 04.01.2025 def binSum(x:list, y:list): s=^y] p=x and y for i in range(1,len(x)): s. append((x^y)^p) p=(x and y)or(p and (x or y)) return s x=list() y=list()	Это мы не проходили, это нам не задавали...(асихронный счётчик с управляющим сигналом задержки). Hrethgir 04.01.2025 Асинхронный счётчик на сумматорах (шестиразрядный по числу диодов на плате, но наверное разрядов будет больше - восемь или шестнадцать, а диоды на старшие), так как триггеры прошли тестирование и. . .	Руководство по созданию бота для Телеграм на Python IT_Exp 04.01.2025 Боты для Телеграм представляют собой автоматизированные программы, которые выполняют различные задачи, взаимодействуя с пользователями через интерфейс мессенджера. В данной статье мы рассмотрим,. . .	Применение компонентов PrimeVue в Vue.js 3 на TypeScript BasicMan 04.01.2025 Введение в PrimeVue и настройка окружения PrimeVue представляет собой мощную библиотеку компонентов пользовательского интерфейса для Vue. js 3, которая предоставляет разработчикам богатый набор. . .
Как стать Senior developer cpp_developer 04.01.2025 В современной индустрии разработки программного обеспечения позиция Senior Developer представляет собой не просто следующую ступень карьерной лестницы, а качественно новый уровень профессионального. . .	Что известно о дате выхода Windows 12 и чего от нее ждать IT_Exp 04.01.2025 В мире технологий постоянно происходят изменения, и операционные системы не являются исключением. Windows 11, выпущенная в октябре 2021 года, принесла множество инноваций и улучшений, но. . .	Что новенького в .NET Core 9 Programming 04.01.2025 Обзор ключевых изменений в . NET Core 9 Платформа . NET Core продолжает активно развиваться, и версия 9 представляет собой значительный шаг вперед в эволюции этой технологии. Новый релиз. . .	Инструкция по установке python3.13.1 в Debian 12 AlexSky-coder 03.01.2025 sudo apt update sudo apt install build-essential zlib1g-dev libncurses5-dev libgdbm-dev libnss3-dev libssl-dev libreadline-dev libffi-dev wget. . .	Затестил триггеры. архив проекта прилагаю с GOA файлами в настройках архиватора проектов. Hrethgir 03.01.2025 В этот раз нет закольцованности, потому что от неё только глюки, как я понял, логика не вырезанная. Триггеры очень быстрые если верить измерениям с помощью анализатора от Gowin. Есть ещё регистры,. . .	Python в помощь DevOps IT_Exp 03.01.2025 Причины использования Python в работе DevOps Python стал неотъемлемой частью мира DevOps, и это не случайно. Этот язык программирования обладает множеством преимуществ, которые делают его. . .

@dmitrii2000 2 / 2 / 0 Регистрация: 03.05.2020 Сообщений: 202
		1
	Шляпа 24.06.2020, 14:22. Показов 22501. Ответов 12 Метки нет (Все метки) Шляпа Летом Максим съездил в Летнюю Какую-то Школу, где, помимо учёбы, ему очень запомнилась игра «Шляпа», в которую он вместе с друзьями играл всю смену. Опишем правила игры, которых они придерживались. Обратите внимание: эти правила немного отличаются от общепринятых. Изначально в шляпу помещают некоторое количество бумажек с написанными на них различными словами. После этого команды из двух человек по очереди и в случайном порядке начинают отгадывать слова — один член команды объясняет другому написанное на бумажке слово, не используя однокоренные. Если партнёр отгадывает его, то команде засчитывается одно очко, слово выкидывается, а команда достаёт из шляпы новое, если у неё ещё осталось время в этом раунде. Если команда не успевает отгадать очередное слово, то бумажка на которой оно написано, возвращается в шляпу, и ход передаётся какой-то случайной команде, возможно, той же самой. Игра продолжается, пока все слова из шляпы не будут отгаданы. Теперь Максим провёл турнир для 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 4580 / 2348 / 601 Регистрация: 26.11.2017 Сообщений: 5,264 Записей в блоге: 3
	24.06.2020, 17:46	2
	В чем конкретно вопрос? Заводите словарь для ключ - слово, значение - номер команды и проверяйте было или нет слово. 0

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

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