Общий форум @ Timus Online Judge

Tran Nam Trung (trungduck@yahoo.com) I have asked but none of u answer me ! [9] 26 июн 2001 06:47

Please tell me whether vector (0,0,0) and (1,1,1) ( for
example ) are independent in Prob 1041 ?
Thanks.
71222119
mailto : trungduck@yahoo.com

Dinh Quang Hiep (mg9h@yahoo.com) i don't know how to answer you, but i think here is a good way to find out it [4] 26 июн 2001 19:42

you can have the test cases for this problem from russian
website (one of the link in "links" part).
as i remember, this problem is just to find maximum matches
!

QH@

Tran Nam Trung (trungduck@yahoo.com) Re: i don't know how to answer you, but i think here is a good way to find out it [3] 27 июн 2001 09:08

My program was right for all test cases except this test
case :
5 4
1 0 0 0
1 1 0 0
1 1 1 0
1 2 3 0
2 3 4 0
1
1
1
1
1
Why the correct answer is 0 ? I think all 5 vectors are
independent so the answer is :
4
1
2
3
4
Can u tell me why ?

> you can have the test cases for this problem from russian
> website (one of the link in "links" part).
> as i remember, this problem is just to find maximum
matches
> !
>
> QH@

Dinh Quang Hiep (mg9h@yahoo.com) Vi` no' co' cai co^.t cuoi la` toan so 0 thi` fai :D [1] 27 июн 2001 18:12

cap ghep tim dc fai co so dinh ghep dc la maximum (a[i][j]=0
coi nhu ko co ca.nh ;) )
noi chung ba`i na`y anh cung hoi rua, nen ko tra loi ki dc,
em thu xem xet cai DN cua thang Mirzayanov Michael xem the
nao ;)

QH@

Tran Nam Trung (trungduck@yahoo.com) Re: Vi` no' co' cai co^.t cuoi la` toan so 0 thi` fai :D 27 июн 2001 18:26

I think this prob doesn't need to uses maximum matches. We
just "loa.i bo?" vectors that are not independent. For the
rest vector (after "loa.i bo?"), we sort it "tang". Just
simple ! I have read the definition of Mirzayanov Michael
but I din't understand and it was different from the one I
know (I read in "Toan cao cap"). Is there any thing reasons
that make the test case : 0 ?

> cap ghep tim dc fai co so dinh ghep dc la maximum (a[i][j]
=0
> coi nhu ko co ca.nh ;) )
> noi chung ba`i na`y anh cung hoi rua, nen ko tra loi ki
dc,
> em thu xem xet cai DN cua thang Mirzayanov Michael xem
the
> nao ;)
>
> QH@

Jivko Ganev Re: i don't know how to answer you, but i think here is a good way to find out it 28 июн 2001 00:28

Of course the vectors are dependend, can't you see that the
last column contains only 0?
Btw for your previous question. Every matrix that contains
the 0 vector has determinant 0 i.e. the vectors are linarly
dependend.

Mirzayanov Michael Defenition of independence for vectors [3] 27 июн 2001 11:23

Vectors a1, a2, ... ,an is not independent iff exist such
numbers b1, b2, ... ,bn that:
1) abs(b1)+abs(b2)+ ... +abs(bn)>0
2) a1*b1+a2*b2+ ... +an*bn=0

Dinh Hong Minh Re: Defenition of independence for vectors [2] 28 июн 2001 15:44

You are Saratov #3 ?

Mirzayanov Michael Re: You are Saratov #3 ? [1] 28 июн 2001 17:40

No, I am the member of SaratovSU #3 team :)
How is your question connect with defenition of
independence?

Dinh Hong Minh curious ;-) 28 июн 2001 23:57

> No, I am the member of SaratovSU #3 team :)
> How is your question connect with defenition of
> independence?

Vua moi chay xuong nha xem phim duoc 1 ty, len chung no da lam x Does left-single-quote is #145 and right-single-quote is #39 in ASCII? // Задача 1050. Подготавливая статью 28 июн 2001 23:53

Tran Nam Trung (trungduck@yahoo.com) Yes, this Prob is easy but I get "Wrong answer". Can u tell me what is the last empty line for ? Is there any points that we should consider ? // Задача 1089. Проверка со словарём 28 июн 2001 17:49

Dinh Hong Minh Marat, Pavel, we respected you, but you don't. We asked but you don't aswer. [5] 24 июн 2001 12:49

NONAME00 Can someone submit problems? [1] 24 июн 2001 11:55

Dan Ghinea What happens if the number of digits is odd? [1] // Задача 1044. Счастливые билеты. Easy! 24 июн 2001 02:07

NONAME00 What's the matter with the server?! 23 июн 2001 20:13

Tran Nam Trung (trungduck@yahoo.com) What's matter with you ? [1] 23 июн 2001 10:08

Kulama CANNOT USE ONLINE JUDGE TO SUBMIT PROBLEM? 23 июн 2001 08:01

tomato Ffffffffffff! Steven Sivek , my cousin, why is not me in IOIteam :'''''( ????? [2] 20 июн 2001 17:27

HNT Who can submit solutions by e-mail ? 21 июн 2001 23:55

Roger Who can help me? Thank you! 21 июн 2001 18:35

Tran Nam Trung (trungduck@yahoo.com) Let me know what is the limit of number system ? I mean what is the range of it ? (Last time DQH didn't tell me) ! [1] // Задача 1071. Никифор 2 21 июн 2001 17:26

tomato Hehe Dinh Quang Hiep (DSAP Group) but .... [1] 21 июн 2001 15:14

Tran Nam Trung (trungduck@yahoo.com) I was so disappointed because I couldn't use this site for a long time ! 21 июн 2001 17:18

Le Phuoc Hai Son WA // Задача 1018. Двоичная яблоня 20 июн 2001 19:37

I don't know why i am get WA.
Admin can you send me any tests and solutions.
Anyone can help me find the errors:

{I use dynamic programming}
Program ACM1018;
Const max=100;
Var n,q,t:byte;
    qhd:array[0..max,0..max] of longint;
    mg1:array[0..100] of record
rank,n1,n2:byte;app:integer;end;
    mg:array[1..100] of record i,j:byte;k:integer;end;

Procedure readin;
Var i,count:byte;
Begin
     Readln(n,q);if q=n then q:=n-1;
     For i:=1 to n-1 do
         begin
         readln(mg[i].i,mg[i].j,mg[i].k);
         end;
     {********}
     count:=n-1;t:=1;
     fillchar(mg1,sizeof(mg1),0);mg1[1].rank:=1;
     Repeat
           For i:=1 to n-1 do
               begin
                    if (mg1[mg[i].i].rank=t) and (mg1[mg
[i].j].rank=0) then
                       begin
                            if mg1[mg[i].i].n1=0 then mg1[mg
[i].i].n1:=mg[i].j
                                                 else if mg1
[mg[i].i].n2=0 then mg1[mg[i].i].n2:=mg[i].j;
                            mg1[mg[i].j].app:=mg[i].k;
                            mg1[mg[i].j].rank:=t+1;dec
(count);
                       end;
                    if (mg1[mg[i].j].rank=t) and (mg1[mg
[i].i].rank=0) then
                       begin
                            if mg1[mg[i].j].n1=0 then mg1[mg
[i].j].n1:=mg[i].i
                                                 else if mg1
[mg[i].j].n2=0 then mg1[mg[i].i].n2:=mg[i].i;
                            mg1[mg[i].i].app:=mg[i].k;
                            mg1[mg[i].i].rank:=t+1;dec
(count);
                       end;
               end;
           inc(t);
     Until count=0;

End;

Procedure dynamic;
Var i,j,k,l,m:byte;temp:longint;
Begin
     fillchar(qhd,sizeof(qhd),0);
     For i:=t downto 1 do
         Begin
              For j:=1 to n do
                  if mg1[j].rank=i then
                  begin
                  if mg1[j].n1=0 then begin qhd[j,1]:=mg1
[j].app;qhd[j,0]:=1;end
                  else
                  begin
                       qhd[j,1]:=mg1[j].app;qhd[j,0]:=1;
                       if qhd[mg1[j].n1,0]>0 then For k:=1
to qhd[mg1[j].n1,0] do
                           begin
                                if qhd[j,k+1]<qhd[mg1
[j].n1,k]+mg1[j].app then qhd[j,k+1]:=qhd[mg1[j].n1,k]+mg1
[j].app;
                                if k+1>qhd[j,0] then qhd
[j,0]:=k+1;
                                if qhd[mg1[j].n2,0]>0 then
For l:=1 to qhd[mg1[j].n2,0] do
                                    begin
                                        if qhd[j,l+1]<qhd
[mg1[j].n2,l]+mg1[j].app then qhd[j,l+1]:=qhd[mg1[j].n2,l]
+mg1[j].app;
                                        if l+1>qhd[j,0]
then qhd[j,0]:=l+1;
                                        m:=k+l+1;
                                        if m>qhd[j,0] then
qhd[j,0]:=m;
                                        temp:=qhd[mg1
[j].n1,k]+qhd[mg1[j].n2,l]+mg1[j].app;
                                        if qhd[j,m]<temp
then qhd[j,m]:=temp;
                                    end;

                           end;
                       if qhd[j,0]>q-mg1[j].rank+2 then qhd
[j,0]:=q-mg1[j].rank+2;
                       if qhd[j,0]<0 then qhd[j,0]:=0;
                  end;
                  end;
         End;
End;

Begin
     readin;
     dynamic;
     writeln(qhd[1,q+1]);
End.

Le Phuoc Hai Son WA // Задача 1018. Двоичная яблоня 20 июн 2001 19:36

I don't know why i am get WA.
Admin can you send me any tests and solutions.
Anyone can help me find the errors:

{I use dynamic programming}
Program ACM1018;
Const max=100;
Var n,q,t:byte;
    qhd:array[0..max,0..max] of longint;
    mg1:array[0..100] of record
rank,n1,n2:byte;app:integer;end;
    mg:array[1..100] of record i,j:byte;k:integer;end;

Procedure readin;
Var i,count:byte;
Begin
     Readln(n,q);if q=n then q:=n-1;
     For i:=1 to n-1 do
         begin
         readln(mg[i].i,mg[i].j,mg[i].k);
         end;
     {********}
     count:=n-1;t:=1;
     fillchar(mg1,sizeof(mg1),0);mg1[1].rank:=1;
     Repeat
           For i:=1 to n-1 do
               begin
                    if (mg1[mg[i].i].rank=t) and (mg1[mg
[i].j].rank=0) then
                       begin
                            if mg1[mg[i].i].n1=0 then mg1[mg
[i].i].n1:=mg[i].j
                                                 else if mg1
[mg[i].i].n2=0 then mg1[mg[i].i].n2:=mg[i].j;
                            mg1[mg[i].j].app:=mg[i].k;
                            mg1[mg[i].j].rank:=t+1;dec
(count);
                       end;
                    if (mg1[mg[i].j].rank=t) and (mg1[mg
[i].i].rank=0) then
                       begin
                            if mg1[mg[i].j].n1=0 then mg1[mg
[i].j].n1:=mg[i].i
                                                 else if mg1
[mg[i].j].n2=0 then mg1[mg[i].i].n2:=mg[i].i;
                            mg1[mg[i].i].app:=mg[i].k;
                            mg1[mg[i].i].rank:=t+1;dec
(count);
                       end;
               end;
           inc(t);
     Until count=0;

End;

Procedure dynamic;
Var i,j,k,l,m:byte;temp:longint;
Begin
     fillchar(qhd,sizeof(qhd),0);
     For i:=t downto 1 do
         Begin
              For j:=1 to n do
                  if mg1[j].rank=i then
                  begin
                  if mg1[j].n1=0 then begin qhd[j,1]:=mg1
[j].app;qhd[j,0]:=1;end
                  else
                  begin
                       qhd[j,1]:=mg1[j].app;qhd[j,0]:=1;
                       if qhd[mg1[j].n1,0]>0 then For k:=1
to qhd[mg1[j].n1,0] do
                           begin
                                if qhd[j,k+1]<qhd[mg1
[j].n1,k]+mg1[j].app then qhd[j,k+1]:=qhd[mg1[j].n1,k]+mg1
[j].app;
                                if k+1>qhd[j,0] then qhd
[j,0]:=k+1;
                                if qhd[mg1[j].n2,0]>0 then
For l:=1 to qhd[mg1[j].n2,0] do
                                    begin
                                        if qhd[j,l+1]<qhd
[mg1[j].n2,l]+mg1[j].app then qhd[j,l+1]:=qhd[mg1[j].n2,l]
+mg1[j].app;
                                        if l+1>qhd[j,0]
then qhd[j,0]:=l+1;
                                        m:=k+l+1;
                                        if m>qhd[j,0] then
qhd[j,0]:=m;
                                        temp:=qhd[mg1
[j].n1,k]+qhd[mg1[j].n2,l]+mg1[j].app;
                                        if qhd[j,m]<temp
then qhd[j,m]:=temp;
                                    end;

                           end;
                       if qhd[j,0]>q-mg1[j].rank+2 then qhd
[j,0]:=q-mg1[j].rank+2;
                       if qhd[j,0]<0 then qhd[j,0]:=0;
                  end;
                  end;
         End;
End;

Begin
     readin;
     dynamic;
     writeln(qhd[1,q+1]);
End.

Tran Nam Trung (trungduck@yahoo.com) TO ADMINS : WHY DON'T YOU ANSWER OUR QUESTIONS ? ARE YOU BUSY NOW ? [2] 20 июн 2001 17:08

tomato Hehe Dinh Quang Hiep (DSAP Group) [1] 20 июн 2001 17:01

Dinh Hong Minh Stefan Pochmann - the most economical person in the world. [3] 19 июн 2001 23:11