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

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

Восстановить пароль Регистрация
Другие темы раздела
C++ Обработка двумерных массивов. Указатели. http://www.cyberforum.ru/cpp-beginners/thread428519.html
Лабораторная работа №5 Обработка двумерных массивов. Указатели. Цель работы: изучение способов описания, ввода-вывода и обработки двумерных массивов, использование указателей при работе с массивами. Задание Дана целочисленная матрица размера mхn. Найти матрицу, получающуюся перестановкой столбцов (первого с последним, второго с предпоследним и т.д.). Откройте ворд, там можете поиграться с...
C++ не могу понять в чем ошибка помогите найти ошибку http://www.cyberforum.ru/cpp-beginners/thread428512.html
C++ Программирование циклов с неизвестным заранее числом повторений
Лабораторная работа №3 Программирование циклов с неизвестным заранее числом повторений Цель работы: освоение средств языка C++ для описания итерационных циклов и закрепление навыков использования их при программировании. Лабораторное задание 1. Выбрать задание, соответствующее номеру варианта. 2. Составить схему программы и разработать программу для вычисления указанной функции...
C++ Вывести все наддиагональные элементы матрицы в порядке, заданном диаграммой
Помогите решить эту задачу. Дана матрица вещественных чисел x. Составить программу, которая выводит все наддиагональные элементы этой матрицы в порядке, заданном диаграммой. Помогите пожалуйста.
C++ Посоветуйте Visual Studio http://www.cyberforum.ru/cpp-beginners/thread428492.html
Может была такая тема, я тогда извиняюсь что повторно создаю Но ближе к делу. Посоветуйте Visual Studio c такими конфигурацее компьютера: Проц: AMD Seprom 2.0ГГЦ Видео 256 МБ ОЗУ: 1,5 ГБ На Диске С места 1,5 ГБ
C++ массивы задача про отрезок в массиве А определите отрезок данной длины К с максимальной суммой элементов.сначала вводится N и К затем элеметы массива .в ответе указать позицию начала отрезка и сумму Добавлено через 25 минут помогите хоть чем то...сижу на экзамене подробнее

Показать сообщение отдельно
Mr.X
Эксперт С++
 Аватар для Mr.X
2807 / 1583 / 248
Регистрация: 03.05.2010
Сообщений: 3,696
16.01.2012, 14:21     возможно ли всех ОВП рассадить за двумя столами?
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
        );                    
}
 
Текущее время: 11:45. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru