Поиск:

Ответ в темуСоздание новой темы Создание опроса
> Мат Логика 
:(
    Опции темы
vinter
Дата 13.3.2007, 11:43 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Explorer
****


Профиль
Группа: Завсегдатай
Сообщений: 2735
Регистрация: 1.4.2006
Где: Н.Новгород

Репутация: нет
Всего: 56
есть задача
Цитата

2. Истинные утверждения

Документ состоит из предложений вида «Предложение I истинно» или «Предложение I ложно». Предложения могут противоречить друг другу. Требуется определить, какое максимальное количество предложений в документе может быть одновременно истинным.
Входной файл

Содержит в первой строке число N - количество предложений. Следующие N строк содержат предложения в виде двух чисел I и T, где I – порядковый номер предложения в документе (начиная с 1), о котором утверждается в данном предложении, а T принимает значения 0 (ложно) или 1 (истинно).
Выходной файл

Содержит в первой строке единственное число - максимальное количество одновременно истинных предложений.
Ограничения

Время на выполнение программы: 15 секунд.

1 < N < 4000
Пример 1 входного файла  Пример 1 выходного файла 

1                                                 1
1 1    

Пример входного файла    
                                    Пример 2 выходного файла
1                                         0
1 0    


Пример 3 входного файла    
                             Пример 3 выходного файла

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

кто нить может подсказать алгоритм ее решения?


--------------------
Мой блог
PM MAIL WWW   Вверх
urikz
Дата 13.3.2007, 15:34 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 3
Регистрация: 21.9.2006

Репутация: нет
Всего: нет

Точно не знаю, но может здесь надо воспользовать задачей о максимальном числе паросочетаниях? 
PM MAIL   Вверх
vinter
Дата 13.3.2007, 15:40 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Explorer
****


Профиль
Группа: Завсегдатай
Сообщений: 2735
Регистрация: 1.4.2006
Где: Н.Новгород

Репутация: нет
Всего: 56
urikz, вот и я тоже не знаюsmile


--------------------
Мой блог
PM MAIL WWW   Вверх
  
 Ответ в темуСоздание новой темы Создание опроса
Правила форума "Алгоритмы"

maxim1000

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

Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, maxim1000.
 
0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | Алгоритмы | Следующая тема »

Подписаться на тему | Подписка на этот форум | Скачать/Распечатать тему


 




[ Время генерации скрипта: 0.0573 ]   [ Использовано запросов: 21 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
 По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.