Please Help me with this question.

help
1

any one ??

2 
x = raw_input()
s = input()
s = s.split(' ')
for yo in s:
   if yo > s and len(s) != x:
      print('Error!')
      exit()
print(s.count('1'))
3

The first step in solving this is the following observation:

For the two statements

S1: At least 4 guards are telling the truth

S2: At least 10 guards are telling the truth

Notice that statement S2 is the stronger statement. Because if S2 is true, S1 is definitely true. But, if S1 is true, S2 is not necessarily true.

With this observation in mind, let’s sort the array R in non-decreasing order. Let’s call the sorted array R as SR. There is great advantage in doing so. If the maximum number of guards who are definitely telling the truth is X, then those guards can only be the first X guards in SR.

Now the stage is set to actually find X. Array indices start from 1 in the following explanation:

As we are given that at least one guard is telling the truth, we initialise X to 1 and then keep on updating X to a larger value according to the following rule.

Initially X=1, therefore the first guard is telling the truth. This means that the guards 1,2,…,SR[1] are all definitely telling the truth. Note that as SR is sorted, max(SR[1], SR[2], …, SR[SR[1]])=SR[SR[1]]. Therefore, SR[SR[1]] guards are also definitely telling the truth and so on…

In general, if at least X guards are telling the truth then at least SR[X] guards are also definitely telling the truth.

There is a corner case though. If SR[X]==SR[X+1]==SR[X+2], and we know that first X guards are telling the truth, then definitely X+2 guards are telling the truth. This is because the guards X,X+1 and X+2 are making the same statements.

The following is a good reference solution:

https://www.codechef.com/viewsolution/12331883

1 Like