ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

## Discussion of Problem 1487. Chinese Football

Am I stupid?
Posted by Alexander Sokolov [MAI] 8 Oct 2006 22:12
I cant ivent any tests that my solution will fail, but I have WA1!
Can any body help...
Give me some test!
Plz...
Re: Am I stupid?
Posted by Alexander Sokolov [MAI] 8 Oct 2006 22:28
example tests
4
0110
0011
0001
1000
4
1 4
2 3
3 2
4 1
my output:
No
No
No
No
3
010
000
100
3
1 3
3 1
2 3
out:
No
Yes
No
Is it correct?
Give some more tests!
Re: Am I stupid?
Posted by Burmistrov Ivan (USU) 8 Oct 2006 23:23
You should print "YES", but not "Yes"...
Re: Am I stupid?
Posted by Alexander Sokolov [MAI] 8 Oct 2006 23:47
WA 2
CODE:
program china;
var
t:char;
i,j,k:integer;
a:array[1..100,1..100] of boolean;
b:array[1..100] of integer;
chk:array[1..100] of boolean;
x,y,q,n,m:integer;

procedure solve(k:integer);
var
i:integer;
begin
for i:=1 to n do begin
if a[k,i] then begin
if not chk[i] then begin
chk[i]:=true;
solve(i);
end;
end;
end;
end;

begin
for i:=1 to n do begin
for j:=1 to n do begin
if t='0' then a[i,j]:=false else a[i,j]:=true;
end;
end;

for i:=1 to n do begin
fillchar(chk,n,false);
solve(i);
for j:=1 to n do begin
if chk[j] then b[i]:=b[i]+1;
end;
end;

for i:=1 to q do begin
if b[x]>b[y] then writeln('YES') else writeln('No');
end;
end.
Re: Am I stupid?
Posted by Burmistrov Ivan (USU) 9 Oct 2006 21:09
4
0010
0001
0100
0000
4
1 2
1 4
4 1
4 3

YES
YES
YES
No

Re: Am I stupid?
Posted by Sid 9 Oct 2006 23:40
Why answer for 1 4 and 4 1 YES
and what is the anwer for

4
0100
0000
0001
0000
7
1 2
2 1
3 4
4 3
3 1
1 3
3 2
Re: Am I stupid?
Posted by Burmistrov Ivan (USU) 10 Oct 2006 23:22
Sid wrote 9 October 2006 23:40
Why answer for 1 4 and 4 1 YES
Because you should print "No" only if nodex x and y have common predecessor. In other cases you should print "YES".

YES
YES
YES
YES
YES
YES
YES
Re: Am I stupid?
Posted by Sid 12 Oct 2006 21:48
Re: Am I stupid?
Posted by Yaroslavtsev Grigory (SpbSPU) 15 Oct 2006 19:01
Burmistrov Ivan (USU) wrote 10 October 2006 23:22
Because you should print "No" only if nodex x and y have common predecessor. In other cases you should print "YES".

Where this is written in the statement? Why can't I solve the problem this way:
1. Make transitive closure of the given graph (matrix A)using Floyd.
2. For every request (pair i j) print "YES" if A[i][j] = 1 otherwise print "No".
Re: Am I stupid?
Posted by Burmistrov Ivan (USU) 18 Oct 2006 23:10
Yaroslavtsev Grigory (SpbSPU) wrote 15 October 2006 19:01
Burmistrov Ivan (USU) wrote 10 October 2006 23:22
Because you should print "No" only if nodex x and y have common predecessor. In other cases you should print "YES".

Where this is written in the statement?

Here:
"In this case we say that the team A is stronger than the teams B and C (more formally, A is stronger than B if A has beaten B or if A has beaten a team C which is stronger than B)."

Edited by author 18.10.2006 23:11

Edited by author 18.10.2006 23:11
Re: Am I stupid?
Posted by AnisimovaViktoria 14 May 2019 23:24
4 1 anwer is No, because 1 better than 3, 3 better than 2, 2 better than 4 => 1 better than 4