IWANTTOSUBMIT's blog

By IWANTTOSUBMIT, 13 years ago, In Russian
Столкнулся с такой задачей: нам даётся объект, который принадлежит одному из типов объектов p1, ..., pn. Есть тесты t1, ..., tm. Для каждого из pi объектов тест tj может отвечать одно из трёх: признак присутствует, признак отсутствует, признак неизвестен. Т.е. нам на вход даётся матрица n*m с -1, 0 и 1.

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

Может задача известная какая, но гугол мне не помог...

Помогите пожалуйста, поделитесь идеями?

UPD: Спасибо freopen! Будем втыкать...
  • Vote: I like it
  • -5
  • Vote: I do not like it