OJ Board

The Online Judge board
https://onlinejudge.org/board/

116 - Unidirectional TSP

https://onlinejudge.org/board/viewtopic.php?t=1114

Page 7 of 16

Posted: Sat Jun 19, 2004 6:34 pm
by SilentStrike
I reversed it. Instead of trying to find minimum sum from left to right, it goes from right to left. Now it works. I have no clue why, I think they should both give the same answer. Here is the working solution.

Code: Select all

// http://acm.uva.es/p/v1/116.html

#include <iostream>
#include <climits>
using namespace std;

int rows; // 1 <= rows <= 10
int cols; // 1 <= cols <= 1000

const int max_rows = 12;
const int max_cols = 1020;
int in[max_rows][max_cols];
int next[max_rows][max_cols];
int sum[max_rows][max_cols];
int back[max_rows][max_cols];

void show_graph(int g[max_rows][max_cols]) {
  for (int i = 1; i <= rows; ++i) {
    for (int j = 1; j <= cols; ++j) {
      cout << g[i][j] << '\t';
    }
    cout << '\n';
  }
  cout << '\n';
}

int wrap_row(int dir, int i) {
  int selected_row = i + dir;
  if (selected_row == 0) selected_row = rows;
  if (selected_row > rows) selected_row = 1;
  return selected_row;
}

void play() {

  for (int i = 1; i <= rows; ++i) sum[i][cols] = in[i][cols];

  for (int j = cols - 1; j > 0 ; --j) {
    for (int i = 1; i <= rows; ++i) {
      int best_sum=INT_MAX;
      for (int dir = -1; dir <= 1; ++dir) {
        int selected_row = wrap_row(dir, i);
        int selected_sum = in[i][j] + sum[selected_row][j + 1];
        if (selected_sum < best_sum) best_sum = selected_sum;
      }
      for (int dir = -1; dir <= 1; ++dir) {
        int selected_row = wrap_row(dir, i);
        int selected_sum = in[i][j] + sum[selected_row][j + 1];
        if (selected_sum == best_sum) next[i][j] |= (1 << (dir + 1));
      }
      sum[i][j] = best_sum;
    }
    //show_graph(sum);
  }
  
  int min_sum = sum[1][1];
  for (int i = 1; i <= rows; ++i) 
    if (sum[i][1] < min_sum) min_sum = sum[i][1];
  
  /*show_graph(sum);
  show_graph(next);
  show_graph(back);
  */

  int lex_best_row;
  for (int i = 1; i <= rows; ++i) 
    if (sum[i][1] == min_sum) {
      lex_best_row = i;
      break;    
    }
  
  if (cols == 1) {
    cout << lex_best_row << '\n' << min_sum << '\n';
    return;
  }

  for (int j = 1; j < cols; ++j) {
    cout << lex_best_row;
    int this_best_row = INT_MAX;
    for (int dir = -1; dir <= 1; ++dir) {
      if (next[lex_best_row][j] & (1 << (dir + 1))) {
        int this_row = wrap_row(lex_best_row, dir);
        if (this_row < this_best_row) this_best_row = this_row;
      }
    }
    lex_best_row = this_best_row;
    cout << ' ';
  }
  cout << lex_best_row << '\n';
  //show_graph(sum);
  cout << min_sum << '\n';
}

int main() {

  while (cin >> rows >> cols) {
    for (int i = 1; i <= rows; ++i) {
      for (int j = 1 ; j <= cols; ++j) {
        cin >> in[i][j];
        back[i][j] = next[i][j] = 0;
      }
    }
    play();
  }

  return 0;
}

Posted: Sun Jun 20, 2004 8:39 am
by angga888
SilentStrike wrote:I reversed it. Instead of trying to find minimum sum from left to right, it goes from right to left. Now it works. I have no clue why, I think they should both give the same answer.
Yes, I'm also using the same method. Be careful with lexicographical order. Instead of working from left to right, it is easier to work from right to left.

Nice test case

Posted: Mon Jun 21, 2004 5:20 pm
by SilentStrike
Here is a test case that my original program failed on. Maybe yours will too.

10 10
9 0 9 9 9 9 9 9 9 9
9 9 0 9 2 2 1 1 1 1
9 9 9 2 9 9 9 9 9 9
1 1 1 1 9 9 9 9 9 9
9 9 9 9 1 1 1 1 1 1
9 9 9 9 9 9 9 9 9 9
9 9 9 9 9 9 9 9 9 9
9 9 9 9 9 9 9 9 9 9
9 9 9 9 9 9 9 9 9 9
0 9 9 9 9 9 9 9 9 9

Correct Answer is
4 4 4 4 5 5 5 5 5 5
10

My first program gave the incorrect answer of
4 4 4 3 2 2 2 2 2 2
10

Hope this helps.

Thanks to your input_output

Posted: Tue Jun 22, 2004 12:15 pm
by Rajib
Thank you very much SilentStrike. You post a beautiful sample input. It help me a lot to find the bug in my code.

Before testing with this input I was fool enought to find the bug...
It was just a simple mistake. I think most people are doing the same mistake as I do.

Finally I get AC :D .

116 Error, why?

Posted: Sun Jul 11, 2004 6:07 am
by lord_burgos
These is may code

[cpp]
# include <cstdio>
# include <cstring>

typedef struct{ long v, s, r; } TSP;
char index[252][10], ind[252];
TSP t[252][101];

void creaindex(){ for(int i=0;i<252;i++) sprintf(index,"%d",i); }

TSP Camino(int x, int y){
long sum;

sum = t[x-1][y+1].v + t[x-1][y+1].s;
if(t[x][y]. s > sum || ( t[x][y].s == sum && strcmp(index[ind[x-1]],index[ind[t[x][y].r]] ) < 0 )){
t[x][y].s = sum;
t[x][y].r = x-1;
}

sum = t[x][y+1].v + t[x][y+1].s;
if(t[x][y]. s > sum || ( t[x][y].s == sum && strcmp(index[ind[x]] , index[ind[t[x][y].r]]) < 0 )){
t[x][y].s = sum;
t[x][y].r = x;
}

sum = t[x+1][y+1].v + t[x+1][y+1].s;
if(t[x][y]. s > sum || ( t[x][y].s == sum && strcmp( index[ind[x+1]] , index[ind[t[x][y].r]]) < 0 ) ){
t[x][y].s = sum;
t[x][y].r = x+1;
}
return t[x][y];
}

void exploraTSP(int n, int m){
long i,j;
for(i=m-2;i>=0;i--)
for(j=1;j<n-1;j++)
t[j] = Camino(j,i);
}

void imprimeTSP(int x, int y,int m){
if(y == m) return;
printf("%d ",ind[x]);
imprimeTSP(t[x][y].r,y+1,m);
}


main(){
long n,m,i,j,k, pos, min;
char num[10];
FILE *pf;

# if defined(ONLINE_JUDGE)
pf = stdin;
# else
pf = fopen("input.txt","r");
# endif

creaindex();
while(fscanf(pf,"%ld %ld",&n,&m) != EOF){
for(i=0;i<n;i++)
for(j=0;j<m;j++){
ind = i+1;
fscanf(pf,"%lld",&t[j].v);
t[j].s = (j == m-1)?0:200000000;
t[j].r = 250;
}
for(k=0;k<n;i++,k++)
for(j=0;j<m;j++){
ind = k+1;
t[j].v = t[k][j].v;
t[j].s = (j == m-1)?0:200000000;
t[j].r = 250;
}
for(k=0;k<n;i++,k++)
for(j=0;j<m;j++){
ind[i] = k+1;
t[i][j].v = t[k][j].v;
t[i][j].s = (j == m-1)?0:200000000;
t[i][j].r = 250;
}

exploraTSP(3*n,m);


min = 200000000;
pos = 0;
for(i=n;i<2*n;i++){
if(t[i][0].v + t[i][0].s < min){
min = t[i][0].v + t[i][0].s;
pos = i;
}
else
if(t[i][0].v + t[i][0].s == min && strcmp(index[ind[i]],index[ind[pos]]) < 0){
min = t[i][0].v + t[i][0].s;
pos = i;
}
}

imprimeTSP(pos,0,m); printf("\n");
printf("%d\n", min);
}
return 0;
}

[/cpp]


My program write:

Input:
[c]
10 10
9 0 9 9 9 9 9 9 9 9
9 9 0 9 2 2 1 1 1 1
9 9 9 2 9 9 9 9 9 9
1 1 1 1 9 9 9 9 9 9
9 9 9 9 1 1 1 1 1 1
9 9 9 9 9 9 9 9 9 9
9 9 9 9 9 9 9 9 9 9
9 9 9 9 9 9 9 9 9 9
9 9 9 9 9 9 9 9 9 9
0 9 9 9 9 9 9 9 9 9
[/c]
output:
[c]
10 1 2 3 2 2 2 2 2 2
10
[/c]

What is my error?

Be VERY careful for the condition lexicographically smallest

Posted: Thu Jul 15, 2004 10:43 am
by jackie
Finally got AC (DP left to right)

Nothing special for the input and output .

[cpp]for (i = 0; i < m; ++i)
for (j = 0; j < n; ++j)
scanf("%d", &grid[j]);[/cpp]

difficult to find the lexicographically smallest one

some test input for debugging coming from the forum

5 6
3 4 1 2 8 6
6 1 8 2 7 4
5 9 3 9 9 5
8 4 1 3 2 6
3 7 2 8 6 4

5 6
3 4 1 2 8 6
6 1 8 2 7 4
5 9 3 9 9 5
8 4 1 3 2 6
3 7 2 1 2 3

2 2
9 10
9 10

5 4
9 1 9 9
1 9 9 9
9 9 9 9
1 1 1 1
9 9 1 9

5 6
-3 -4 -1 -2 -8 -6
-6 -1 -8 -2 -7 -4 -5 -9 -3 -9 -9 -5
-8 -4 -1 -3 -2 -6 -3 -7 -2 -8 -6 -4

4 7
1 2 -3 4 -2 1 5
-1 3 5 -2 6 -3 4
2 1 3 -2 -1 3 1
3 -3 4 2 -3 4 3

5 6
1 1 1 1 1 1
2 2 2 2 2 2
3 3 3 3 3 3
4 4 4 4 4 4
5 5 5 5 5 5

3 4
1 2 3 4
1 2 3 4
1 2 3 4

5 5
1 5 10 6 3
5 1 8 4 11
10 12 5 2 9
7 3 20 5 8
4 1 5 12 6

5 10
11 53 34 73 18 53 99 52 31 54
4 72 24 6 46 17 63 82 89 25
67 22 10 97 99 64 33 45 81 76
24 71 46 62 18 11 54 40 17 51
99 8 57 76 7 51 90 92 51 21

5 10
11 53 1 73 18 53 99 52 31 54
4 72 54 6 46 17 63 82 89 25
67 22 80 97 99 64 33 45 81 76
24 71 46 62 18 11 54 40 17 51
99 8 57 76 7 51 90 92 51 21

5 6
-3 -4 -1 -2 -8 -6
-6 -1 -8 -2 -7 -4 -5 -9 -3 -9 -9 -5
-8 -4 -1 -3 -2 -6 -3 -7 -2 -8 -6 -4

10 100
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

6 8
9 1 9 9 1 1 1 1
1 9 9 1 9 9 9 9
9 9 1 9 9 1 1 1
1 1 9 9 1 9 9 9
9 9 9 1 9 9 9 9
9 9 1 9 9 9 9 9

output:

1 2 3 4 4 5
16
1 2 1 5 4 5
11
1 1
19
2 1 5 4
4
4 3 2 3 3 4
-49
1 4 1 2 1 2 3
-11
1 1 1 1 1 1
6
1 1 1 1
10
1 2 3 2 1
14
2 3 3 2 1 2 3 4 4 5
188
1 5 1 2 1 2 3 4 4 5
172
4 3 2 3 3 4
-49
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
100
2 1 6 5 4 3 3 3
8

116 output please

Posted: Fri Jul 23, 2004 11:41 am
by oriol78
Can anybody post the output for this input please? thanks for advance

12 14
1 2 2 1 1 1 1 1 1 1 1 1 1 2
1 1 2 2 1 1 1 1 1 1 1 1 1 1
1 1 1 2 2 1 1 1 1 1 1 1 1 1
1 1 1 1 2 2 1 1 1 1 1 1 1 1
1 1 1 1 1 2 2 1 1 1 1 1 1 1
1 1 1 1 1 1 2 2 1 1 1 1 1 1
1 1 1 1 1 1 1 2 2 1 1 1 1 1
1 1 1 1 1 1 1 1 2 2 1 1 1 1
1 1 1 1 1 1 1 1 1 2 2 1 1 1
1 1 1 1 1 1 1 1 1 1 2 2 1 1
1 1 1 1 1 1 1 1 1 1 1 2 1 1
1 1 1 1 1 1 1 1 1 1 1 1 2 2

c u.

Posted: Fri Jul 23, 2004 2:15 pm
by Krzysztof Duleba
1 1 10 9 8 7 6 5 4 3 2 11 10 9
14

Posted: Fri Jul 23, 2004 6:28 pm
by oriol78
thanks but...
i think that the row 10 isn't accesible from the row 1, why am i wrong?
the same with 2 and 11
and the result of your sequence is 15,
maybe i don't understand correctly the exercise, plz help me.

Posted: Fri Jul 23, 2004 7:20 pm
by Krzysztof Duleba
That's because your input is incorrect.
For each specification the number of rows will be between 1 and 10 inclusive; the number of columns will be between 1 and 100 inclusive.

116 WA? All test input works!!

Posted: Tue Jul 27, 2004 5:45 pm
by omega
Here's the C++ code
[cpp]#include <iostream.h>
#include <stdio.h>

#ifndef ONLINE_JUDGE
int _fcloseall( void );
FILE *filein = freopen ("input.in", "rt", stdin);
FILE *fileout = freopen ("output.out", "wt", stdout);
#else
FILE *filein = stdin;
FILE *fileout = stdout;
#endif

const int MAX_ROWS = 10;
const int MAX_COLS = 100;

int main(void)
{
int a = 0, b = 0, c = 0;
int n = 0, m = 0;
int total = 0, smallest = 0, weight_top = 0, weight_center = 0, weight_bottom = 0;
int matrix[MAX_ROWS][MAX_COLS][MAX_COLS];
int path[MAX_COLS];
while (cin >> m >> n)
{
for (a = 0; a < m; a++)
for (b = 0; b < n; b++)
cin >> matrix[a][0];
if (n != 1)
{
for (a = 1; a < n; a++)
for (b = 0; b < n - a; b++)
for (c = 0; c < m; c++)
{
if (c == 0) weight_top = matrix[m-1][b+1][a-1];
else weight_top = matrix[c-1][b+1][a-1];
weight_center = matrix[c][b+1][a-1];
if (c == (m - 1)) weight_bottom = matrix[0][b+1][a-1];
else weight_bottom = matrix[c+1][b+1][a-1];
if ((c > 0 && weight_top <= weight_center && weight_top <= weight_bottom) ||
(c == 0 && weight_top < weight_center && weight_top < weight_bottom))
{matrix[c][a] = weight_top + matrix[c][0];}
else if((c < (m - 1) && weight_center <= weight_bottom) ||
(c == (m - 1) && weight_center < weight_bottom))
{matrix[c][a] = weight_center + matrix[c][0];}
else
{matrix[c][a] = weight_bottom + matrix[c][0];}
}
}
for (a = 0, smallest = matrix[a][0][n-1], path[0] = 0; a < m; a++)
{
if (matrix[a][0][n-1] < smallest)
{
smallest = matrix[a][0][n-1];
path[0] = a;
}
}
if (n != 1)
{
for (a = n - 2, b = 1; a >= 0; a--, b++)
{
if (path[b-1] == 0) weight_top = matrix[m-1][a];
else weight_top = matrix[path[b-1] - 1][a];
weight_center = matrix[path[b-1]][a];
if (path[b-1] == (m - 1)) weight_bottom = matrix[0][b][a];
else weight_bottom = matrix[path[b-1]+1][b][a];
if ((path[b-1] > 0 && weight_top <= weight_center && weight_top <= weight_bottom) ||
(path[b-1] == 0 && weight_top < weight_center && weight_top < weight_bottom))
{path[b] = path[b-1]-1;}
else if((path[b-1] < (m - 1) && weight_center <= weight_bottom) ||
(path[b-1] == (m - 1) && weight_center < weight_bottom))
{path[b] = path[b-1];}
else
{path[b] = path[b-1]+1;}
if (path[b] == -1) path[b] = m - 1;
else if (path[b] == m) path[b] = 0;
}
}
/*for (a = 0; a < n; a++)
{
for (b = 0; b < m; b++)
{
for (c = 0; c < n - a; c++)
printf("%03d ", matrix[b][c][a]);
cout << endl;
}
cout << endl;
}*/
for (a = 0; a < n; a++)
{
cout << (path[a]+1);
if (a != (n - 1)) cout << " ";
else cout << endl;
}
for (a = 0, total = 0; a < n; a++) total+=matrix[path[a]][a][0];
cout << total << endl;
}
return 0;
}
[/cpp]
here's the input file
4
2
9 1
9 9
0 9
0 9
1 1
1
1 2
1 1
10 1
-1
-2
-3
-4
-5
-6
-7
-8
-9
0
2 10
0 9 0 0 0 9 0 0 9 0
9 0 9 0 0 0 9 0 0 0
10 13
0 9 9 9 9 9 9 9 9 0 9 0 0
9 0 9 0 9 9 9 0 9 9 9 0 9
9 9 0 9 9 9 0 9 0 9 0 9 9
9 9 9 0 0 9 9 9 9 0 9 9 9
9 9 9 9 9 0 9 9 9 9 9 9 9
9 9 9 9 9 9 0 9 9 9 9 9 9
9 9 9 9 9 9 9 0 9 9 9 9 9
9 9 9 9 9 9 9 9 0 9 9 9 9
9 9 9 9 9 9 9 9 9 0 9 9 9
9 9 9 9 9 9 9 9 9 9 0 9 0
10 10
9 9 9 9 9 9 9 9 9 9
9 9 9 9 2 2 1 1 1 1
9 9 9 2 9 9 9 9 9 9
1 1 1 1 9 9 9 9 9 9
9 9 9 9 1 1 1 1 1 1
9 9 9 9 9 9 9 9 9 9
9 9 9 9 9 9 9 9 100 9
9 9 9 9 9 9 9 9 9 -100
9 9 9 9 9 9 9 9 9 9
0 9 9 9 9 9 9 9 9 9
5 6
3 4 1 2 8 6
6 1 8 2 7 4
5 9 3 9 9 5
8 4 1 3 2 6
3 7 2 8 6 4

5 6
3 4 1 2 8 6
6 1 8 2 7 4
5 9 3 9 9 5
8 4 1 3 2 6
3 7 2 1 2 3

2 2
9 10
9 10

5 4
9 1 9 9
1 9 9 9
9 9 9 9
1 1 1 1
9 9 1 9

5 6
-3 -4 -1 -2 -8 -6
-6 -1 -8 -2 -7 -4 -5 -9 -3 -9 -9 -5
-8 -4 -1 -3 -2 -6 -3 -7 -2 -8 -6 -4

4 7
1 2 -3 4 -2 1 5
-1 3 5 -2 6 -3 4
2 1 3 -2 -1 3 1
3 -3 4 2 -3 4 3

5 6
1 1 1 1 1 1
2 2 2 2 2 2
3 3 3 3 3 3
4 4 4 4 4 4
5 5 5 5 5 5

3 4
1 2 3 4
1 2 3 4
1 2 3 4

5 5
1 5 10 6 3
5 1 8 4 11
10 12 5 2 9
7 3 20 5 8
4 1 5 12 6

5 10
11 53 34 73 18 53 99 52 31 54
4 72 24 6 46 17 63 82 89 25
67 22 10 97 99 64 33 45 81 76
24 71 46 62 18 11 54 40 17 51
99 8 57 76 7 51 90 92 51 21

5 10
11 53 1 73 18 53 99 52 31 54
4 72 54 6 46 17 63 82 89 25
67 22 80 97 99 64 33 45 81 76
24 71 46 62 18 11 54 40 17 51
99 8 57 76 7 51 90 92 51 21

5 6
-3 -4 -1 -2 -8 -6
-6 -1 -8 -2 -7 -4 -5 -9 -3 -9 -9 -5
-8 -4 -1 -3 -2 -6 -3 -7 -2 -8 -6 -4

10 100
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

6 8
9 1 9 9 1 1 1 1
1 9 9 1 9 9 9 9
9 9 1 9 9 1 1 1
1 1 9 9 1 9 9 9
9 9 9 1 9 9 9 9
9 9 1 9 9 9 9 9

and here's the output

4 1
1
1
1
1 1
2
9
-9
1 2 1 1 1 2 1 1 2 1
0
1 2 3 4 4 5 6 7 8 9 10 1 1
0
4 4 4 4 5 5 6 7 8 8
-67
1 2 3 4 4 5
16
1 2 1 5 4 5
11
1 1
19
2 1 5 4
4
4 3 2 3 3 4
-49
1 4 1 2 1 2 3
-11
1 1 1 1 1 1
6
1 1 1 1
10
1 2 3 2 1
14
2 3 3 2 1 2 3 4 4 5
188
1 5 1 2 1 2 3 4 4 5
172
4 3 2 3 3 4
-49
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
100
2 1 6 5 4 3 3 3
8

ANY help would be nice

WA #116

Posted: Wed Jul 28, 2004 12:22 am
by StevenTang
Guys, can anyone give some help?Thx.
I am exhausted with the problem #116. I've tried all the sample inputs found in the board and all passed.

By the way, I coded in JAVA. I didnot check the row size and column size, since my code works for larger rows and columns, I do not know if I have to.

Code: Select all

Input:

4 2 
9 1 
9 9 
0 9 
0 9 
1 1 
1 
1 2 
1 1 
10 1 
-1 
-2 
-3 
-4 
-5 
-6 
-7 
-8 
-9 
0 
2 10 
0 9 0 0 0 9 0 0 9 0 
9 0 9 0 0 0 9 0 0 0 
10 13 
0 9 9 9 9 9 9 9 9 0 9 0 0 
9 0 9 0 9 9 9 0 9 9 9 0 9 
9 9 0 9 9 9 0 9 0 9 0 9 9 
9 9 9 0 0 9 9 9 9 0 9 9 9 
9 9 9 9 9 0 9 9 9 9 9 9 9 
9 9 9 9 9 9 0 9 9 9 9 9 9 
9 9 9 9 9 9 9 0 9 9 9 9 9 
9 9 9 9 9 9 9 9 0 9 9 9 9 
9 9 9 9 9 9 9 9 9 0 9 9 9 
9 9 9 9 9 9 9 9 9 9 0 9 0 
10 10 
9 9 9 9 9 9 9 9 9 9 
9 9 9 9 2 2 1 1 1 1 
9 9 9 2 9 9 9 9 9 9 
1 1 1 1 9 9 9 9 9 9 
9 9 9 9 1 1 1 1 1 1 
9 9 9 9 9 9 9 9 9 9 
9 9 9 9 9 9 9 9 100 9 
9 9 9 9 9 9 9 9 9 -100 
9 9 9 9 9 9 9 9 9 9 
0 9 9 9 9 9 9 9 9 9 
5 6 
3 4 1 2 8 6 
6 1 8 2 7 4 
5 9 3 9 9 5 
8 4 1 3 2 6 
3 7 2 8 6 4 

5 6 
3 4 1 2 8 6 
6 1 8 2 7 4 
5 9 3 9 9 5 
8 4 1 3 2 6 
3 7 2 1 2 3 

2 2 
9 10 
9 10 

5 4 
9 1 9 9 
1 9 9 9 
9 9 9 9 
1 1 1 1 
9 9 1 9 

5 6 
-3 -4 -1 -2 -8 -6 
-6 -1 -8 -2 -7 -4 -5 -9 -3 -9 -9 -5 
-8 -4 -1 -3 -2 -6 -3 -7 -2 -8 -6 -4 

4 7 
1 2 -3 4 -2 1 5 
-1 3 5 -2 6 -3 4 
2 1 3 -2 -1 3 1 
3 -3 4 2 -3 4 3 

5 6 
1 1 1 1 1 1 
2 2 2 2 2 2 
3 3 3 3 3 3 
4 4 4 4 4 4 
5 5 5 5 5 5 

3 4 
1 2 3 4 
1 2 3 4 
1 2 3 4 

5 5 
1 5 10 6 3 
5 1 8 4 11 
10 12 5 2 9 
7 3 20 5 8 
4 1 5 12 6 

5 10 
11 53 34 73 18 53 99 52 31 54 
4 72 24 6 46 17 63 82 89 25 
67 22 10 97 99 64 33 45 81 76 
24 71 46 62 18 11 54 40 17 51 
99 8 57 76 7 51 90 92 51 21 

5 10 
11 53 1 73 18 53 99 52 31 54 
4 72 54 6 46 17 63 82 89 25 
67 22 80 97 99 64 33 45 81 76 
24 71 46 62 18 11 54 40 17 51 
99 8 57 76 7 51 90 92 51 21 

5 6 
-3 -4 -1 -2 -8 -6 
-6 -1 -8 -2 -7 -4 -5 -9 -3 -9 -9 -5 
-8 -4 -1 -3 -2 -6 -3 -7 -2 -8 -6 -4 

10 100 
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
1 1 1 1 1 1 
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
1 1 1 1 1 1 
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
1 1 1 1 1 1 
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
1 1 1 1 1 1 
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
1 1 1 1 1 1 
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
1 1 1 1 1 1 
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 

6 8 
9 1 9 9 1 1 1 1 
1 9 9 1 9 9 9 9 
9 9 1 9 9 1 1 1 
1 1 9 9 1 9 9 9 
9 9 9 1 9 9 9 9 
9 9 1 9 9 9 9 9

Code: Select all

Output:
4 1
1
1
1
1 1
2
9
-9
1 2 1 1 1 2 1 1 2 1
0
1 2 3 4 4 5 6 7 8 9 10 1 1
0
4 4 4 4 5 5 6 7 8 8
-67
1 2 3 4 4 5
16
1 2 1 5 4 5
11
1 1
19
2 1 5 4
4
4 3 2 3 3 4
-49
1 4 1 2 1 2 3
-11
1 1 1 1 1 1
6
1 1 1 1
10
1 2 3 2 1
14
2 3 3 2 1 2 3 4 4 5
188
1 5 1 2 1 2 3 4 4 5
172
4 3 2 3 3 4
-49
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
100
2 1 6 5 4 3 3 3
8

Code: Select all

This one works ,too.
input: 

10 16 
0 1 0 1 1 1 0 1 1 1 1 1 0 1 1 0 
0 1 1 1 1 0 1 1 1 1 1 0 1 1 0 1 
1 0 0 0 0 1 1 1 1 1 0 1 0 0 1 1 
1 0 0 1 1 1 1 1 1 0 1 1 1 1 1 1 
0 1 1 0 1 1 1 1 0 1 0 1 1 1 1 0 
1 1 1 1 0 0 1 0 1 1 1 0 0 0 0 1 
1 1 1 1 1 1 0 1 0 1 1 1 1 0 1 1 
1 1 1 1 1 0 1 1 1 0 0 0 0 1 1 0 
1 1 1 1 1 1 1 1 0 1 1 1 1 1 0 1 
1 0 1 0 1 1 1 0 1 1 1 1 1 0 1 1 

output: 
2 3 3 3 3 2 1 10 9 8 8 8 8 7 6 5 
0

Posted: Wed Jul 28, 2004 12:34 am
by StevenTang
My output is:
1 2 3 4 5 6 7 8 9 10 11 12 1 2
14
But I am not sure if it is correct, since I have not get a AC yet.

Posted: Wed Jul 28, 2004 1:33 am
by StevenTang
Now I found that my program get into ArrayIndexOutOfBoundsException stub. Does anybody know the format of the input?

Posted: Wed Jul 28, 2004 9:26 pm
by StevenTang
Use the same idea I got AC in C++....
All times are UTC+02:00
Page 7 of 16

Powered by phpBB® Forum Software © phpBB Limited