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

возможно ли всех ОВП рассадить за двумя столами? - C++

Восстановить пароль Регистрация
 
Андрей17
0 / 0 / 0
Регистрация: 28.10.2011
Сообщений: 42
15.01.2012, 13:00     возможно ли всех ОВП рассадить за двумя столами? #1
На банкет были приглашены N Очень Важных Персон (ОВП). Были поставлены 2 стола. Столы достаточно большие, чтобы все посетители банкета могли сесть за любой из них. Проблема заключается в том, что некоторые ОВП не ладят друг с другом и не могут сидеть за одним столом. Вас попросили определить, возможно ли всех ОВП рассадить за двумя столами.

Формат входных данных
В первой строке входного файла дано два числа: N и M (1 <= N,M <= 100), где N - количество ОВП, а M - количество пар ОВП, которые не могут сидеть за одним столом. В следующих M строках записано по 2 числа - пары ОВП, которые не могут сидеть за одним столом.

Формат выходных данных
Если способ рассадить ОВП существует, то в выходной файл выведите YES в первой строке и номера ОВП, которых необходимо посадить за первый стол, во второй строке. В противном случае в первой и единственной строке выведите NO.

Добавлено через 39 минут
помогите очень надо
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
15.01.2012, 13:00     возможно ли всех ОВП рассадить за двумя столами?
Посмотрите здесь:

C++ Структуры. По запросу выдать: всех женщин, сменивших свою фамилию, всех военнообязанных, всех холостых
C++ Вывод всех чисел, находящихся между двумя заданными числами
C++ Вычислить сумму всех чисел, лежащих между двумя целыми
Составить программу вычисления количества всех делителей всех чисел от 1 до n C++
C++ Вычислить сумму всех целых чисел, лежащих между двумя целыми числами, выбранными пользователем
Найти сумму всех отрицательных, и произведение всех положительных элементов матрицы C++
C++ Найти способы рассадить заданное количество флегматичных и меланхоличных ленивцев по вольерам
Найти способы рассадить заданное количество флегматичных и меланхоличных ленивцев по вольерам C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Mr.X
Эксперт С++
 Аватар для Mr.X
2807 / 1583 / 248
Регистрация: 03.05.2010
Сообщений: 3,693
16.01.2012, 14:21     возможно ли всех ОВП рассадить за двумя столами? #2
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
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
/////////////////////////////////////////////////////////////////////////////////////////
//На банкет были приглашены N Очень Важных Персон (ОВП). Были поставлены 2 стола. 
//Столы достаточно большие, чтобы все посетители банкета могли сесть за любой из них. 
//Проблема заключается в том, что некоторые ОВП не ладят друг с другом и не могут 
//сидеть за одним столом. Вас попросили определить, возможно ли всех ОВП рассадить 
//за двумя столами.
//
//Формат входных данных
//В первой строке входного файла дано два числа: N и M (1 <= N,M <= 100), 
//где N - количество ОВП, а M - количество пар ОВП, которые не могут сидеть 
//за одним столом. В следующих M строках записано по 2 числа - пары ОВП, которые 
//не могут сидеть за одним столом.
//
//Формат выходных данных
//Если способ рассадить ОВП существует, то в выходной файл выведите YES в первой строке 
//и номера ОВП, которых необходимо посадить за первый стол, во второй строке. 
//В противном случае в первой и единственной строке выведите NO.
//Пример
//input.txt     
//3 2
//1 2
//1 3
//  
//output.txt
//YES
//2 3
/////////////////////////////////////////////////////////////////////////////////////////
#include <algorithm>
#include <fstream>
#include <iostream>
#include <list>
#include <map>
#include <set>
#include <string>
#include <vector>
/////////////////////////////////////////////////////////////////////////////////////////
typedef std::string                         T_str;
typedef size_t                              T_person;
typedef std::list<T_person>                 T_bad_persons;
typedef std::map<T_person, T_bad_persons>   T_bad_persons_for_person;
/////////////////////////////////////////////////////////////////////////////////////////
const T_person  PERSON_MIN = 1;
/////////////////////////////////////////////////////////////////////////////////////////
enum  T_table
{
    NO_TABLE = 0,
    TABLE_1,
    TABLE_2
};
/////////////////////////////////////////////////////////////////////////////////////////
typedef std::map<T_person, T_table>         T_table_of_person;
/////////////////////////////////////////////////////////////////////////////////////////
bool  successfully_depth_first_search
    (
        T_person                            person,
        const T_bad_persons_for_person&     bad_persons_for_person,
        T_table_of_person&                  table_of_person
    )
{    
    if(table_of_person[person] == NO_TABLE)
    {
        table_of_person[person] = TABLE_1;
    }    
    
    T_bad_persons_for_person::const_iterator  
        person_and_bad_persons_it = bad_persons_for_person.find(person);
 
    if( person_and_bad_persons_it == bad_persons_for_person.end() )
    {
        return  true;
    }
 
    T_bad_persons  bad_persons = person_and_bad_persons_it->second;
    
    for(
        T_bad_persons::const_iterator 
        bad_person_it = bad_persons.begin();
        bad_person_it != bad_persons.end();
        ++bad_person_it
       )
    {
        if(
            table_of_person[*bad_person_it] == table_of_person[person]  
          )
        {
            return  false;
        }
        else if(
                table_of_person[*bad_person_it] == NO_TABLE
               )
        {
            table_of_person[*bad_person_it] =   table_of_person[person] == TABLE_1
                                                    ? TABLE_2
                                                    : TABLE_1;
 
            if(
                !successfully_depth_first_search
                    (
                        *bad_person_it,
                        bad_persons_for_person,
                        table_of_person
                    )  
              )
            {
                return  false;
            }
        }//else if    
    }//for
    return  true;
}
/////////////////////////////////////////////////////////////////////////////////////////
bool  successfully_to_seat
    (
        const T_bad_persons_for_person&     bad_persons_for_person,
        T_table_of_person&                  table_of_person        
    )
{    
    for(T_table_of_person::iterator  person_and_table_it = table_of_person.begin();
        person_and_table_it != table_of_person.end(); ++person_and_table_it)
    {
        if(person_and_table_it->second != NO_TABLE) continue;
        
        if(
            !successfully_depth_first_search
                (
                    person_and_table_it->first,
                    bad_persons_for_person,
                    table_of_person
                ) 
          )
        {
            return  false;
        }       
    }
    return  true;
}
/////////////////////////////////////////////////////////////////////////////////////////
void  input_persons_data
        (
            const T_str&                ifile_name,
            T_table_of_person&          table_of_person,
            T_bad_persons_for_person&   bad_persons_for_person
        )
{
    std::ifstream   ifile( ifile_name.c_str() );
 
    int  persons_total          = 0;
    ifile >> persons_total;
 
    for(T_person  person = PERSON_MIN; person <= persons_total; ++person)
    {
        table_of_person[person] = NO_TABLE;
    }
    
    int  persons_pairs_total    = 0;
    ifile >> persons_pairs_total;
 
    for(int  i = 0; i < persons_pairs_total; ++i)
    {
        int  L = 0;
        ifile >> L;        
 
        int  R = 0;
        ifile >> R;        
        
        bad_persons_for_person[L].push_back(R);
        bad_persons_for_person[R].push_back(L);
    } 
}
/////////////////////////////////////////////////////////////////////////////////////////
void  print_persons_placement_at_tables
    (
        const T_str&                ofile_name,
        bool                        persons_are_successfully_seated,        
        const T_table_of_person&    table_of_person
    )
{
    std::ofstream   ofile( ofile_name.c_str() );
    ofile   <<  (
                    persons_are_successfully_seated 
                        ? "YES" 
                        : "NO"
                )
 
            << std::endl;               
 
    if(persons_are_successfully_seated)
    {
        for(T_table_of_person::const_iterator  person_and_table_it = table_of_person.begin();
            person_and_table_it != table_of_person.end(); ++person_and_table_it)
        {
            if(person_and_table_it->second == TABLE_1)
            {
                ofile   << person_and_table_it->first
                        << " ";
            }
        }
        ofile << std::endl;
    }
}
/////////////////////////////////////////////////////////////////////////////////////////
int main()
{
    const T_str     ifile_name = "input.txt";           
    const T_str     ofile_name = "output.txt";
 
    
    T_bad_persons_for_person    bad_persons_for_person;
    T_table_of_person           table_of_person;
 
    input_persons_data
        (
            ifile_name,
            table_of_person,
            bad_persons_for_person
        );   
 
    bool        bool_res =  successfully_to_seat
                                (
                                    bad_persons_for_person,
                                    table_of_person                                    
                                );
 
    print_persons_placement_at_tables
        (
            ofile_name,
            bool_res,            
            table_of_person
        );                    
}
Yandex
Объявления
16.01.2012, 14:21     возможно ли всех ОВП рассадить за двумя столами?
Ответ Создать тему
Опции темы

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