ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1487. Китайский футбол

Alexander Sokolov [MAI] Am I stupid? [10] // Задача 1487. Китайский футбол 8 окт 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...
Alexander Sokolov [MAI] Re: Am I stupid? [9] // Задача 1487. Китайский футбол 8 окт 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!
Burmistrov Ivan (USU) Re: Am I stupid? [8] // Задача 1487. Китайский футбол 8 окт 2006 23:23
You should print "YES", but not "Yes"...
Alexander Sokolov [MAI] Re: Am I stupid? [7] // Задача 1487. Китайский футбол 8 окт 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
readln(n);
for i:=1 to n do begin
for j:=1 to n do begin
read(t);
if t='0' then a[i,j]:=false else a[i,j]:=true;
end;
readln;
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;

readln(q);
for i:=1 to q do begin
readln(x,y);
if b[x]>b[y] then writeln('YES') else writeln('No');
end;
end.
Burmistrov Ivan (USU) Re: Am I stupid? [6] // Задача 1487. Китайский футбол 9 окт 2006 21:09
may be this test will help you:
4
0010
0001
0100
0000
4
1 2
1 4
4 1
4 3

answer:
YES
YES
YES
No

Sid Re: Am I stupid? [4] // Задача 1487. Китайский футбол 9 окт 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
Burmistrov Ivan (USU) Re: Am I stupid? [3] // Задача 1487. Китайский футбол 10 окт 2006 23:22
Sid писал(a) 9 октября 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".

My answer for your test:
YES
YES
YES
YES
YES
YES
YES
Sid Re: Am I stupid? // Задача 1487. Китайский футбол 12 окт 2006 21:48
Thank you, your answer helped me mutch!
Yaroslavtsev Grigory (SpbSPU) Re: Am I stupid? [1] // Задача 1487. Китайский футбол 15 окт 2006 19:01
Burmistrov Ivan (USU) писал(a) 10 октября 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".
Burmistrov Ivan (USU) Re: Am I stupid? // Задача 1487. Китайский футбол 18 окт 2006 23:10
Yaroslavtsev Grigory (SpbSPU) писал(a) 15 октября 2006 19:01
Burmistrov Ivan (USU) писал(a) 10 октября 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
AnisimovaViktoria Re: Am I stupid? // Задача 1487. Китайский футбол 14 май 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