说谎者的拼图 [英] The puzzle of Liars

问题描述

我一直在试图解决 Interviewstreet 的一个难题。但我不现在有一个线索的问题。这将是巨大的，如果有人可以给我一个提示。

I have been trying to solve a puzzle in Interviewstreet. But I don't have a clue for the problem by now. It'll be great if someone can give me a hint.

让人不解的是： 您有编号从1到N每一个你的士兵要么是骗子还是一个真实的人ñ士兵。你有M组的相关信息。该信息如下形式：

The puzzle is: You have N soldiers numbered from 1 to N. Each of your soldiers is either a liar or a truthful person. You have M sets of information about them. The information is of the following form:

每个行包含3个整数 - A，B和C这意味着，在一组士兵编号为{A，A + 1，A + 2，...，B}，他们正是C是骗子。 有M行象上面

Each line contains 3 integers - A, B and C. This means that in the set of soldiers numbered as {A, A+1, A+2, ..., B}, exactly C of them are liars. There are M lines like the above.

让L是你的骗子士兵的总数。因为你找不到升的精确值，你想找到的最小和L的最大值。

Let L be the total number of your liar soldiers. Since you can't find the exact value of L, you want to find the minimum and maximum value of L.

输入：

输入的第一行包含两个整数N和M。 每个接下来的M行有三个整数 - A，B和C（1＆LT; =艾＆LT; =毕＆LT; = n）和（0℃= Cl＆LT; =双艾）。其中A，B i和C I分别指的是A，B和C的值在第i行 N和M是不大于101以上，这是保证给定的信息是可满足的。你总是可以找到的情况下满足给定的信息。

The first line of the input contains two integers N and M. Each of next M lines contains three integers - A, B and C (1 <= Ai <= Bi <= n) and (0 <= Ci <= Bi-Ai). where Ai, B i and C i refers to the values of A, B and C in the ith line respectively N and M are not more than 101, and it is guaranteed the given informations are satisfiable. You can always find a situation that satisfies the given information .

输出：

打印两个整数Lmin时和Lmax的到输出

Print two integers Lmin and Lmax to the output.

采样输入

3 2
1 2 1
2 3 1

示例输出

1 2

采样输入

20 11
3 8 4
1 9 6
1 13 9
5 11 5
4 19 12
8 13 5
4 8 4
7 9 2
10 13 3
7 16 7
14 19 4

示例输出

13 14

说明

在测试用例的第一行的第一个样本是3 2，这意味着有3士兵，我们有两组信息。第一个信息是，在一系列的士兵{1，2}，1人是骗子，第二条信息是，在一系列的士兵{2,3}再有一个骗子。现在有两种可能这样的场景：战士1号和3骗子或士兵2号是骗子。 所以骗子的最小数目是1，骗子最大数目是2。因此答案，1 2

In the first sample testcase the first line is "3 2", meaning that there are 3 soldiers and we have two sets of information. The first information is that in the set of soldiers {1, 2} one is a liar and the second piece of information is that in the set of soldiers {2,3} again there is one liar. Now there are two possibilities for this scenario: Soldiers number 1 and 3 are liars or soldier number 2 is liar. So the minimum number of liars is 1 and maximum number of liars is 2. Hence the answer, 1 2.

推荐答案

您可以轻松地制订这是一个整数线性规划。由于约束矩阵是完全幺模，它可以快速通过任何ILP求解器解决。

You can easily formulate this as an Integer Linear Program. Since the constraint matrix is totally unimodular, it can be quickly solved by any ILP solver.

这篇关于说谎者的拼图的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！