Форум программистов, компьютерный форум CyberForum.ru

Сколько легендарных команд можно создать из заданного числа людей? - C++

Восстановить пароль Регистрация
 
WalkRight
0 / 0 / 0
Регистрация: 04.11.2015
Сообщений: 12
14.05.2016, 13:32     Сколько легендарных команд можно создать из заданного числа людей? #1
Подскажите алгоритм к этой задаче или даже можно решение. А то всю голову сломал, не идет.
Ничто не старит нас так, как годы. Много замечательных соревнований прошло, многие программисты — больше не студенты, и поэтому не могут участвовать в соревнованиях. Хотя их дух так же свеж и молод, как и годы назад! Поэтому однажды они решили организовать в Уральском государственном университете соревнование среди лучших команд прошлых лет…
Чтобы сделать соревнование интересным, они решили пригласить как можно больше "легендарных" команд. Жюри подготовило список команд, показывавших лучшие результаты в старые добрые времена, тем самым заслуживших право называться "легендарными". Все эти команды были приглашены на соревнование, и все они приняли приглашение. Но в жюри забыли одну важную вещь: в течение долгой истории соревнований в университете состав команд мог меняться, и некоторые программисты участвовали в составе различных "легендарных" команд. Тем не менее, жюри решило не оставлять исходную идею и сформировать для участия в соревновании как можно больше легендарных команд — и ваша программа должна помочь жюри!
Исходные данные
Первая строка содержит целое число K, 1 ≤ K ≤ 18 — количество легендарных команд. В следующих K строках следуют описания команд. Каждая строка содержит три имени членов соответствующей команды. Все имена записаны не более чем 20 строчными латинскими буквами.
Результат
Выведите максимально возможное количество легендарных команд, которые смогут одновременно участвовать в соревновании.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
14.05.2016, 13:32     Сколько легендарных команд можно создать из заданного числа людей?
Посмотрите здесь:

Создать массив из индексов элементов матрицы, меньших заданного числа C++
C++ Определять, сколько чисел в файле больше заданного пользователем числа
Создать функцию, вычисляющую логарифм заданного числа по заданному основанию. C++
C++ Найти количество различных чисел, которые можно получить из числа ровно за C команд
Можно ли внутри функции f_1 создать массив размера, заданного аргументом n_1? C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
fire_Rising
 Аватар для fire_Rising
10 / 11 / 2
Регистрация: 11.05.2016
Сообщений: 111
14.05.2016, 13:47     Сколько легендарных команд можно создать из заданного числа людей? #2
Тебе надо описать ввод этих К строк. Тут решается через записи, перечисляемый тип.
Т.е. тебе надо ввести 18*3 имен членов этих команд и просто описать это в коде.

Как я понял, поправьте, если что-то не уловил)
IGPIGP
Комп_Оратор)
 Аватар для IGPIGP
6162 / 2891 / 282
Регистрация: 04.12.2011
Сообщений: 7,691
Записей в блоге: 3
14.05.2016, 14:21     Сколько легендарных команд можно создать из заданного числа людей? #3
WalkRight, если я правильно уяснил условие то с командами в которых нет "многостаночников" нет и проблем. Пусть их N3 штук. Команд в которых по одному "многостаночнику" N2 и в которых по одному, - соответственно N1
Создаём класс троек и контейнер для него закидываем в него N3. В отдельный контейнер складываем тройки с одним нулём. И последний - контейнер "единичников" (с двумя нулями). Для сохранения максимальной аутентичности составов дополняем двоечников до троечников единичниками пока не кончатся те или другие. Полученные троечники - в контейнер троечников (готовых команд). Оставшийся неизрасходованным контейнер используем для формирования троек. Если это единичный, то всё тривиально, а если двоечный то каждая пара может стать "пищей" для следующих двух. Действуя по такой схеме можно получить максимум 2-х незадействованных участников.

Добавлено через 11 минут
Цитата Сообщение от IGPIGP Посмотреть сообщение
Действуя по такой схеме можно получить максимум 2-х незадействованных участников.
то есть если я правильно, опять же понял, то зная числа N1, N2, N3 , можно посчитать команды и без контейнеров:
Если N1 > N2
N= N3+N2+(N1-N2)/3
Если N2 > N1
N= N3+N1+((N2-N1)*2)/3
если равно то N= N3+N2
Mr.X
Эксперт С++
 Аватар для Mr.X
2798 / 1574 / 246
Регистрация: 03.05.2010
Сообщений: 3,651
15.05.2016, 19:54     Сколько легендарных команд можно создать из заданного числа людей? #4
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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
//Ничто не старит нас так, как годы. Много замечательных соревнований прошло,
//многие программисты — больше не студенты, и поэтому не могут участвовать
//в соревнованиях. Хотя их дух так же свеж и молод, как и годы назад! Поэтому
//однажды они решили организовать в Уральском государственном университете
//соревнование среди лучших команд прошлых лет…
//Чтобы сделать соревнование интересным, они решили пригласить как можно больше
//"легендарных" команд. Жюри подготовило список команд, показывавших лучшие
//результаты в старые добрые времена, тем самым заслуживших право называться
//"легендарными". Все эти команды были приглашены на соревнование, и все они
//приняли приглашение. Но в жюри забыли одну важную вещь: в течение долгой
//истории соревнований в университете состав команд мог меняться, и некоторые
//программисты участвовали в составе различных "легендарных" команд. Тем не менее,
//жюри решило не оставлять исходную идею и сформировать для участия в соревновании
//как можно больше легендарных команд — и ваша программа должна помочь жюри!
 
//Исходные данные
//Первая строка содержит целое число K, 1 ≤ K ≤ 18 — количество легендарных команд.
//В следующих K строках следуют описания команд. Каждая строка содержит три имени
//членов соответствующей команды. Все имена записаны не более чем 20 строчными
//латинскими буквами.
 
//Результат
//Выведите максимально возможное количество легендарных команд, которые смогут
//одновременно участвовать в соревновании.
///////////////////////////////////////////////////////////////////////////////
#include <array>
#include <iostream>
#include <map>
#include <set>
#include <string>
#include <vector>
///////////////////////////////////////////////////////////////////////////////
static  const   int     TEAM_SIZE   =   3;
///////////////////////////////////////////////////////////////////////////////
typedef std::string                                         T_programmer;
typedef std::array      < T_programmer,  TEAM_SIZE      >   T_team;
typedef std::vector     < T_team        >                   T_teams;
typedef std::set        < T_programmer  >                   T_all_programmers;
typedef size_t                                              T_team_ind;
typedef size_t                                              T_progr_ind;
typedef std::map        < T_team_ind,   T_progr_ind     >   T_progr_ind_of_team_ind;
///////////////////////////////////////////////////////////////////////////////
bool    successfully_inc_progr_ind_or_clear_and_return_false
    (
        T_teams             const   &   teams,
        T_all_programmers           &   all_programmers,
        T_progr_ind_of_team_ind     &   progr_ind_of_team_ind,
        int                             team_ind
    )
{
    auto    &   progr_ind_ref   =   progr_ind_of_team_ind[ team_ind ];
 
    if( progr_ind_ref )
    {
        all_programmers.insert
            (
                teams[ team_ind ][ progr_ind_ref - 1 ]
            );
    }//if
 
    ++progr_ind_ref;
 
    for (
            ;
            progr_ind_ref   <=  TEAM_SIZE;
            ++progr_ind_ref
        )
    {
        auto    const   &   cur_progr   =   teams[ team_ind ][ progr_ind_ref - 1 ];
 
        if  (
                all_programmers.count( cur_progr )
            )
        {
            all_programmers.erase( cur_progr );
            return  true;
        }//if
    }//for
 
    progr_ind_ref   =   0;
    return  false;
}
///////////////////////////////////////////////////////////////////////////////
int     teams_count_max
    (
        T_teams             const   &   teams,
        T_all_programmers               all_programmers
    )
{
    int     res{};
 
    if  (
            !teams.size()
        )
    {
        return  res;
    }//if
 
    int     team_ind_max
                {
                        int (
                                teams.size()
                            )
 
                    -   1
                };
 
    T_progr_ind_of_team_ind     progr_ind_of_team_ind;
 
    for (
            int  team_ind{};;
        )
    {
        if  (
                successfully_inc_progr_ind_or_clear_and_return_false
                    (
                        teams,
                        all_programmers,
                        progr_ind_of_team_ind,
                        team_ind
                    )
            )
        {
            if  (
                        !res
 
                    ||      team_ind    +   1
                        >   res
                )
            {
                res     =   team_ind    +   1 ;
            }//if
 
            if  (
                        team_ind
                    ==  team_ind_max
                )
            {
                break;
            }//if
 
            ++team_ind;
        }
        else
        {
            if  (
                    team_ind    ==  0
                )
            {
                break;
            }
 
            --team_ind;
        }//else
    }//for
 
    return  res;
}
///////////////////////////////////////////////////////////////////////////////
int     main()
{
    int                 teams_total{};
    std::cin    >>      teams_total;
 
    T_teams             teams( teams_total );
    T_all_programmers   all_programmers;
 
    for (
            auto    &   team    :
            teams
        )
    {
        for (
                auto    &   programmer  :
                team
            )
        {
            std::cin    >>  programmer;
            all_programmers.insert( programmer );
        }//for
    }//for
 
    std::cout   <<  teams_count_max
                        (
                            teams,
                            all_programmers
                        )
 
                <<  std::endl;
}
Yandex
Объявления
15.05.2016, 19:54     Сколько легендарных команд можно создать из заданного числа людей?
Ответ Создать тему
Опции темы

Текущее время: 15:03. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru