116 - Unidirectional TSP

All about problems in Volume 1. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
SilentStrike
New poster
Posts: 22
Joined: Fri Jan 04, 2002 2:00 am

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

angga888
Experienced poster
Posts: 143
Joined: Sat Dec 21, 2002 11:41 am
Location: Indonesia

Post 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.

SilentStrike
New poster
Posts: 22
Joined: Fri Jan 04, 2002 2:00 am

Nice test case

Post 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.

Rajib
New poster
Posts: 28
Joined: Tue Nov 04, 2003 6:45 am
Location: Bangladesh

Thanks to your input_output

Post 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 .

lord_burgos
New poster
Posts: 43
Joined: Mon Oct 13, 2003 4:54 pm
Location: Mexico
Contact:

116 Error, why?

Post 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?

jackie
New poster
Posts: 47
Joined: Tue May 04, 2004 4:24 am

Be VERY careful for the condition lexicographically smallest

Post 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

oriol78
New poster
Posts: 32
Joined: Mon Mar 31, 2003 7:39 pm

116 output please

Post 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.

Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:

Post by Krzysztof Duleba »

1 1 10 9 8 7 6 5 4 3 2 11 10 9
14

oriol78
New poster
Posts: 32
Joined: Mon Mar 31, 2003 7:39 pm

Post 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.

Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:

Post 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.

omega
New poster
Posts: 5
Joined: Tue Jul 27, 2004 5:37 pm

116 WA? All test input works!!

Post 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

StevenTang
New poster
Posts: 4
Joined: Tue Jul 27, 2004 4:11 am

WA #116

Post 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


StevenTang
New poster
Posts: 4
Joined: Tue Jul 27, 2004 4:11 am

Post 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.

StevenTang
New poster
Posts: 4
Joined: Tue Jul 27, 2004 4:11 am

Post by StevenTang »

Now I found that my program get into ArrayIndexOutOfBoundsException stub. Does anybody know the format of the input?

StevenTang
New poster
Posts: 4
Joined: Tue Jul 27, 2004 4:11 am

Post by StevenTang »

Use the same idea I got AC in C++....

Post Reply

Return to “Volume 1 (100-199)”