Show all threads Hide all threads Show all messages Hide all messages | Hint | Конобейцев Иван Олегович | 1124. Mosaic | 9 Oct 2022 14:42 | 1 | Hint Конобейцев Иван Олегович 9 Oct 2022 14:42 Amount of pieces to move, edges to make euler path(only pieces with (in[i] + out[i]) > 0) and amount of components | If you WA #3, look at this simple case | jacketinsysu | 1124. Mosaic | 4 Aug 2021 14:09 | 3 | 4 3 1 1 1 2 2 2 3 3 3 4 4 4 > 0 my solution is: edge number + component number - 1. | Why move the hand? | [SPb NRU ITMO] Niyaz Nigmatullin | 1124. Mosaic | 20 Dec 2020 15:10 | 5 | 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 | How to solve with Kotlin | vodka2 | 1124. Mosaic | 25 Aug 2020 21:48 | 1 | 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. | AC | qwertyqwe | 1124. Mosaic | 7 Sep 2019 13:54 | 1 | AC qwertyqwe 7 Sep 2019 13:54 Please, could you send your problem(AC code) | how to do? | Czw's Brother | 1124. Mosaic | 8 Oct 2012 02:55 | 4 | 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))) | Solve | Eatmyshit | 1124. Mosaic | 14 Sep 2010 14:58 | 1 | Solve Eatmyshit 14 Sep 2010 14:58 | WA #12, T_T Give me some tests plz | Latina_Matrix | 1124. Mosaic | 20 Nov 2008 06:47 | 1 | 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; } | Specal cases... | Yashar Abbasov | 1124. Mosaic | 16 Jun 2008 05:43 | 2 | 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... | Why I get WA? Pelase, help me!!!!!!! (+) | Nazarov Denis (nsc2001@rambler.ru) | 1124. Mosaic | 22 Dec 2007 16:44 | 6 | 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? | WA13 Why!!!! | ZiV | 1124. Mosaic | 25 Sep 2007 19:13 | 2 | 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??? | WA =( show me my mistakes, please! | CExFX | 1124. Mosaic | 22 Aug 2007 03:10 | 5 | 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. | 4Admins : Russian description | PSV | 1124. Mosaic | 4 Apr 2007 02:48 | 1 | in Input format: В следующим M строках находит цвета), числа в строке разделены одним пробелом. Some mistake there - no sense of sentence | Why WA? | Zmy | 1124. Mosaic | 15 Nov 2005 16:34 | 3 | 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. | why I got TL!!!!!!!!!!!! | ACer | 1124. Mosaic | 15 Aug 2003 09:17 | 3 | 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. | why I got TL | ACer | 1124. Mosaic | 14 Aug 2003 09:40 | 2 | 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. > > > > | Where my program fail? | Andrey Popyk (popyk@ief.tup.km.ua) | 1124. Mosaic | 14 Jan 2002 17:43 | 3 | 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! Andrey Popyk (popyk@ief.tup.km.ua) 14 Jan 2002 17:43 Thanks, I ge AC, but I write new version of solution. Simulations doesn't work! | What's the idea of this problem? | Nazarov Denis (nsc2001@rambler.ru) | 1124. Mosaic | 10 Jan 2002 18:00 | 1 | | Mosaic ? Why output is 6 ? | Dinh Quang Hiep (contest submissions only) | 1124. Mosaic | 28 Oct 2001 20:47 | 3 | 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@ |
|
|