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

C# для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 13, средняя оценка - 4.77
CoRReS
0 / 0 / 0
Регистрация: 17.10.2012
Сообщений: 62
#1

Задача про больных - C#

25.04.2013, 15:51. Просмотров 1885. Ответов 34
Метки нет (Все метки)

Братья программисты,помогите решить данную задачу,алгоритм я впринципе придумал,а реализовать не могу вообще...

Прошу кто шарит,накиньте программку для этой задачи,очень прошу!

Заранее спасибо!

В связи с эпидемией гриппа в больницу направляется А больных гриппом “А” и В больных гриппом “B”. Больных гриппом “А” нельзя помещать в одну палату с больными гриппом “B”. Имеется информация об общем количестве палат P в больнице, пронумерованных от 1 до P, и о распределении уже имеющихся там больных. Необходимо определить максимальное количество больных M, которое больница в состоянии принять. При размещении новых больных не разрешается переселять уже имеющихся больных из палаты в палату.

Входные данные находятся в текстовом файле с именем input.txt и имеют следующую структуру:

в первой строке находится целое число A (0 ≤ A ≤ 150);
во второй строке — целое число B (0 ≤ B ≤ 100);
в третьей строке — натуральное число P (P ≤ 20);
в каждой из последующих P строк находятся 3 числа n, a, b, разделенных пробелом, где n — вместимость палаты, a — количество уже имеющихся в палате больных гриппом “А”, b — количество уже имеющихся в палате больных гриппом “B”. Информация о вместимости палат вводится последовательно для палат с номерами 1, 2, …, P. Числа n, a, b — целые неотрицательные, меньшие 100.

Выходные данные должны быть записаны в текстовый файл с именем output.txt и иметь следующий формат:

в первой строке должно находиться число M;
если все поступившие больные размещены, то во второй строке должны находиться номера палат, разделенные пробелом, куда помещаются больные гриппом “А” (в порядке возрастания).

Пример входных данных

10
7
3
5 2 0
4 0 1
8 0 0

Пример выходных данных
13
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
25.04.2013, 15:51
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Задача про больных (C#):

Задача про парикмахера - C#
Для каждого посетителя парикмахерской (с одним мастером) известны следующие величины: t – момент его прихода и τ – продолжительность его...

Задача про драконов - C#
Условие: У каждой S-ножки 1 голова. Найти количество ног N у K-главого дракона, если у всех вместе A голов и B ног. Технические...

задача про прямые - C#
Прямая на плоскости может быть задана уравнением ax + by = c, где a, b одновременно не равны нулю, a, b, c — целые. Пусть даны коэффициенты...

Задача про лыжника - C#
Готовясь к соревнованиям, лыжник в первый день побежал 10 км, затем каждый день увеличивал расстояние на 10%. Сколько километров пробежал...

Задача про спортсмена - C#
Начав тренировки, спортсмен пробежал в первый день 10 км. Каждый следующий день он увеличивал дневную норму на 10 % от нормы предыдущего...

Задача про бутылки - C#
Есть бутылки с разным количеством литров. Первое число при вводе - количество бутылок, второе - сколько в ней литров. Если бутылка пустая...

34
dev-a1056
228 / 95 / 4
Регистрация: 16.04.2013
Сообщений: 315
Записей в блоге: 2
26.04.2013, 08:29 #16
Цитата Сообщение от NewBeginner Посмотреть сообщение
А что если этого файла еще нету?
а его и так нет, но будет.
Цитата Сообщение от NewBeginner Посмотреть сообщение
3+3+8 = 14,
, а должно быть 3 + 3 + 7 или 8 + 2 + 3.
причем даже в условии это есть.
Цитата Сообщение от NewBeginner Посмотреть сообщение
Костыльный вариант с подбитием результатов
для тестовой системы будишь подбирать на более 1000 тестов?

Ну в общем ты ни когда не решал подобного рода алгоритмических задач на соревнованиях по программированию - советую, никогда не поздно начать. На много интереснее, чем писать унылый код(его и на работе хватает). вот хорошая ссылка http://codeforces.ru/ тут можно решать, участвовать в соревнованиях, смотреть разборы задач и еще много всего полезного.
2
NewBeginner
16 / 14 / 1
Регистрация: 28.03.2013
Сообщений: 54
26.04.2013, 10:04 #17
а его и так нет, но будет.
был не прав прошу прощения...
5 2 0
4 0 1
8 0 0
5-2=3+
4-1=3+
8-0=8=14 я не знаю как по другому посчитать... покажите пожалуйста, а то так и помру бездарем...

для тестовой системы будишь подбирать на более 1000 тестов?
Бог милостив поэтому мне это не грозит.

За наставления очень признателен - спасибо!

Добавлено через 33 минуты
покажите пожалуйста, а то так и помру бездарем...
Все... не надо показывать - я и сам уже понял что я безнадежен... Все верно 13.
0
dev-a1056
228 / 95 / 4
Регистрация: 16.04.2013
Сообщений: 315
Записей в блоге: 2
26.04.2013, 13:22 #18
Цитата Сообщение от NewBeginner Посмотреть сообщение
что я безнадежен.
если понял, значит это не так. Удачи и это хорошо, что разбираешь решения, а не принимаешь на веру.
2
CoRReS
0 / 0 / 0
Регистрация: 17.10.2012
Сообщений: 62
26.04.2013, 17:03  [ТС] #19
Цитата Сообщение от dev-a1056 Посмотреть сообщение
если понял, значит это не так. Удачи и это хорошо, что разбираешь решения, а не принимаешь на веру.
К сожалению тесты не все проходят,но что не так я не могу сказать,ибо проверяет бездушная тестилка
0
dev-a1056
228 / 95 / 4
Регистрация: 16.04.2013
Сообщений: 315
Записей в блоге: 2
26.04.2013, 18:47 #20
CoRReS, кинь ссылку.

Добавлено через 26 секунд
сейчас отладим. какой номер теста?

Добавлено через 4 минуты
о я, кажется понял..


Добавлено через 3 минуты
а теперь дошло совсем. Мое решение неверное в корне и все таки жадность тут не поможет.
0
NewBeginner
16 / 14 / 1
Регистрация: 28.03.2013
Сообщений: 54
26.04.2013, 18:58 #21
Цитата Сообщение от dev-a1056 Посмотреть сообщение
Мое решение неверное в корне
Но всеравно классное

Добавлено через 1 минуту
Мне особенно вот эта строка понравилась я не знал что так можно...
Цитата Сообщение от dev-a1056 Посмотреть сообщение
string[] ss = reader.ReadLine().Split();
0
CoRReS
0 / 0 / 0
Регистрация: 17.10.2012
Сообщений: 62
26.04.2013, 19:15  [ТС] #22
Цитата Сообщение от dev-a1056 Посмотреть сообщение
CoRReS, кинь ссылку.

Добавлено через 26 секунд
сейчас отладим. какой номер теста?

Добавлено через 4 минуты
о я, кажется понял..


Добавлено через 3 минуты
а теперь дошло совсем. Мое решение неверное в корне и все таки жадность тут не поможет.
Ссылку не как не кину,это универская лажа...

Короче 7 из 10 тестов проходит,а 3 нет

Пишет неправильный ответ (2)
0
dev-a1056
228 / 95 / 4
Регистрация: 16.04.2013
Сообщений: 315
Записей в блоге: 2
26.04.2013, 21:15 #23
CoRReS, хм.. если 7 из 10, то похоже это какой-то граничный случай. Подумаю, чуть позже.

Добавлено через 20 минут
одну багу нашел:

0
8
3
5 2 0
4 0 1
8 0 0

вот на этом тесте неправильный ответ. сейчас поправлю

Добавлено через 6 минут
пробуй вот этот код сдать. и пиши о результатах, все таки в алгоритме пока проблем не вижу.
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
using System;
using System.Collections.Generic;
using System.IO;
 
namespace PatientProblem
{
    class Program
    {
        struct Ward : IComparable<Ward>
        {
            public int No;
            public int Capacity;
 
            public int CompareTo(Ward other)
            {
                return -1 * Capacity.CompareTo(other.Capacity);
            }
        }
        private static List<Ward> _wa;
        private static List<Ward> _wb;
        private static List<Ward> _wc;
        private static int _a;
        private static int _b;
 
        static void Main()
        {
            using (var sr = new StreamReader("input.txt"))
                ReadData(sr);
            using (var sw = new StreamWriter("output.txt"))
                PrintResult(sw);
        }
 
        private static bool Resolve(out List<int> res, out int m)
        {
            m = _a + _b;
            res = new List<int>();
            bool f1 = _a == 0 || PutA(res);
            bool f2 = _b == 0 || PutB();
            if (f1 && f2)
                return true;
            if (!PutC(res))
            {
                m = m - (_a + _b);
                return false;
            }
            return true;
        }
 
        private static bool PutC(List<int> res)
        {
            foreach (var w in _wc)
            {
                if (_a > _b)
                {
                    int t = _a - w.Capacity;
                    _a -= t < 0 ? _a : w.Capacity;
                    res.Add(w.No);
                }
                else
                {
                    int t = _b - w.Capacity;
                    _b -= t < 0 ? _b : w.Capacity;
                }
                if (_a + _b == 0) return true;
            }
            return false;
        }
 
        private static bool PutB()
        {
            foreach (var w in _wa)
                _b -= w.Capacity;
            _b = _b < 0 ? 0 : _b;
            return _b == 0;
        }
 
        private static bool PutA(List<int> res)
        {
            foreach (var w in _wa)
            {
                int t = _a - w.Capacity;
                res.Add(w.No);
                if (t <= 0)
                {
                    _a = 0;
                    break;
                }
                _a -= w.Capacity;
            }
            return _a == 0;
        }
 
        private static void PrintResult(TextWriter writer)
        {
            List<int> res;
            int m;
            if (Resolve(out res, out m) && m != 0)
            {
                res.Sort();
                writer.WriteLine(m);
                if(res.Count > 0)
                    writer.WriteLine(string.Join(" ", res)); //net 4.0 и выше
            }
            else
            {
                writer.WriteLine(m);
            }
        }
 
        private static void ReadData(TextReader reader)
        {
            _a = int.Parse(reader.ReadLine());
            _b = int.Parse(reader.ReadLine());
            int p = int.Parse(reader.ReadLine());
            _wa = new List<Ward>(p);
            _wb = new List<Ward>(p);
            _wc = new List<Ward>(p);
            for (int i = 0; i < p; ++i)
            {
                string[] ss = reader.ReadLine().Split();
                int n = int.Parse(ss[0]);
                int a = int.Parse(ss[1]);
                int b = int.Parse(ss[2]);
                var w = new Ward { No = i + 1, Capacity = n - a - b };
                if (a > 0)
                {
                    _wa.Add(w);
                }
                else if (b > 0)
                {
                    _wb.Add(w);
                }
                else
                {
                    _wc.Add(w);
                }
            }
            _wa.Sort();
            _wc.Sort();
        }
    }
}
Добавлено через 14 минут
должна пройти. больше проблем не вижу.
0
CoRReS
0 / 0 / 0
Регистрация: 17.10.2012
Сообщений: 62
26.04.2013, 23:16  [ТС] #24
Цитата Сообщение от dev-a1056 Посмотреть сообщение
CoRReS, хм.. если 7 из 10, то похоже это какой-то граничный случай. Подумаю, чуть позже.

Добавлено через 20 минут
одну багу нашел:

0
8
3
5 2 0
4 0 1
8 0 0

вот на этом тесте неправильный ответ. сейчас поправлю



Добавлено через 6 минут
пробуй вот этот код сдать. и пиши о результатах, все таки в алгоритме пока проблем не вижу.
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
using System;
using System.Collections.Generic;
using System.IO;
 
namespace PatientProblem
{
    class Program
    {
        struct Ward : IComparable<Ward>
        {
            public int No;
            public int Capacity;
 
            public int CompareTo(Ward other)
            {
                return -1 * Capacity.CompareTo(other.Capacity);
            }
        }
        private static List<Ward> _wa;
        private static List<Ward> _wb;
        private static List<Ward> _wc;
        private static int _a;
        private static int _b;
 
        static void Main()
        {
            using (var sr = new StreamReader("input.txt"))
                ReadData(sr);
            using (var sw = new StreamWriter("output.txt"))
                PrintResult(sw);
        }
 
        private static bool Resolve(out List<int> res, out int m)
        {
            m = _a + _b;
            res = new List<int>();
            bool f1 = _a == 0 || PutA(res);
            bool f2 = _b == 0 || PutB();
            if (f1 && f2)
                return true;
            if (!PutC(res))
            {
                m = m - (_a + _b);
                return false;
            }
            return true;
        }
 
        private static bool PutC(List<int> res)
        {
            foreach (var w in _wc)
            {
                if (_a > _b)
                {
                    int t = _a - w.Capacity;
                    _a -= t < 0 ? _a : w.Capacity;
                    res.Add(w.No);
                }
                else
                {
                    int t = _b - w.Capacity;
                    _b -= t < 0 ? _b : w.Capacity;
                }
                if (_a + _b == 0) return true;
            }
            return false;
        }
 
        private static bool PutB()
        {
            foreach (var w in _wa)
                _b -= w.Capacity;
            _b = _b < 0 ? 0 : _b;
            return _b == 0;
        }
 
        private static bool PutA(List<int> res)
        {
            foreach (var w in _wa)
            {
                int t = _a - w.Capacity;
                res.Add(w.No);
                if (t <= 0)
                {
                    _a = 0;
                    break;
                }
                _a -= w.Capacity;
            }
            return _a == 0;
        }
 
        private static void PrintResult(TextWriter writer)
        {
            List<int> res;
            int m;
            if (Resolve(out res, out m) && m != 0)
            {
                res.Sort();
                writer.WriteLine(m);
                if(res.Count > 0)
                    writer.WriteLine(string.Join(" ", res)); //net 4.0 и выше
            }
            else
            {
                writer.WriteLine(m);
            }
        }
 
        private static void ReadData(TextReader reader)
        {
            _a = int.Parse(reader.ReadLine());
            _b = int.Parse(reader.ReadLine());
            int p = int.Parse(reader.ReadLine());
            _wa = new List<Ward>(p);
            _wb = new List<Ward>(p);
            _wc = new List<Ward>(p);
            for (int i = 0; i < p; ++i)
            {
                string[] ss = reader.ReadLine().Split();
                int n = int.Parse(ss[0]);
                int a = int.Parse(ss[1]);
                int b = int.Parse(ss[2]);
                var w = new Ward { No = i + 1, Capacity = n - a - b };
                if (a > 0)
                {
                    _wa.Add(w);
                }
                else if (b > 0)
                {
                    _wb.Add(w);
                }
                else
                {
                    _wc.Add(w);
                }
            }
            _wa.Sort();
            _wc.Sort();
        }
    }
}
Добавлено через 14 минут
должна пройти. больше проблем не вижу.



Не проходят те же тесты
0
Миниатюры
Задача про больных  
dev-a1056
228 / 95 / 4
Регистрация: 16.04.2013
Сообщений: 315
Записей в блоге: 2
26.04.2013, 23:50 #25
ну ок. напишу полный перебор и найду ошибку входные данные позволяют
0
CoRReS
0 / 0 / 0
Регистрация: 17.10.2012
Сообщений: 62
27.04.2013, 00:00  [ТС] #26
Цитата Сообщение от dev-a1056 Посмотреть сообщение
ну ок. напишу полный перебор и найду ошибку входные данные позволяют
Спасибо,просто у нас по алгоритмам у всех разная,и вот эта такая конченная задача...просто жесть я ей алгоритм неделю сдавал)))
0
dev-a1056
228 / 95 / 4
Регистрация: 16.04.2013
Сообщений: 315
Записей в блоге: 2
27.04.2013, 03:34 #27
10
7
3
5 0 0
4 0 0
8 0 0
вот этот тест обламывает мое решение.
Как верно заметил мой друг shuffle - эта классическая задача о рюкзаке. И он предложил динамику для этого решения. И т.к. идея его, я думаю он и выложит решение

Я же решил задачу откровенно в лоб, просто перебрав все возможные варианты, за 2^20 в худшем случае т.е. O(2^P);
Решение абсолютно криворукое, т.к. это костыль в уже предложенное решение и могут быть баги в реализации, но попробовать сдать можно.
если пройдет OK, иначе будем писать динамику или отлаживать эту писанину.
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
#define _PRINT_RES
#undef _PRINT_RES
#define _RESOLVE_1
#undef _RESOLVE_1
 
using System;
using System.Collections.Generic;
using System.IO;
 
namespace PatientProblem
{
    internal class Program
    {
        private struct Ward : IComparable<Ward>
        {
            public int No;
            public int Capacity;
 
            public int CompareTo(Ward other)
            {
                return -1*Capacity.CompareTo(other.Capacity);
            }
        }
 
        private static List<Ward> _wa;
        private static List<Ward> _wb;
        private static List<Ward> _wc;
        private static int _a;
        private static int _b;
 
        private static void Main()
        {
            using (var sr = new StreamReader("input.txt"))
                ReadData(sr);
            using (var sw = new StreamWriter("output.txt"))
                PrintResult(sw);
            
        }
 
        private static bool Resolve(out List<int> res, out int m)
        {
            m = _a + _b;
            res = new List<int>();
            bool f1 = _a == 0 || PutA(res);
            bool f2 = _b == 0 || PutB();
            if (f1 && f2)
                return true;
#if _RESOLVE_1
            if (!PutC(res))
            {
                m = m - (_a + _b);
                return false;
            }
            return true;
#else
            int max = FindMax(res) + m - _a - _b;
            bool result = (m - max) == 0;
            m = max;
#if _PRINT_RES
            return true;
#else
            return result;
#endif
#endif
        }
 
        private static bool PutC(List<int> res)
        {
            foreach (Ward w in _wc)
            {
                if (_a > _b)
                {
                    int t = _a - w.Capacity;
                    _a -= t < 0 ? _a : w.Capacity;
                    res.Add(w.No);
                }
                else
                {
                    int t = _b - w.Capacity;
                    _b -= t < 0 ? _b : w.Capacity;
                }
                if (_a + _b == 0) return true;
            }
            return false;
        }
 
        private static bool PutB()
        {
            foreach (Ward w in _wa)
                _b -= w.Capacity;
            _b = _b < 0 ? 0 : _b;
            return _b == 0;
        }
 
        private static bool PutA(List<int> res)
        {
            foreach (Ward w in _wa)
            {
                int t = _a - w.Capacity;
                res.Add(w.No);
                if (t <= 0)
                {
                    _a = 0;
                    break;
                }
                _a -= w.Capacity;
            }
            return _a == 0;
        }
 
        private static void PrintResult(TextWriter writer)
        {
            List<int> res;
            int m;
            if (Resolve(out res, out m) && m != 0)
            {
                res.Sort();
                writer.WriteLine(m);
                if (res.Count > 0)
                    writer.WriteLine(string.Join(" ", res)); //net 4.0 и выше
            }
            else
            {
                writer.WriteLine(m);
            }
        }
 
        private static void ReadData(TextReader reader)
        {
            _a = int.Parse(reader.ReadLine());
            _b = int.Parse(reader.ReadLine());
            int p = int.Parse(reader.ReadLine());
            _wa = new List<Ward>(p);
            _wb = new List<Ward>(p);
            _wc = new List<Ward>(p);
            for (int i = 0; i < p; ++i)
            {
                string[] ss = reader.ReadLine().Split();
                int n = int.Parse(ss[0]);
                int a = int.Parse(ss[1]);
                int b = int.Parse(ss[2]);
                var w = new Ward {No = i + 1, Capacity = n - a - b};
                if (a > 0)
                {
                    _wa.Add(w);
                }
                else if (b > 0)
                {
                    _wb.Add(w);
                }
                else
                {
                    _wc.Add(w);
                }
            }
#if _RESOLVE_1
            _wa.Sort();
            _wc.Sort();
#endif
        }
 
        private static bool NextSubset(bool[] b)
        {
            int i;
            for (i = 0; i < b.Length && b[i]; ++i)
                b[i] = false;
            return i != b.Length && (b[i] = true);
 
        }
 
        //Беспощадный перебор по подмножествам
        private static int FindMax(List<int> res)
        {
            var s = new bool[_wc.Count];
            int sum = 0;
            for (int i = 0; i < s.Length; ++i) s[i] = false;
            for (int i = 0; i < _wc.Count; ++i) sum += _wc[i].Capacity;
            int max = int.MinValue;
            var p = new bool[s.Length];
            do
            {
                int a = 0;
                for (int i = 0; i < _wc.Count && a < _a; ++i)
                    if (s[i]) //A
                        a += _wc.Capacity;
                a = a > _a ? _a : a;
                int b = sum - a;
                b = b > _b ? _b : b;
                if (a + b > max)
                {
                    max = a + b;
                    Array.Copy(s, p, s.Length);
                }
            } 
            while (NextSubset(s));
#if _PRINT_RES
            bool result = true;
#else
            bool result =max == _a + _b; 
#endif
            if (result)
            {
                int t = 0;
                for (int i = 0; i < p.Length && t < _a; ++i)
                {
                    if (p[i])
                    {
                        res.Add(_wc[i].No);
                        t += _wc[i].Capacity;
                    }
                }
            }
            return max;
        }
    }
}
Добавлено через 5 минут
вот для саморазвития http://informatics.mccme.ru/moodle/m...5&chapterid=60
0
CoRReS
0 / 0 / 0
Регистрация: 17.10.2012
Сообщений: 62
27.04.2013, 13:04  [ТС] #28
Цитата Сообщение от dev-a1056 Посмотреть сообщение
10
7
3
5 0 0
4 0 0
8 0 0
вот этот тест обламывает мое решение.
Как верно заметил мой друг shuffle - эта классическая задача о рюкзаке. И он предложил динамику для этого решения. И т.к. идея его, я думаю он и выложит решение

Я же решил задачу откровенно в лоб, просто перебрав все возможные варианты, за 2^20 в худшем случае т.е. O(2^P);
Решение абсолютно криворукое, т.к. это костыль в уже предложенное решение и могут быть баги в реализации, но попробовать сдать можно.
если пройдет OK, иначе будем писать динамику или отлаживать эту писанину.
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
#define _PRINT_RES
#undef _PRINT_RES
#define _RESOLVE_1
#undef _RESOLVE_1
 
using System;
using System.Collections.Generic;
using System.IO;
 
namespace PatientProblem
{
    internal class Program
    {
        private struct Ward : IComparable<Ward>
        {
            public int No;
            public int Capacity;
 
            public int CompareTo(Ward other)
            {
                return -1*Capacity.CompareTo(other.Capacity);
            }
        }
 
        private static List<Ward> _wa;
        private static List<Ward> _wb;
        private static List<Ward> _wc;
        private static int _a;
        private static int _b;
 
        private static void Main()
        {
            using (var sr = new StreamReader("input.txt"))
                ReadData(sr);
            using (var sw = new StreamWriter("output.txt"))
                PrintResult(sw);
            
        }
 
        private static bool Resolve(out List<int> res, out int m)
        {
            m = _a + _b;
            res = new List<int>();
            bool f1 = _a == 0 || PutA(res);
            bool f2 = _b == 0 || PutB();
            if (f1 && f2)
                return true;
#if _RESOLVE_1
            if (!PutC(res))
            {
                m = m - (_a + _b);
                return false;
            }
            return true;
#else
            int max = FindMax(res) + m - _a - _b;
            bool result = (m - max) == 0;
            m = max;
#if _PRINT_RES
            return true;
#else
            return result;
#endif
#endif
        }
 
        private static bool PutC(List<int> res)
        {
            foreach (Ward w in _wc)
            {
                if (_a > _b)
                {
                    int t = _a - w.Capacity;
                    _a -= t < 0 ? _a : w.Capacity;
                    res.Add(w.No);
                }
                else
                {
                    int t = _b - w.Capacity;
                    _b -= t < 0 ? _b : w.Capacity;
                }
                if (_a + _b == 0) return true;
            }
            return false;
        }
 
        private static bool PutB()
        {
            foreach (Ward w in _wa)
                _b -= w.Capacity;
            _b = _b < 0 ? 0 : _b;
            return _b == 0;
        }
 
        private static bool PutA(List<int> res)
        {
            foreach (Ward w in _wa)
            {
                int t = _a - w.Capacity;
                res.Add(w.No);
                if (t <= 0)
                {
                    _a = 0;
                    break;
                }
                _a -= w.Capacity;
            }
            return _a == 0;
        }
 
        private static void PrintResult(TextWriter writer)
        {
            List<int> res;
            int m;
            if (Resolve(out res, out m) && m != 0)
            {
                res.Sort();
                writer.WriteLine(m);
                if (res.Count > 0)
                    writer.WriteLine(string.Join(" ", res)); //net 4.0 и выше
            }
            else
            {
                writer.WriteLine(m);
            }
        }
 
        private static void ReadData(TextReader reader)
        {
            _a = int.Parse(reader.ReadLine());
            _b = int.Parse(reader.ReadLine());
            int p = int.Parse(reader.ReadLine());
            _wa = new List<Ward>(p);
            _wb = new List<Ward>(p);
            _wc = new List<Ward>(p);
            for (int i = 0; i < p; ++i)
            {
                string[] ss = reader.ReadLine().Split();
                int n = int.Parse(ss[0]);
                int a = int.Parse(ss[1]);
                int b = int.Parse(ss[2]);
                var w = new Ward {No = i + 1, Capacity = n - a - b};
                if (a > 0)
                {
                    _wa.Add(w);
                }
                else if (b > 0)
                {
                    _wb.Add(w);
                }
                else
                {
                    _wc.Add(w);
                }
            }
#if _RESOLVE_1
            _wa.Sort();
            _wc.Sort();
#endif
        }
 
        private static bool NextSubset(bool[] b)
        {
            int i;
            for (i = 0; i < b.Length && b[i]; ++i)
                b[i] = false;
            return i != b.Length && (b[i] = true);
 
        }
 
        //Беспощадный перебор по подмножествам
        private static int FindMax(List<int> res)
        {
            var s = new bool[_wc.Count];
            int sum = 0;
            for (int i = 0; i < s.Length; ++i) s[i] = false;
            for (int i = 0; i < _wc.Count; ++i) sum += _wc[i].Capacity;
            int max = int.MinValue;
            var p = new bool[s.Length];
            do
            {
                int a = 0;
                for (int i = 0; i < _wc.Count && a < _a; ++i)
                    if (s[i]) //A
                        a += _wc.Capacity;
                a = a > _a ? _a : a;
                int b = sum - a;
                b = b > _b ? _b : b;
                if (a + b > max)
                {
                    max = a + b;
                    Array.Copy(s, p, s.Length);
                }
            } 
            while (NextSubset(s));
#if _PRINT_RES
            bool result = true;
#else
            bool result =max == _a + _b; 
#endif
            if (result)
            {
                int t = 0;
                for (int i = 0; i < p.Length && t < _a; ++i)
                {
                    if (p[i])
                    {
                        res.Add(_wc[i].No);
                        t += _wc[i].Capacity;
                    }
                }
            }
            return max;
        }
    }
}
Добавлено через 5 минут
вот для саморазвития http://informatics.mccme.ru/moodle/m...5&chapterid=60

Тут вообще 2 теста прошли

У нас на эту задачу тема динамическое программирование )
0
dev-a1056
228 / 95 / 4
Регистрация: 16.04.2013
Сообщений: 315
Записей в блоге: 2
27.04.2013, 14:39 #29
Цитата Сообщение от CoRReS Посмотреть сообщение
У нас на эту задачу тема динамическое программирование
с этого и надо было начинать. В переборе проблема реализации, а не алгоритма. Ну жди теперь когда динамику, напишу

Добавлено через 1 минуту
ну вообщем случае идея подробно изложена по ссылке, которую дал

Добавлено через 2 минуты
вообще хочется перебор заталкать скинь скрин тестов

Добавлено через 3 минуты
кстати багу нашел, все от того что лень написать нормальные тесты

Добавлено через 4 минуты
0
6
3
5 2 0
4 3 0
8 4 0

Добавлено через 6 минут
C#
1
2
3
4
5
6
7
  private static bool PutB()
        {
            foreach (var w in _wa) //!!!??? вообще тесты чудом проходили должно быть _wb
                _b -= w.Capacity;
            _b = _b < 0 ? 0 : _b;
            return _b == 0;
        }
но это не все.
0
CoRReS
0 / 0 / 0
Регистрация: 17.10.2012
Сообщений: 62
27.04.2013, 14:45  [ТС] #30
Цитата Сообщение от dev-a1056 Посмотреть сообщение
с этого и надо было начинать. В переборе проблема реализации, а не алгоритма. Ну жди теперь когда динамику, напишу

Добавлено через 1 минуту
ну вообщем случае идея подробно изложена по ссылке, которую дал

Добавлено через 2 минуты
вообще хочется перебор заталкать скинь скрин тестов

Добавлено через 3 минуты
кстати багу нашел, все от того что лень написать нормальные тесты

Добавлено через 4 минуты
0
6
3
5 2 0
4 3 0
8 4 0

Добавлено через 6 минут
C#
1
2
3
4
5
6
7
  private static bool PutB()
        {
            foreach (var w in _wa) //!!!??? вообще тесты чудом проходили должно быть _wb
                _b -= w.Capacity;
            _b = _b < 0 ? 0 : _b;
            return _b == 0;
        }
но это не все.
Буду ждать )
0
Миниатюры
Задача про больных  
27.04.2013, 14:45
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
27.04.2013, 14:45
Привет! Вот еще темы с ответами:

Задача про строку - C#
Распечатать введенную строку, заменив строчные буквы прописными и повторив дважды каждую цифру. Как решить покороче, чтобы не...

Задача про Незнайку - C#
Здравствуйте. Помогите пожалуйста со школьной задачкой. Условие: &quot;Изучая английский язык, Незнайка каждый день учит столько слов,...

Задача про точки в пространстве - C#
Никак не могу доработать, помогите, пожалуйста. Не понимаю что нужно исправлять. Текст задачи прямо в коде. // Задано множество точек M в...

Задача про последовательность чисел - C#
4. Вводится последовательность вещественных чисел, оканчивающаяся нулём, и состоящая более чем из одного ненулевого элемента. Определить,...


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

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

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