Главное меню портала
• О портале
• Архив задач
• Карта архива задач
• Результаты тестов
• Ошибки тестирования
• Преподаватели
• Библиотечка
Рейтинг у учителя
• Рейтинг на портале
Начинающему
• Работа с порталом
• Курс для начинающего
• Архив задач начинающего
Олимпиаднику
• Архив задач олимпиадника
Олимпиады
Дистанционные олимпиады
• Положение олимпиады
Новое сообщениеОтправленые
Загрузка...
Время на прохождение теста: 1 секунд(а/ы).
Имя входного файла: input.txt
Имя выходного файла: output.txt

Автор: Бельский Андрей Владимирович

Тестировщик

Петр Васильевич Колошин решил стать профессиональным тестировщиком. Прослушав двухмесячные курсы по тестированию программ, он утроился на работу в знаменитую компанию “Gold&Silver Soft”. После двух месяцев работы Петру Васильевичу доверили тестировать серьезный проект. Провозившись не одну неделю, Петр Васильевич никак не мог определить, в чем заключается ошибка. Как-то раз нашего тестировщика посетила гениальная мысль о том, что вся загвоздка заключается не в программном  коде, а в трансляторе, который исполняет эту программу. Досконально  изучив транслятор, Петр Васильевич столкнулся с интересным фактом, что при исполнении программы транслятор хранит счетчик суммы, который равняется сумме всех значений переменных, используемых в  исполняемой программе, и предположил, что именно этот счетчик  всегда переполняется.

Внимательно изучив код и спецификацию программы, Петр Васильевич выписал все ограничения, накладываемые на переменные. Ему также известно, что все переменные данной программы могут принимать  только целые неотрицательные  значения. Каждое ограничение представляет собой одно из шести видов неравенств:

 

·        Variable1_>=_Variable2_+_Number

·        Variable1_>_Variable2_+_Number

·        Variable1_>=_Variable2

·        Variable1_>_Variable2

·        Variable1_>=_Number

·        Variable1_>_Number

В данной записи символ “_” обозначает пробел(ASCII 32). Varible1,Varible2 – это два различных идентификатора, обозначающие названия переменных. Идентификатором переменной будем называть строку, содержащую от одного до десяти  символов, которыми могут быть цифры и маленькие латинские буквы, причем первый символ всегда буква. Два идентификатора называются различными, если они состоят из неравного количества символов либо существует различие хотя бы в одном символе. Кроме того, известно, что данный транслятор не позволяет, чтобы двум различным переменным соответствовал один  и тот же идентификатор, а также чтобы одной переменной соответствовали два различных идентификатора. Numberэто целое неотрицательно число не превосходящее 1000.

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

Входные данные:

В первой  строке  входного  файла   input.txt  содержится   целое неотрицательное число K (1 ≤ K ≤ 2000) – количество ограничений. Следующие  K строк описывают ограничения, накладываемые на переменные. Каждая такая строка описывает ровно одно ограничение, которое, как оговаривалось выше, представляет собой одно из шести возможных  неравенств. 

Выходные данные:

Если не существует ни одного набора значений переменных, удовлетворяющих ограничениям, то выходной файл output.txt должен содержать одно число: -1, иначе выходной файл должен содержать минимальное из всевозможных значений счетчика суммы.


Примеры:
input.txt output.txt
1 5
a > b
kol >= 9
num >= col2 + 100
kol > 0
col2 > kol
130
2 3
a123 > b11
b11 >= a123 + 1000
a12 > 17
-1

Сложность задачи: 50%



Проверку могут осуществлять только зарегистрированные пользователи!


Разбор задачи

Каждой переменной поставим в соответствие вершину графа, а каждому неравенству       поставим в соответствие дугу, весом которой будет число q, которое говорит о том, что переменная v1 больше переменной v2 на значение q. Ясно,  что если q>0 данная модель разрешима только для  ориентированного графа без циклов. То есть, сортируем вершины топологической сортировкой и вычисляем значения переменных снизу вверх. Для случая q = 0, необходимо «стянуть» компоненты сильносвязности в одну вершину получим ориентированный граф без циклов. 

Показать обсуждение


На сайте гостей 17, зарегистрированных 0:
Сейчас онлайн только гости...
[Данные за последние 5 минут]