11659 - Informants

[tryit1]

how to solve this problem ?

Can you post links to similar problems.

[Igor9669]

I think that this test could help to find a solution for that problem, it is really easy.

Code: Select all

20 0
0 0


answer is 20!

[tryit1]

yes it is 20 because the mask 2^20 -1 is satisfied by all things. I don't understand how to formulate this problem and i find this problem VERY HARD. I really don't now how to solve this one. Can you give me more examples ,smaller ones so that i can relate it understand and use it to test my program.

Should we do something like this ?

dfs()
for each person ,
assume he is speaking truth,
-> All reliables are speaking truth
dfs(for each reliable)
if he is false
do nothing.

The problem is with conflicts, a future reliable can conflict with current not reliable and a current not reliable can be future reliable. This causes confusion. Maybe this is wrong approach. Can you tell me similar problems ?

[Igor9669]

You make it very hard yourself!
It is simple adhoc problem.
You need only one array and one loop! array[i]=0 if informant "i" is not reliable and 1 if reliable. At first all array is 1!
Hope it helps!

[tryit1]

As an example, let's assume there are four informants A, B, C and D, with the following surveyed answers: ``A says B is reliable but D is not'', ``B says C is not reliable'', and ``C says A and D are reliable''. In this case, it happens that at most two informants are reliable.

Can you tell me how we get 2 informans as reliable ? how would you approach the above example. Any similar problems ?

[ecarrion]

Hi, how and imput like this should be treated.

6 4
1 2
2 -3
1 4
4 -2


Would the answer be 5 or 4?

I mean that if we have to look for all transitive relations? and if we have to, on some special cases, wouldn't it take us to an endless loop?

Thanks.

[ecarrion]

As an example, let's assume there are four informants A, B, C and D, with the following surveyed answers: ``A says B is reliable but D is not'', ``B says C is not reliable'', and ``C says A and D are reliable''. In this case, it happens that at most two informants are reliable.

Can you tell me how we get 2 informans as reliable ? how would you approach the above example. Any similar problems ?

It is simple, in ther first step all informants are reliable, then A says B is reliable bit D is not, so we got all informants reliable except D, then B wich is reliable says than C is not reliable, so we got A,B reliable and C,D not reliable, then C says that A and D are reliable, but since C is not reliable we should ignore what he or she is saying.

So A and B are the only one reliables, so the answer is 2.

[saiful_sust]

Ithink it is a easy problem

But I got WA........

Some one PLZ check my code.........

Code: Select all

#include<stdio.h>
#include<stdlib.h>

int a[803];

int main()
{
   int i,n,b,c,m,Count,j,d;
   while(scanf("%d%d",&m,&n)==2 && (m || n))
   {
      Count= 0;
      for(i=1;i<=m;i++)
         a[i]=1;
      for(i=1;i<=n;i++)
      {
         scanf("%d%d",&b,&c);

         if(a[b])
         {
            if( c > 0)
            {
               a[c] = 1;
               
            }
            else if(c < 0)
            {
               d = (-1)*c;
               a[d] = 0;
            }         
         }
      }
      for(i=1;i<=m;i++)
      {
         if(a[i])
            Count++;
      }
      printf("%d\n",Count);
   }
   return 0;
}


[hasan3050]

try this input

Code: Select all

20 6
1 -3
2 -3
3 1
2 2
7 -1
4 3


the rigth out put should be 18......your code shows 19.....

[saiful_sust]

Thanks hasan3050 for ur test case
I solve this test case But again WA
My modified code Here:
PLZ help me.....

Code: Select all

#include<stdio.h>
#include<stdlib.h>

int a[803];

int main()
{
   int i,n,b,c,m,Count,d,e;
   //freopen("a.txt","r",stdin);
   while(scanf("%d%d",&m,&n)==2 && (m || n))
   {
      Count= 0;
      for(i=1;i<=m;i++)
         a[i]=1;
      for(i=1;i<=n;i++)
      {
         scanf("%d%d",&b,&c);
         e = c;
         if( e < 0)
         {
            e = (-1)*e;
         }
         if( (a[b]==2) && ( a[e] > 0) )
         {
            if( c > 0)
            {
               a[c] = 2;
               
            }
            else if(c < 0)
            {               
               a[e] = 0;
            }         
         }
         else if( (a[b]==1) && ( a[e] > 0) )
         {
            if( c > 0)
            {
               a[c] = 2;
               
            }
            else if(c < 0)
            {               
               a[e] = 0;
            }
         }
      }

      for(i=1;i<=m;i++)
      {
         //printf("a [%d] == %d\n",i,a[i]);
         if(a[i]>=1)
            Count++;
      }
      printf("\n%d\n",Count);
   }
   return 0;
}


[Igor9669]

First you print leading new line!
Second why do you use such a big array you need only 20 elements and third try this test:

Code: Select all

3 2
1 -3
3 -2
0 0


Answer should be 1!

[Chimed]

how to solve this problem ?

Can you post links to similar problems.

"tryit1": can you put problem name when you creating new thread.

[apurba]

First you print leading new line!
Second why do you use such a big array you need only 20 elements and third try this test:

Code: Select all

3 2
1 -3
3 -2
0 0


Answer should be 1!

how could the answer be 1 !!!!!

[Jehad Uddin]

because 3 isnt reliable and 2 isnt reliable ,so only 1 is reliable so ans is 1,its so simple problem,try all the I/Os in the board,

[ecarrion]

because 3 isnt reliable and 2 isnt reliable ,so only 1 is reliable so ans is 1,its so simple problem,try all the I/Os in the board,

I think that the problem says that when an informant is not reliable, their words can be true or false, so I don't se a way of how 2 is not relieabe.
Did I misunderstood the problem statemen?