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 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)

SUJE-MI PULA

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

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.

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 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;


}

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?

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.

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.

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@