Amount of pieces to move, edges to make euler path(only pieces with (in[i] + out[i]) > 0) and amount of components 4 3 1 1 1 2 2 2 3 3 3 4 4 4 > 0 my solution is: edge number + component number - 1. Why would I move the hand to another box? We only have to put pieces in their places, we don't have to put our hand anywhere into the box. If ur hand fixed on box i, then u can move it to some other position j and it worths 1, but if piece of color j in box i now, u can move it to box j with ur hand Not bad Edited by author 07.12.2020 21:40 Not bad Edited by author 12.12.2020 23:06 If you want to get AC for a Kotlin solution, you should probably use java.util.Scanner instead of readLine() and try multiple times. I was able to get AC only on the second try with the same code, got TLE first time. Please, could you send your problem(AC code) My solution is the following: First read the input and count how many pieces are placed in the wrong boxes(i.e. there color is not the same as the color of the box) lets call that number cnt. You must move these pieces at least once. Then I build a graph for which the boxes are the nodes and there is an edge between two boxes a and b iff there is a piece of color b in the box of color a. After building the graph one should count the number of connected components in it(lets call it count). Now the answer to our problem is simply cnt + max(count-1,0) as one should do at least max(count-1,0) moving of his hand to another box and it is always possible to solve the problem in exactly that many moves of the hand without moving a piece. LSBG, thank you so much, it's the better solution I've ever seen))) This is my program, i tried to fix it 4 6 hours. But no fault's detected. Help me plz.... ----------------------- #include <stdio.h> #include <math.h> #include <iostream> using namespace std; #define DEBUG 0 #define MaxM 510 int t; int m, n; int cnt; int ou[ MaxM]; int a[ MaxM][ MaxM]; void readInput() { cin >> m >> n;
cnt = 0; memset( a, 0, sizeof( a)); memset( ou, 0, sizeof( ou));
for( int i = 1; i <= m; i ++) for( int j = 0; j < n; j ++) { cin >> t; if( t != i) { a[ i][ t] ++; ou[ i] ++; } } } void visit( int index) { if( DEBUG) { cout << "---> " << index; }
for( int i = 1; i <= m; i ++) if( a[ index][ i] != 0 && ou[ i] > 0) { cnt ++; ou[ index] --; a[ index][ i] --;
visit( i); return ; }
for( int i = 1; i <= m; i ++) if( a[ index][ i] != 0) { cnt ++; ou[ index] --; a[ index][ i] --;
visit( i); return ; } } int main() { if( DEBUG) { freopen( "mosaic.in", "r", stdin); freopen( "mosaic.ou", "w", stdout); }
readInput();
for( int i = 1; i <= m; i ++) while( ou[ i] % 2 != 0) { cnt ++; visit( i);
if( DEBUG) { cout << endl; } } for( int i = 1; i <= m; i ++) while( ou[ i] != 0) { cnt ++; visit( i);
if( DEBUG) { cout << endl; } } if( cnt > 0) cout << cnt-1 << endl; else cout << cnt << endl;
return 0; } What are they? Are there any tricky tests? My prog passes all tests on webboard, however i got WA#11. My method is simple: First I find the box where the amount of foreign pieces is maximum. Then I start to move each piece to its own box... If the pieces in this box are arranged successfully then I again move to the box where the amount of foreign pieces is maximum and so on until all pieces are in their own boxes... Where is my mistake? Edited by author 13.05.2008 16:05 Me WA#10 too... I don't know why... My program: Program t1124; Var M,N,i,j,k,a,t :integer; c,s,u :array[1..500]of integer; begin a:=0; for i:=1 to 500 do c[i]:=i; for i:=1 to 500 do s[i]:=0; for i:=1 to 500 do u[i]:=-1; read(m,n); for i:=1 to m do for j:=1 to n do begin read(k); if k<>i then begin a:=a+1; s[k]:=s[k]+1; for t:=1 to m do if c[t]=k then c[t]:=i; end; end; t:=0; for i:=1 to m do if s[i]>0 then begin if u[c[i]]=-1 then u[c[i]]:=0; if s[i] mod 2=1 then u[c[i]]:=u[c[i]]+1; end; for i:=1 to m do if u[i]<>-1 then if (u[i]=0)or(u[i]=2) then t:=t+1 else t:=t+(u[i] div 2); if t>0 then t:=t-1; writeln(a+t); end. 3 3 1 2 2 2 3 3 3 1 1 The answer should be 6, not 7. Good luck. > 3 3 > 1 2 2 > 2 3 3 > 3 1 1 > The answer should be 6, not 7. > > Good luck. My new program: Program t1124; Var M,N,i,j,k,a,t :integer; c,s,u :array[1..500]of integer; begin a:=0; for i:=1 to 500 do c[i]:=i; for i:=1 to 500 do s[i]:=0; for i:=1 to 500 do u[i]:=-1; read(m,n); for i:=1 to m do for j:=1 to n do begin read(k); if k<>i then begin a:=a+1; s[k]:=s[k]+1; for t:=1 to m do if c[t]=c[k] then c[t]:=c[i]; end; end; t:=0; {for i:=1 to m do if s[i]>0 then begin if u[c[i]]=-1 then u[c[i]]:=0; if s[i] mod 2=1 then u[c[i]]:=u[c[i]]+1; end; for i:=1 to m do if u[i]<>-1 then if (u[i]=0)or(u[i]=2) then t:=t+1 else t:=t+(u[i] div 2);} for i:=1 to m do begin if c[i]<>0 then t:=t+1; for j:=i+1 to m do if c[j]=c[i] then c[j]:=0; end; if t>0 then t:=t-1; writeln(a+t); end. 2 1 1 2 The answer is 0. Good luck! Thank for you help!But I still get WA!.I don't know what's wrong. I have 2 programs. But they both wrong!!!. Please, help me!!! May be my algorithm is wrong??! \\\\\\\Program I: Program t1124; Var M,N,i,j,k,a,t :integer; c,s,u :array[1..500]of integer; begin a:=0; for i:=1 to 500 do c[i]:=i; for i:=1 to 500 do s[i]:=0; for i:=1 to 500 do u[i]:=-1; read(m,n); for i:=1 to m do for j:=1 to n do begin read(k); if k<>i then begin a:=a+1; s[k]:=s[k]+1; for t:=1 to m do if c[t]=c[k] then c[t]:=c[i]; end; end; t:=0; for i:=1 to m do if s[i]>0 then begin if u[c[i]]=-1 then u[c[i]]:=0; if s[i] mod 2=1 then u[c[i]]:=u[c[i]]+1; end; for i:=1 to m do begin if (c[i]<>0)and(s[i]<>0) then t:=t+1; for j:=i+1 to m do if c[j]=c[i] then c[j]:=0; end; if t>0 then t:=t-1; writeln(a+t); end. \\\\\\\\Program II: Program t1124; Var M,N,i,j,k,a,t :integer; c,s,u :array[1..500]of integer; begin a:=0; for i:=1 to 500 do c[i]:=i; for i:=1 to 500 do s[i]:=0; for i:=1 to 500 do u[i]:=-1; read(m,n); for i:=1 to m do for j:=1 to n do begin read(k); if k<>i then begin a:=a+1; s[k]:=s[k]+1; for t:=1 to m do if c[t]=c[k] then c[t]:=c[i]; end; end; t:=0; for i:=1 to m do if s[i]>0 then begin if u[c[i]]=-1 then u[c[i]]:=0; if s[i] mod 2=1 then u[c[i]]:=u[c[i]]+1; end; for i:=1 to m do if u[i]<>-1 then if (u[i]=0)or(u[i]=2) then t:=t+1 else t:=t+(u[i] div 2); if t>0 then t:=t-1; writeln(a+t); end. My method is similar with yours. I have WA#13. my prog passed all tests that i had.I can't find my mistake. can anyone give me some tricky tests for this problem? Const MaxN = 500; Answer is sum of edjes in graph and subgraphs(except graphs with one vertex)... Var n,m,i,j,k,x: longint; b,c : array[1..MaxN] of Word; BEGIN Read(m,n); K := 0; Fillchar(c,sizeof(c),0); For i := 1 to m do b[i] := i; For i := 1 to m do For j := 1 to n do Begin Read(x); if x <> i then Inc(k); // I count number of edjes b[x] := b[i]; End; For i := 1 to m do Begin Inc(c[b[i]]); if c[b[i]] = 2 then Inc(k); // Here i count number of subgraphs End; Writeln(k-1+byte((k-1)<0)); END. I am WA too.... who can give us any hits??? I have WA and I don't know why. All tests I've done gave me right answers. Somebody, please help me, show me my mistakes!!! Text of program(С++): #include <iostream.h> void main() { short M,N; int j; cout<<"Enter amounts of colors and pieces\n"; cin>>M>>N; cout<<"\nEnter all pieces\n"; short a[500][50]; for (int i=0; i<M; i++) for ( j=0; j<N; j++) cin>>a[i][j]; short t,z,u=0,kolvo=0,p=0,q=0; do { for ( i=0; i<M; i++) for ( j=0; j<N; j++) if(a[i][j]!=(i+1)) { p=j; q=i; if(u==0) t=a[i][j]; else { z=a[i][j]; a[i][j]=t; t=z; } kolvo++;
for (int k=0; k<N; k++) if (a[t-1][k]!=t) { z=a[t-1][k]; a[t-1][k]=t; t=z; u=1; kolvo++; } if (N==1)i=t-2; else i=t-1; j=0;
} }while((i<M)&&(j<N)); if(u==1) kolvo--; cout<<"\nAnswer is="<<kolvo; } You haven't to write some code like cout<<"Enter amounts of colors and pieces\n"; and read FAQ before using Online Judge Thank you, but sill WA on 6th test. =( Try to change short into int>Maybe then you'll get AC. I've already tried to do as you say,but still WA. in Input format: В следующим M строках находит цвета), числа в строке разделены одним пробелом. Some mistake there - no sense of sentence The number of movements=the number of lines in the graphs+the numbers of subgraphs(except the subgraphs with only one point)-1.Isn't it correct? But i got a WA. What's the matter? > The number of movements=the number of lines in the graphs+the numbers > of subgraphs(except the subgraphs with only one point)-1.Isn't it > correct? > But i got a WA. What's the matter? This is my solution too . I got WA . And I don't know why . Maybe your error is this : if the grapf has 0 edges ... Here is a test : 3 1 1 2 3 The solution is 0 not -1 . Thank you very much I just change -1 to 0 then get accepted. If you still wa i can give you my program. var l,m,n,i,j,t,total,s:longint; closed,open,now:longint; a:array[0..500,0..500] of integer; b:array[1..500]of boolean; function done(d,p:longint):boolean; var k:longint; begin done:=false; for k:=1 to a[d,0] do if a[d,k]=p then exit; done:=true; end; begin read(m); read(n); for i:=1 to m do for j:=1 to n do begin read(t); if t<>i then begin if done(i,t) then begin inc(a[i,0]); a[i,a[i,0]]:=t; b[i]:=true; end; inc(s); end; end; for i:=1 to m do if b[i] then begin closed:=a[i,0]; open:=0; while open<closed do begin now:=0; for j:=open+1 to closed do for l:=1 to a[a[i,j],0] do if done(i,a[a[i,j],l]) then begin a[i,closed+now+1]:=a[a[i,j],l] ; inc(now); end; open:=closed; closed:=closed+now; a[i,0]:=closed; end; inc(total); for j:=1 to a[i,0] do b[a[i,j]]:=false; end; if total=0 then writeln(0) else writeln(s+total-1); end. > var l,m,n,i,j,t,total,s:longint; > closed,open,now:longint; > > a:array[0..500,0..500] of integer; > b:array[1..500]of boolean; > > function done(d,p:longint):boolean; > var k:longint; > begin > done:=false; > for k:=1 to a[d,0] do > if a[d,k]=p then exit; > done:=true; > end; > begin > read(m); > read(n); > for i:=1 to m do > for j:=1 to n do begin > read(t); > if t<>i then begin > if done(i,t) then > begin > inc(a[i,0]); > a[i,a[i,0]]:=t; > b[i]:=true; > end; > inc(s); > end; > end; > for i:=1 to m do > if b[i] then begin > closed:=a[i,0]; > open:=0; > while open<closed do begin > now:=0; > for j:=open+1 to closed do > for l:=1 to a[a[i,j],0] do > if done(i,a[a[i,j],l]) then begin > a[i,closed+now+1]:=a[a[i,j],l] ; > inc(now); > end; > open:=closed; > closed:=closed+now; > a[i,0]:=closed; > end; > > inc(total); > for j:=1 to a[i,0] do b[a[i,j]]:=false; > end; > if total=0 then writeln(0) > else writeln(s+total-1); > end. > > var l,m,n,i,j,t,total,s:longint; > > closed,open,now:longint; > > > > a:array[0..500,0..500] of integer; > > b:array[1..500]of boolean; > > > > function done(d,p:longint):boolean; > > var k:longint; > > begin > > done:=false; > > for k:=1 to a[d,0] do > > if a[d,k]=p then exit; > > done:=true; > > end; > > begin > > read(m); > > read(n); > > for i:=1 to m do > > for j:=1 to n do begin > > read(t); > > if t<>i then begin > > if done(i,t) then > > begin > > inc(a[i,0]); > > a[i,a[i,0]]:=t; > > b[i]:=true; > > end; > > inc(s); > > end; > > end; > > for i:=1 to m do > > if b[i] then begin > > closed:=a[i,0]; > > open:=0; > > while open<closed do begin > > now:=0; > > for j:=open+1 to closed do > > for l:=1 to a[a[i,j],0] do > > if done(i,a[a[i,j],l]) then begin > > a[i,closed+now+1]:=a[a[i,j],l] ; > > inc(now); > > end; > > open:=closed; > > closed:=closed+now; > > a[i,0]:=closed; > > end; > > > > inc(total); > > for j:=1 to a[i,0] do b[a[i,j]]:=false; > > end; > > if total=0 then writeln(0) > > else writeln(s+total-1); > > end. var n,m,i,j,t,s:longint; a:array[0..100,0..100]of longint; l:boolean; procedure done(dep:longint); var k:longint; begin for k:=1 to n do if a[dep,k]>0 then begin inc(s); dec(a[dep,k]); dec(a[dep,0]); done(k); end; end; begin read(n); read(m); for i:=1 to n do for j:=1 to m do begin read(t); if t<>I then begin inc(a[i,t]);inc(a[i,0]);end; end; l:=false; for i:=1 to n do if a[i,0]>0 then begin for j:=1 to n do if a[i,j]>0 then begin inc(s); dec(a[i,j]); dec(a[i,0]); done(j); end; inc(s); l:=true; end; if l then s:=s-1; writeln(s); end. > var n,m,i,j,t,s:longint; > a:array[0..100,0..100]of longint; > > l:boolean; > procedure done(dep:longint); > var k:longint; > begin > for k:=1 to n do > if a[dep,k]>0 then begin > inc(s); > dec(a[dep,k]); > dec(a[dep,0]); > done(k); > end; > end; > begin > read(n); > read(m); > for i:=1 to n do > for j:=1 to m do > begin > read(t); > if t<>I then begin inc(a[i,t]);inc(a[i,0]);end; > > end; > > l:=false; > for i:=1 to n do > > if a[i,0]>0 then begin > for j:=1 to n do > if a[i,j]>0 then begin > inc(s); > dec(a[i,j]); > dec(a[i,0]); > done(j); > end; > inc(s); > l:=true; > end; > if l then s:=s-1; > writeln(s); > end. > > > > I use simple simulation of "hand moves". I cannot create a test, where my program fail, but I have received WA :-( Could anyone tell me, where is my bug? VAR A:Array[1..500,1..50] of integer; M,N:integer; PROCEDURE ReadData; var P,i,j:integer; begin readln(M,N); for i:=1 to M do begin for j:=1 to N do read(A[i][j]); readln; end; end; FUNCTION MakeChanges(K,P:integer):longint; var Sum:longint; C,i:integer; bool:boolean; begin Sum:=0; repeat inc(Sum); C:=A[K][P]; A[K][P]:=K; bool:=true; for i:=1 to N do if A[C][i]<>C then begin bool:=false; K:=C; P:=i; break end; until bool; MakeChanges:=Sum; end; PROCEDURE Process; var i,j:integer; Sum:longint; begin Sum:=0; for i:=1 to M do for j:=1 to N do if A[i][j]<>i then Sum:=Sum+MakeChanges(i,j); writeln(Sum); end; BEGIN ReadData; Process; END. For example, for this test: 4 1 2 1 4 3 The answer is 5, not 4. Thanks, I ge AC, but I write new version of solution. Simulations doesn't work! please tell me, i think the output should be 5 at first there are 3 box must be change (1 1 1) (2 3 3) (1 2 2) 1st move : (1 1 ) (2 3 3 ) (1 2 2 3) (hand at box 3) 2nd move : (1 1 ) (2 2 3 3) (1 2 3 ) (hand at box 2) 3rd move : (1 1 ) (2 2 3 ) (1 2 3 3) (hand at box 3) 4th move : (1 1 ) (2 2 2 3) (1 3 3 ) (hand at box 2) 5th move : (1 1 ) (2 2 2 ) (1 3 3 3) (hand at box 3) 6th move : (1 1 1 ) (2 2 2 ) (3 3 3 ) (hand at box 1) but the 6th move from box 3 towards box 1, so it "doesn't take into account", so, the output is 5 ?????? pls explain me about this :( QH@ I think you misunderstand this problem. The prob say that the movement to the first box you choose "doesn't take into account" not to the box number one. For ex, in 1st move, you take hand to box 1( "doesn't take into account" ), take mosaic 3 to box 3 and continue as you say. The 6th move will take into account. Hope you understand. mailto : trungduck@yahoo.com > please tell me, i think the output should be 5 > at first there are 3 box must be change > (1 1 1) (2 3 3) (1 2 2) > 1st move : (1 1 ) (2 3 3 ) (1 2 2 3) (hand at box 3) > 2nd move : (1 1 ) (2 2 3 3) (1 2 3 ) (hand at box 2) > 3rd move : (1 1 ) (2 2 3 ) (1 2 3 3) (hand at box 3) > 4th move : (1 1 ) (2 2 2 3) (1 3 3 ) (hand at box 2) > 5th move : (1 1 ) (2 2 2 ) (1 3 3 3) (hand at box 3) > 6th move : (1 1 1 ) (2 2 2 ) (3 3 3 ) (hand at box 1) > > but the 6th move from box 3 towards box 1, so it "doesn't > take into account", so, the output is 5 ?????? pls explain > me about this :( > > QH@ > I think you misunderstand this problem. The prob say that > the movement to the first box you choose "doesn't take into > account" not to the box number one. For ex, in 1st move, > you take hand to box 1( "doesn't take into account" ), take > mosaic 3 to box 3 and continue as you say. The 6th move > will take into account. > Hope you understand. > mailto : trungduck@yahoo.com > > > > please tell me, i think the output should be 5 > > at first there are 3 box must be change > > (1 1 1) (2 3 3) (1 2 2) > > 1st move : (1 1 ) (2 3 3 ) (1 2 2 3) (hand at box 3) > > 2nd move : (1 1 ) (2 2 3 3) (1 2 3 ) (hand at box 2) > > 3rd move : (1 1 ) (2 2 3 ) (1 2 3 3) (hand at box 3) > > 4th move : (1 1 ) (2 2 2 3) (1 3 3 ) (hand at box 2) > > 5th move : (1 1 ) (2 2 2 ) (1 3 3 3) (hand at box 3) > > 6th move : (1 1 1 ) (2 2 2 ) (3 3 3 ) (hand at box 1) > > > > but the 6th move from box 3 towards box 1, so it "doesn't > > take into account", so, the output is 5 ?????? pls > explain > > me about this :( > > > > QH@ |
|