С Новым годом! Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Андрей17
0 / 0 / 0
Регистрация: 28.10.2011
Сообщений: 42
#1

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

15.01.2012, 13:00. Просмотров 1051. Ответов 1
Метки нет (Все метки)

На банкет были приглашены N Очень Важных Персон (ОВП). Были поставлены 2 стола. Столы достаточно большие, чтобы все посетители банкета могли сесть за любой из них. Проблема заключается в том, что некоторые ОВП не ладят друг с другом и не могут сидеть за одним столом. Вас попросили определить, возможно ли всех ОВП рассадить за двумя столами.

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

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

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

Определить, возможно ли всех персон рассадить за двумя столами - Free Pascal
Доброго времени суток. Есть задача: На банкет были приглашены N Очень Важных Персон (ОВП). Были поставлены 2 стола. Столы...

Два монитора с двумя независимыми рабочими столами - Видеокарты
Во общем имеется два монитора, подключенные и работают нормально, но есть один косяк, когда я разворачиваю игру на основном мониторе, и в...

Нужно сделать прогаммку переключения между двумя вертуальными рабочими столами - Delphi
Нужно сделать прогаммку переключения между двумя вертуальными рабочими столами в зависитомости от того какой ключ приложен к этому...

Запрос с двумя GROUP BY (если такое возможно) - MS Access
Вроде по логике все нормально должно проходить. --- Если по отдельности запускать с GROUP BY для каждого, то цифры адекватные. ...

QML: Возможно ли перетаскивать элементы между двумя ListView - C++ Qt
Добрый день, форумчане! Изучаю qml, и у меня возник вопрос по drag and drop. Я уже знаю как перемещать элементы в окне, как их...

Возможно ли перетаскивание элементов (drag/drop) внутри listbox и между двумя listbox? - Visual C++
Подскажите возможно ли перетаскивание элементов внутри listbox и между двумя listbox, если возможно то как осуществить dragndrop, если нет...

1
Mr.X
Эксперт С++
3051 / 1696 / 265
Регистрация: 03.05.2010
Сообщений: 3,867
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
        );                    
}
2
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
16.01.2012, 14:21
Привет! Вот еще темы с ответами:

Получение всех путей между двумя вершинами в графе - C#
Всем привет, вот мой код для поиска всевозможных путей м/у двумя вершинами: private List&lt;string&gt; dfs(Vertex current) { ...

Вычислить сумму всех чисел, лежащих между двумя целыми - C++
Нужно написать программу, которая запрашивает ввод двух целых чисел(сначала меньшее, потом большее). Затем программа должна вычислить и...

Поиск всех путей между двумя вершинами в ненагруженном графе - Prolog
Помогите пожалуйста решить задачу!!! Найти все пути между двумя вершинами в ненагруженном графе. Заранее спасибо!!!

Вывод всех чисел, находящихся между двумя заданными числами - C++
Задание: напишите программу, которая запрашивает у пользователя два числа и выводит на стандартное устройство ввода все числа, которые...


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

Или воспользуйтесь поиском по форуму:
2
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.