TLE '16 Contest 1 P6 - A Very Normal Test - Olympiads Online Judge

TLE '16 Contest 1 P6 - A Very Normal Test

Points: 25 (partial)

Time limit: 1.0s

Memory limit: 128M

Author:

Problem type

The ~~unfortunate~~ very, very, very, lucky members of Trudeau's Computer Science Club are given another chance to become an exec. To actually be able to become an exec, one must solve an annoying problem that has been approved by ZQFMGB12. No one has bothered to try it in the past, but today that will change!

ZQFMGB12 has put out a simple true/false test for everyone to try. Each question is labelled from $1$ ~1~ to $N$ ~N~. The test is extremely boring because all of the questions follow this rather strict format:

Question	Description
`p==q`	If the answers for question $p$ ~p~ and question $q$ ~q~ are equal, answer `true` to this question. Otherwise, answer `false`.
`!p`	Put the opposite of question $p$ ~p~'s answer.

There is actually a reason for this unusual test format. Tests are fairly compact and easy to grade, yet it is difficult to answer all the questions perfectly.

This test might be impossible because ZQFMGB12 is too lazy to check for a solution. Does a perfect solution exist, and can you provide an example?

Constraints

For all subtasks:

$1 \le N \le 300$ ~1 \le N \le 300~

Subtask 1 [20%]

$N \le 20$ ~N \le 20~

Subtask 2 [20%]

Questions will only be in the form !p.

Subtask 3 [60%]

No additional constraints.

Input Specification

The first line contains integer $N$ ~N~.

The $N$ ~N~ questions are on separate lines. Question $k$ ~k~ is on line number $k+1$ ~k+1~.

Output Specification

If no perfect solution exists, output No perfect solution found.

Otherwise, provide $N$ ~N~ lines of output. The $k^\text{th}$ ~k^\text{th}~ line of output should contain your answer to the $k^\text{th}$ ~k^\text{th}~ question, which could either be true or false.

Sample Input 1

5
1==1
!3
!2
3==2
!1

Sample Output 1

true
false
true
false
false

Sample Input 2

1
!1

Sample Output 2

No perfect solution found

Explanation for Sample 2

If the answer is false, then the grader would look for the opposite of false. The opposite of false is not provided, so the answer is labelled incorrect.

If the answer is true, then the grader would look for the opposite of true. The answer would also be labelled incorrect.

There is no way to answer the question correctly, so no perfect solution exists.

Sample Input 3

4
!2
1==4
1==2
!3

Sample Output 3

No perfect solution found

Comments

-3

The_Lemon_314 commented on Sept. 22, 2016, 12:36 a.m.

Isn't sample output 3 just : True False False True

0

r3mark commented on Sept. 22, 2016, 12:54 a.m.

Since 1==4, 3 should be True, not False.

-3

TheCool1James commented on Sept. 21, 2016, 11:41 p.m.

Umm... Can someone explain Sample Input 1?? How is !3 outputting false?

1

d commented on Sept. 21, 2016, 11:45 p.m.

!3 means to put the opposite of question 3's answer.

The sample output is a perfect solution, and question 2's answer is indeed the opposite of question 3's answer.

-2

TheCool1James commented on Sept. 21, 2016, 11:56 p.m.

What about sample input 3? !2 is the opposite of 2==4, !3 is the opposite of 1==2... So..?

0

ZQFMGB12 commented on Sept. 22, 2016, 12:15 a.m.

No matter how you choose your combination of true/false, you cannot satisfy all of the questions.

1

d commented on Sept. 22, 2016, 12:08 a.m.

It is not possible to provide a perfect solution for Sample Input 3.

-7

TheCool1James commented on Sept. 22, 2016, 12:10 a.m.

That was so helpful...

This comment is hidden due to too much negative feedback. Show it anyway.

10

imaxblue commented on Sept. 21, 2016, 11:34 p.m.

do you want coke or chocolate milk with your salt?

11

d commented on Sept. 21, 2016, 11:36 p.m. ← edited →

I'll have water. Have fun solving the problem.