Нужна помощь / Программирование

ReSQL.ru

Мобильная версия Контакт Правила FAQ Помощь

Гость

Войти | Регистрация | Профиль | Очистить

Новые сообщения | Избранное

Форумы | Пользователи | Статистика | Мод. лог | Поиск

Цитировать

Написать

Автор*:

Ввести пароль для входа

Тема*:

Сообщение

Данное сообщение тематическое

Сообщение содержит картинки или видео 18+

Автор:

ВНИМАНИЕ! На данном подфоруме действуют строгие правила. Удостоверьтесь, что ваше сообщение соответствует им!

Форум или тема закрыты для гостей. Необходима авторизация!

Загрузить последнюю сохраненную версию

Вложение:

Вставить как галерею

Максимальный размер вложений: 4,0 МБ, аудио/видео: 8,0 МБ. Картинки большего размера ужимаются, если возможно.

Введите код, изображенный на картинке. Если код нечитаемый, кликните картинку, чтобы загрузить другой вариант.

Отправляя сообщение, я выражаю свое согласие с правилами форума и принимаю пользовательское соглашение.

Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр

Форумы / Программирование [игнор отключен] [закрыт для гостей] / Нужна помощь

13 сообщений из 13, страница 1 из 1

Нужна помощь

#36306929

windwalker

Гость

Кто-нибудь может реализовать это в Visual C++?

Некоторые школы связаны компьютерной сетью. Каждая школа имеет список школ-получателей, которым она рассылает программное обеспечение всякий раз, получив новые бесплатные программы. При этом, если школа в есть в списке получателей школы а, то школы а может не быть в списке получателей школы в. Напишите программу, определяющую минимальное количество школ, которым надо передать по одному экземпляру нового программного обеспечения, чтобы распространить его по всем школам сети. Кроме того, надо обеспечить возможность рассылки нового программного обеспечения из любой школы по всем остальным школам. Для этого можно расширять списки получателей некоторых школ, добавляя в них новые школы. Найдите минимальное суммарное количество расширений списков, при которых программное обеспечение из любой школы достигло бы всех остальных школ. Одно расширение означает добавление одной школы-получателя в список получателей какой-либо из школ.

за ранее благодарю.

...

Рейтинг:

0 / 0

12.11.2009, 14:47:49

| Ответить | Цитировать | Написать

Нужна помощь

#36307135

MasterZiv

Участник

Откуда: Питер

Сообщения: 32 427

Рейтинг: 0 / 0

windwalker wrote:

> Кто-нибудь может реализовать это в Visual C++?

Безусловно, да. Кто-нибудь может реализовать это на С++.
С++ -- Тьюринг-полный язык, и на нём можно реализовать
любую программу.
Posted via ActualForum NNTP Server 1.4

...

Рейтинг:

0 / 0

12.11.2009, 15:49:56

| Ответить | Цитировать | Написать

Нужна помощь

#36307173

windwalker

Гость

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

...

Рейтинг:

0 / 0

12.11.2009, 16:05:42

| Ответить | Цитировать | Написать

Нужна помощь

#36307209

MasterZiv

Участник

Откуда: Питер

Сообщения: 32 427

Рейтинг: 0 / 0

windwalker wrote:
> мне нужен код, то что это можно реализовать я знаю, просто у меня нет

Так так бы и написал.
Posted via ActualForum NNTP Server 1.4

...

Рейтинг:

0 / 0

12.11.2009, 16:19:25

| Ответить | Цитировать | Написать

Нужна помощь

#36307247

windwalker

Гость

название темы "Нужна помощь",
начало поста "Кто-нибудь может реализовать это в Visual C++?"
как бы подразумевается именно надобность кода.

...

Рейтинг:

0 / 0

12.11.2009, 16:36:20

| Ответить | Цитировать | Написать

Нужна помощь

#36307258

an0nym

Участник

Сообщения: 6 235

Рейтинг: 0 / 0

windwalkerназвание темы "Нужна помощь",
начало поста "Кто-нибудь может реализовать это в Visual C++?"
как бы подразумевается именно надобность кода.
Как бы возможность в принципе и желание за бесплатно (и/или за дешево) помочь нерадивому студенту, который не стал тратить ни толики времени ни на изучение предмета, ни хотя бы на самые основы предмета, ни на написание умного поста на форуме, который не показывал бы два предыдущих пункта так очевидно - это две разные вещи.

Вы просите второе и маловероятно, что найдется тот, кто вам поможет.

...

Рейтинг:

0 / 0

12.11.2009, 16:42:15

| Ответить | Цитировать | Написать

Нужна помощь

#36307295

windwalker

Гость

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

P.S.: прощу прощения что мой пост не умный, в следующий приложу максимум времени и ораторского искусства для написания просьбы о помощи.

...

Рейтинг:

0 / 0

12.11.2009, 16:56:41

| Ответить | Цитировать | Написать

Нужна помощь

#36307725

Nixxx

Гость

Любой каприз за ваши деньги)
Если чё спршаивай ICQ: 348-743-458

...

Рейтинг:

0 / 0

12.11.2009, 19:48:34

| Ответить | Цитировать | Написать

Нужна помощь

#36308153

RT183.1

Участник

Откуда: G1

Сообщения: 535

Рейтинг: 0 / 0

windwalkerНапишите программу, определяющую минимальное количество школ, которым надо передать по одному экземпляру нового программного обеспечения, чтобы распространить его по всем школам сети.
80 школ (№№0-79).
Школа №0 обслуживает школы №2, №6, №13, №15, №31 ...
Ну и так по всем рядам.
=
80
00100010000001010000000000000001010000000010000001010000010000000000000000000000
10010101111100011110011011011000010101000100010100000000000100010100000101001001
00000000011100000000100101001101010000100100000000010000001101101000111110101110
10111100011100111001000110101110101001110100010001100000110000100110000101011010
10010001010100110100110000111001101001000001011010110001111001011001011101001110
10000000110110010101000111001010001110110111011101110001000110010001011100000110
11000101011010011000001111011100000001000101001100011011001000011110010000111010
00001000000000100100000010110100110010000011101001000000110010001000100110010000
11001010000001111100010101100000111100010100000000000000101101010011000111100000
10101001000010010001110101101010101011010010100000100010100000000011101010000000
00000001001001110111000111110011010011100000000000111000001111000000111011000011
10000011101011011100100000111001111001101110101010001111100011001100100111011110
11010010000000010111011011101100011100010000111000010010101101000000011110010000
11000001110001011001001100000000000100000010111010100100100100000000000010000000
11001001110110011101010001101010001011100010101001100000010110011100001111110110
10100010101000111110000100000000110011010000001010000111011100111101101010100110
11001100011100100000010000001101110000000000001100000000001000100100111000011000
00000000001010001000000001000010000100000000000001001000000000101000001000000000
11010101101110000100100000001101101000001111000110010000001110001011100110001010
10010100110001011101000000110011000000000010100101000110100110000000000001001101
10000111101110011000100101000000110000000100010000101000010000000000010001000010
00001000000000011101000101010110010100000000001011010100001100011010101100011000
11000111100011101100001001011101001100100110001100000000000010100000001010001011
10000000001111000001010101000001100101100101100111010110001010000010111001001101
10010001110101000000001100110101100010110011011001001000001111001001010111010000
00010011001100000010000101001001111000011000000100001010001010100000101000000000
11111011000000010000010010100001010010100010000001000110000010000100101011000110
11000110110111100000000000010000001101110000110100111000000000001010000011111010
10110110110101101101001101000101000101110001100100001101100001011001101000001001
10001100111010010011101010001001001010001011100000010000000010101010100101110100
10110000101010110010100100000110000000010111011101011010011100101000000011000110
11001010001000100101100100101010111001011000101101100010111000110011010000000100
10110001001011001001011001101000110011110001011000000000001011101010110100000000
10101011110000100000000000000000010001010001101000001000000011000010100110101101
10110000000100000000001000000000000110110110010011000011011011101110111101000101
10001001101010001011001111011000110110001010001010100010000000111000010110001100
10101101010010001001010011010100000000000111001011000001000110010100110001010110
10010010101100111001011000000000010011100100111101100101100111000000000010010001
10101100011010111010010110011000011000000100000010100101010001000111010011011011
00000010110111001011110000110100000000000000011010011001000110010000100000000000
11100001000001101100000001000000011001101010000010011100000001100101000000000000
10011010101101100001000111011011001100010000000000000001011000000010001011010011
00001001101010110010100000001010001010100110101001100110001010110010000000011011
00000010010000010110000001010011011101101010100000000000000100011010000101100101
10100000000001000000100000000000000010000101001101000101000101100000001000110000
10100000000000001001101001001100101110010001001000000101001010100000000000001001
10000100111001110010100001110011000000111000110000011001001011000001000000000000
10011010011001100000100000000001011001110100111001100000010000000000000000000110
11100000010011010100100010110100001011001011011000011110010000110110010111001000
10000000100000000000010100000101000100010010110101011101010001110011011000011101
10000000000010001001110001010111000111001110110000001001111100110110111010001000
00000011010000011000110001010000000000011100000001101001010100101100100111001000
00000010001000001000001011010011000000011001010101000011001001110000000000000000
11101010100100001010000110000000101000101100010011100011010001101101010000110000
10110010101110101100011000100011000000000000101011001101100010101000101101000101
00000000101000000100100110100000000000011010001001111000100000000000100011001000
11000010101000010011000010010001010000000011001000111011011101000001000111001011
10100101001110100000100110000001000000100000100000000001100100100110100101011000
10000000101110000000000110100110011101100001001110110110101010001100000100011010
10000001001000110101001010100000000000000010000100000100100010001010100110011001
10000000000000110110100101011000000100000000000000110100100111101100100011000000
10000010110000101001000011000010000101100101100010000100111110100101001101110000
10000001011001011100101010000100100100101001110010101000110011011110100100100000
10101000000000000111000111011000010000000000000101011010000000000001100000101001
11001110100011101000000000001100111000100000000000110010000011000100101100010001
10100100000000000000000000010110000000100110101101011000101010100101101010100000
10001001111010000001100000001011010000010010000101101100001010111001110010100000
10011000010101001100010101001100000011010110000111101110001010101010101011000000
10101001110001110100000011100000010111001000010110001101110010010000101011001000
00000100001110000001100010110100010101000010110101101101100011000011100000000000
11101000000101010000010010110000101110010110010111001110100101011110010111100000
11001100110100101001100100100001110000011010101010001000010101000000101000000000
00000000000000000000010001001001101100101101001011010001100000000010110011000001
10000100000000101001100001100110011110010010000100110101101100100000000101101010
10010000010101001110000000000010000011010111010101100101000101110001000000001000
00000010100100100000000010000010110000010000000011000000100000101100110001001100
10000000000000000000001000000000000000100111001000001100101100110010010001110000
10110100001100010010000000010100011010011010101110100100101011000100001101000101
10100100000011000001110101101100000100000000111001000010000110110010101010110000
10000101010001110011000001000001000010000101001100010000100100010100010010000000

Ответ: достаточно 4 школы.
Сначала код нашел набор из 12 школ, потом из 11 ... а минимум = 4 школы.

Код: plaintext

1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.

 12 
 0   1   2   3   4   5   6   7   8   9   10   11  
 11 
 0   1   2   3   4   5   6   7   8   9   11  
 10 
 0   1   2   3   4   5   6   7   8   11  
 9 
 0   1   2   3   4   5   6   7   11  
 8 
 0   1   2   3   4   5   6   11  
 7 
 0   1   2   3   4   5   11  
 6 
 0   1   2   3   5   11  
 5 
 0   11   12   38   74  
 4 
 11   12   38   74

Считало не менее 10 сек: код переборный доморощенный

...

Рейтинг:

0 / 0

13.11.2009, 06:51:38

| Ответить | Цитировать | Написать

Нужна помощь

#36308867

RT183.1

Участник

Откуда: G1

Сообщения: 535

Рейтинг: 0 / 0

Более разреженный - более трудный вариант.

Код: plaintext

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.

 80 
 00100010000001010000000000000000000000000010000001010000010000000000000000000000 
 10010100000000000000000000000000010001000100010100000000000100010100000101001001 
 00000000011100000000100101001101010000100100000000010000001101101000111110101110 
 10000000000000000000000000101110101001110100010001100000110000100110000101011010 
 10010001010100110100110000111001101001000001011010110001111001011001011101001110 
 10000000110110010101000111001010001000110111011101110001000110010001011100000110 
 11000101011010011000000000000000000001000101001100011011001000011110010000111010 
 00001000000000100100000010110100110010000011101001000000110010001000100110010000 
 11001010000000000000010101100000100000010100000000000000101101010011000111100000 
 10101001000010010000000000000000000000010010100000100010100000000011101010000000 
 00000001001001110111000000000000000000000000000000111000001111000000111011000011 
 10000011101011011100100000100000000000000000000000000000000000001100100111011110 
 11010010000000010111011000000000000000000000000000000000000001000000011110010000 
 00000001110001011001001100000000000100000010111010100100100100000000000010000000 
 11001000000000000000000000000000000000000010101001100000010110011100000000000110 
 10100010101000000000000100000000110011010000001010000111011100000000000000000110 
 11001100011100100000010000001101110000000000001100000000001000100100111000011000 
 00000000001010001000000001000010000100000000000001001000000000101000001000000000 
 11000000000000000000100000001101101000000000000110010000001110001011100110001010 
 10010100110001011101000000110011000000000010100101000110100110000000000001001101 
 10000000001110011000100101000000110000000100010000101000010000000000010001000010 
 00001000000000000000000000000000000100000000001011010100001100011010101100011000 
 11000000000000000000000000000000000000100110001100000000000010100000001010001011 
 10000000000000000001010101000001100101100101100111010110001010000010111001001101 
 10010001110101000000001100110101100010110011011001001000001111001001010111010000 
 00010011001100000010000101001001111000011000000100001010001010100000101000000000 
 00000011000000010000010010100001010010100010000001000110000010000100101011000110 
 11000110110111100000000000010000001100000000000000000000000000001010000000000010 
 10110000000100000001001101000101000101110001100100001101100001011001101000001001 
 10001100111010010000000000000000001010001011100000010000000010101010100101110100 
 10110000101000000000000000000000000000000000000000000000000000101000000011000110 
 11001010001000100101100100000000000000000000000000000010111000110011010000000100 
 10110001001011001001011001101000110000000001011000000000001011101010110100000000 
 10101000000000100000000000000000010001010001101000001000000011000010100110101101 
 10110000000100000000001000000000000110110110010011000011011000000000000001000101 
 10001001000000000000000000000000000000000000000000000000000000111000010110001100 
 10100000000000000000000001010100000000000111001011000001000110010100110001010110 
 10010010101100111001011000000000010011100100000001100101100111000000000010010001 
 10101100011000000000000000000000000000000100000010100101010001000000010011011011 
 00000010110111001000000000110100000000000000011010011001000110010000100000000000 
 11100001000001101100000001000000011001101010000010011100000001100101000000000000 
 10000000000000000001000111011011001100010000000000000001011000000010001011010011 
 00001000000000000000000000001010001010100110101001100110001010110010000000011011 
 00000010010000010110000001010011000000000000000000000000000100011010000101100101 
 10100000000001000000100000000000000010000101001101000101000101100000001000110000 
 10100000000000001001101001001100101110010001001000000101001010100000000000001001 
 10000100111001110010100001110011000000111000110000011001001011000001000000000000 
 10011010011001100000100000000001011000000100111001100000010000000000000000000110 
 11100000010011010100100010110100001011001011011000011110010000110110010111001000 
 10000000100000000000010100000101000100010010110101011101010001110011011000011101 
 10000000000010001001110001010111000000001000000000000000000000110110000010001000 
 00000011010000011000110001010000000000011100000001101001010100101100100111001000 
 00000010001000001000001011010011000000011001010101000011001000000000000000000000 
 11101010100100001010000110000000101000101100010011100011010001101101010000110000 
 00000000000000000000000000000000000000000000101011001101100010101000101101000101 
 00000000101000000100100110100000000000011010001000000000100000000000100011001000 
 11000010101000010011000010010001010000000011001000000011000001000001000111001011 
 10100101001110100000100110000001000000100000100000000001100100100110100101011000 
 10000000101110000000000110100110000001100001000000110110101010001100000100011010 
 10000001001000110101001010100000000000000010000100000100100010001010100110011001 
 10000000000000110000000000000000000100000000000000110100100000001000100001000000 
 10000010110000101001000011000010000101100101100010000100000000100101001100000000 
 10000001011001000000101010000100100100101001110010101000110011000000100100100000 
 10101000000000000111000111011000010000000000000101011010000000000001100000101001 
 11000000100000001000000000001100111000100000000000110010000011000100101100010001 
 10100100000000000000000000010110000000100100000000000000000000000000001010100000 
 10001000000010000001100000001011010000010010000101101100001010111001110010100000 
 00000000000000000000000000000000000011010110000000001000001010101010101011000000 
 10101001110000000100000011100000010000000000010110000000000000000000001011001000 
 00000100001110000001100010110100010101000010110100000000000000000011100000000000 
 00000000000101010000010010110000100000000000000000000000100101000000010000000000 
 00000000000000000000000000000000000000000000001010001000010101000000101000000000 
 00000000000000000000010001001000000000000000000000000000000000000010110011000001 
 10000100000000101001100001100110000000010010000100110101101100100000000101101010 
 10010000010101000000000000000010000000010000010101100101000100000001000000001000 
 00000010100100100000000010000010110000010000000011000000100000101100110001001100 
 10000000000000000000001000000000000000100000001000000000101100110010010001110000 
 10110100001100010010000000010100011000000000000000000000000000000100001101000101 
 10100100000011000000000100001100000100000000000001000010000110110010101010110000 
 10000100000000000000000000000001000010000101001100010000100100010100010010000000 






-------- 5 школ покрывают все остальные: нет ни одной колонки из одних нулей;

 5 
 4   24   41   53   69  
 10011001010100110100110000111001101001000001011010110001111001011001011101001110 
 10010001110101000000001110110101100010110011011001001000001111001001010111010000 
 10000000000000000001000111011011001100010100000000000001011000000010001011010011 
 11101010100100001010000110000000101000101100010011100111010001101101010000110000 
 00000100001110000001100010110100010101000010110100000000000000000011110000000000

...

Рейтинг:

0 / 0

13.11.2009, 12:13:53

| Ответить | Цитировать | Написать

Нужна помощь

#36309366

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

RT183.180 школ (№№0-79).
Школа №0 обслуживает школы №2, №6, №13, №15, №31 ...
Ну и так по всем рядам.

Почему мы не рассматриваем тривиальный случай? - "Школа №0 обслуживает все школы." Какое условие задачи мы нарушим?

...

Рейтинг:

0 / 0

13.11.2009, 14:28:23

| Ответить | Цитировать | Написать

Нужна помощь

#36310180

RT183.1

Участник

Откуда: G1

Сообщения: 535

Рейтинг: 0 / 0

Почему не рассматриваем???

> Какое условие задачи мы нарушим?

Никакое, конечно.

...

Рейтинг:

0 / 0

13.11.2009, 20:40:35

| Ответить | Цитировать | Написать

Нужна помощь

#36310231

RT183.1

Участник

Откуда: G1

Сообщения: 535

Рейтинг: 0 / 0

Подправил под такую (более "жизненную") задачу:
есть M оптовых продавцов и надо у них закупить N видов товара.
Какие-то товары у i-го продавца есть ("1"), каких-то нет ("0").
Надо выбрать мин. набор оптовиков, чтобы закупить у них все N видов товара.

Тест-файл:

=
60 80
00100010000001010000000000000000000000000010000001010000010000000000000000000000
10010100000000000000000000000000010001000100010100000000000100010100000101001001
00000000011100000000100101001101010000100100000000010000001101101000111110101110
10000000000000000000000000101110101001110100010001100000110000100110000101011010
10010001010100110100110000111001101001000001011010110001111001011001011101001110
10000000110110010101000111001010001000110111011101110001000110010001011100000110
11000101011010011000000000000000000001000101001100011011001000011110010000111010
00001000000000100100000010110100110010000011101001000000110010001000100110010000
11001010000000000000010101100000100000010100000000000000101101010011000111100000
10101001000010010000000000000000000000010010100000100010100000000011101010000000
00000001001001110111000000000000000000000000000000111000001111000000111011000011
10000011101011011100100000100000000000000000000000000000000000001100100111011110
11010010000000010111011000000000000000000000000000000000000001000000011110010000
00000001110001011001001100000000000100000010111010100100100100000000000010000000
11001000000000000000000000000000000000000010101001100000010110011100000000000110
10100010101000000000000100000000110011010000001010000111011100000000000000000110
11001100011100100000010000001101110000000000001100000000001000100100111000011000
00000000001010001000000001000010000100000000000001001000000000101000001000000000
11000000000000000000100000001101101000000000000110010000001110001011100110001010
10010100110001011101000000110011000000000010100101000110100110000000000001001101
10000000001110011000100101000000110000000100010000101000010000000000010001000010
00001000000000000000000000000000000100000000001011010100001100011010101100011000
11000000000000000000000000000000000000100110001100000000000010100000001010001011
10000000000000000001010101000001100101100101100111010110001010000010111001001101
10010001110101000000001100110101100010110011011001001000001111001001010111010000
00010011001100000010000101001001111000011000000100001010001010100000101000000000
00000011000000010000010010100001010010100010000001000110000010000100101011000110
11000110110111100000000000010000001100000000000000000000000000001010000000000010
10110000000100000001001101000101000101110001100100001101100001011001101000001001
10001100111010010000000000000000001010001011100000010000000010101010100101110100
10110000101000000000000000000000000000000000000000000000000000101000000011000110
11001010001000100101100100000000000000000000000000000010111000110011010000000100
10110001001011001001011001101000110000000001011000000000001011101010110100000000
10101000000000100000000000000000010001010001101000001000000011000010100110101101
10110000000100000000001000000000000110110110010011000011011000000000000001000101
10001001000000000000000000000000000000000000000000000000000000111000010110001100
10100000000000000000000001010100000000000111001011000001000110010100110001010110
10010010101100111001011000000000010011100100000001100101100111000000000010010001
10101100011000000000000000000000000000000100000010100101010001000000010011011011
00000010110111001000000000110100000000000000011010011001000110010000100000000000
11100001000001101100000001000000011001101010000010011100000001100101000000000000
10000000000000000001000111011011001100010000000000000001011000000010001011010011
00001000000000000000000000001010001010100110101001100110001010110010000000011011
00000010010000010110000001010011000000000000000000000000000100011010000101100101
10100000000001000000100000000000000010000101001101000101000101100000001000110000
10100000000000001001101001001100101110010001001000000101001010100000000000001001
10000100111001110010100001110011000000111000110000011001001011000001000000000000
10011010011001100000100000000001011000000100111001100000010000000000000000000110
11100000010011010100100010110100001011001011011000011110010000110110010111001000
10000000100000000000010100000101000100010010110101011101010001110011011000011101
10000000000010001001110001010111000000001000000000000000000000110110000010001000
00000011010000011000110001010000000000011100000001101001010100101100100111001000
00000010001000001000001011010011000000011001010101000011001000000000000000000000
11101010100100001010000110000000101000101100010011100011010001101101010000110000
00000000000000000000000000000000000000000000101011001101100010101000101101000101
00000000101000000100100110100000000000011010001000000000100000000000100011001000
11000010101000010011000010010001010000000011001000000011000001000001000111001011
10100101001110100000100110000001000000100000100000000001100100100110100101011000
10000000101110000000000110100110000001100001000000110110101010001100000100011010
10000001001000110101001010100000000000000010000100000100100010001010100110011001

Код:

Код: plaintext

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <string>
#include <vector>
#include <bitset>
using namespace std;

const int M_MAX =  80 ;
const int N_MAX =  100 ;
typedef bitset<N_MAX> BS;
typedef vector<int> PATH;

BS a[M_MAX];
BS b[M_MAX];
BS z;
PATH ans;
int ans_sz = M_MAX +  1 ;
int m;
int n;


void foo(int st, BS t, PATH tmp, int cnt) {
    ++cnt;
    if (cnt == ans_sz) return;
    tmp.push_back(st);
    t |= a[st];
    z = t | b[st +  1 ];
    if (z.count() != n) return;
    if (t.count() == n) {
        ans_sz = cnt;
        ans = tmp;
        return;
    }
    for (int j = st +  1 ; j < m; ++j) {
        foo(j, t, tmp, cnt);
    }
}



int main() {
    freopen("E:\\postavki.txt", "rt", stdin);
    freopen("E:\\postavki_out.txt", "wt", stdout);

    cin >> m >> n;
    for (int i =  0 ; i < m; ++i) {
        string s;
        getline(cin, s);
        a[i].reset();
        for (int j =  0 ; j < n; ++j) {
            char ch;
            cin >> ch;
            if (ch == '1') a[i].set(j);
        }
        if (a[i].count() == n) {
            ans_sz =  1 ;
            ans.push_back(i);
        }
    }

    b[m -  1 ] = a[m -  1 ];
    for (int i = m -  2 ; i >  0 ; --i) b[i] = b[i + 1] | a[i];

    BS t;
    PATH tmp;
    t.reset();
    tmp.clear();
    for (int i =  0 ; i < m; ++i) foo(i, t, tmp,  0 );

    // output:
    cout << ans_sz << endl;
    for (int k =  0 ; k < ans_sz; ++k)
        cout << ans[k] << " ";
    cout << endl;
    for (int k =  0 ; k < ans_sz; ++k) {
        for (int j =  0 ; j < n; ++j)
            cout << a[ans[k]].test(j);
        cout << endl;
    }

return  0 ;
}

Ризалт:

Код: plaintext

1.
2.
3.
4.
5.
6.
7.
8.

 6 
 1   3   23   48   53   59  
 10010100000000000000000000000000010001000100010100000000000100010100000101001001 
 10000000000000000000000000101110101001110100010001100000110000100110000101011010 
 10000000000000000001010101000001100101100101100111010110001010000010111001001101 
 11100000010011010100100010110100001011001011011000011110010000110110010111001000 
 11101010100100001010000110000000101000101100010011100011010001101101010000110000 
 10000001001000110101001010100000000000000010000100000100100010001010100110011001

Кто меньше?

...

Рейтинг:

0 / 0

13.11.2009, 22:08:51

| Ответить | Цитировать | Написать

13 сообщений из 13, страница 1 из 1

Форумы / Программирование [игнор отключен] [закрыт для гостей] / Нужна помощь

Читали тему (0):

Читали форум (0):

Пользователи онлайн (0):

start [/forum/topic.php?fid=16&fpage=114&tid=1344102]:	0ms
get settings:	6ms
get forum list:	9ms
check forum access:	2ms
check topic access:	2ms
track hit:	60ms
get topic data:	7ms
get forum data:	2ms
get page messages:	46ms
get tp. blocked users:	1ms
others:	186ms

total:	321ms

	Необходимые cookie
	Cookie для сбора статистики
	Cookie для маркетинга и рекламы