Is there a O(1) extra space solution? I tried looking up for patterns but it didn't help. Can we have a function f such that matrix[i][j] = f(i, j, n) for all valid i and j?

...........................

Считаем кол-во клеток ( квадрат + 2 треугольника сверху и снизу )

156 мс, как ускорить программу? сократить формулу? найти более легкую закономерность?

n = int(input())
def tr(size):
    ans = 0
    for i in range(1, size+1):
        ans += i
    return ans
for j in range(n):
    print()
    for i in range(n):
        if i >= j:
            print((n-i-1)*j + tr(j) + tr(n-i-2) + 1 + j + (n-i-1), end = ' ')
        else:
            print(n*n - (i+1)*(n-j) - tr(n-j-1) - tr(i-1) + 1, end = ' ')

#include <iostream>

int main()
{
  int N;
  std:: cin >> N;
  /* dynamic memory allocation */
  int ** p = new int * [N];
  for (int i = 0; i < N; i++)
    p[i] = new int [N];

  /* initialize upper triangle matrix */
  p[0][N-1] = 1;
  int m, n;
  int ct = 1, value = 2, iter = 1, row = 0, column = N - 2;
  while (ct <= N - 1)
  {
    n = column, m = row;
    for (int i = 0; i <= iter; i++)
    {
      p[m++][n++] = value;
      value++;
    }

    iter++; ct++;
    column--;
  }

  /* initialize the lower triangle matrix */
  row = 1; column = 0, iter = N - 2;
  while (ct > 1)
  {
    n = column, m = row;
    for (int i = 0; i <= iter; i++)
    {
      p[m++][n++] = value;
      value++;
    }

    iter--; ct--;
    row++;
  }

  /* display matrix */
  for (int i = 0; i < N; i++)
  {
    for (int j = 0; j < N; j++)
      std::cout << p[i][j] << " ";
    std::cout << std::endl;
  }

  /* release memory */
  for (int i = 0; i < N; i++)
    delete[] p[i];
  delete[] p;

  return 0;
}

Hi. My solution works on my computer but there is not.

What's wrong with my code?

#include <iostream>

using namespace std;

int main()
{
    int n, c = 1;
    int pix[100][100];

    for ( int i = 0; i < n; ++i ) {
        for ( int j = 0; j < n; ++j ) {
            pix[i][j] = 0;
        }
    }

    cin >> n;

    for ( int i = 0; i < n; ++i ) {
        for ( int j = (n - 1); j >= 0; --j ) {
            if ( pix[i][j] > 0 )
                continue;

            int ii =  i, jj = j;

            while ( ii < n && jj < n ) {
                pix[ii][jj] = c;
                ii++;
                jj++;
                c++;
            }
        }
    }

    for ( int i = 0; i < n; ++i ) {
        for ( int j = 0; j < n; ++j ) {
            cout << pix[i][j] << " ";
        }
        cout << endl;
    }

    return 0;
}

Edited by author 10.06.2017 15:16

Edited by author 10.06.2017 15:16

Edited by author 10.06.2017 15:17

divide  the matrex into three divisions >> above the diagonal >>> the diagonal>>under the diagonal
simulate more than matrix for insure your answer

Running in my computer is OK,use use Visual C++ 2010. But in here (use Visual C++ 2013) is wrong answer. I don't understand. Help me, please!

#include <iostream>
using namespace std;

int main(){
        int a[100][100];
        int n, x=0;
        cout<<"\Input n: ";
        cin>>n;
        for(int j=n-1,i=0;j>=0;j--){
            int h=i,k=j;
            while(k<n) a[h++][k++]=++x;
        }
        for(int i=1,j=0;i<n;i++){
            int h=i,k=j;
            while(h<n) a[h++][k++]=++x;
        }
        for(int i=0; i<n ;i++){
            for(int j=0; j<n ;j++){
                cout.width(4);
                cout<<a[i][j];
            }
            cout<<endl;
        }

    cin.ignore(80,'\n');
    cin.get();
    return 0;
}

using System.IO;
using System;

class Program
{
    static void Main()
    {
        int size = Int32.Parse(Console.ReadLine());
        int[,] arr=new int[size,size];
        int count=1;
        for(int x=size;x>=0;x--)
        {
            int y=0;
            int xx=x;
            bool exc=false;
            while(!exc)
            {
                try
                {
                    arr[xx,y]=count;
                    count++;
                    xx++;
                    y++;
                }
                catch
                {
                    exc=true;
                    break;
                }
            }
        }

        for(int y=1;y<=size-1;y++)
        {
            int x=0;
            int yy=y;
            bool exc=false;
            while(!exc)
            {
                try
                {
                    arr[x,yy]=count;
                    count++;
                    x++;
                    yy++;
                }
                catch
                {
                    exc=true;
                    break;
                }
            }
        }

        for(int x=0;x<size;x++)
        {
            for(int y=0;y<size;y++)
            {
                Console.Write(arr[y,x]+" ");
            }
            Console.WriteLine();
        }

    }
}

What is the format of output, blank spaces before number?

hi,i know! there are some solution in this discussion that is a dangerous thing for someone that want to think more... so i say something about this problem for only hint..

for solving this problem this is better to check 2 or 3 example then consider a general case with n as input then try to simulate the answer and in the final step code it.

be successful...

Edited by author 02.11.2013 13:47

var
   i,j,n:word;
   a:array[1..100] of word;
begin
     readln(n);
     a[1]:=1;
     for i:=2 to n do
         a[i]:=a[i-1]+i-1;

     for j:=n downto 1 do
         begin
              for i:=n downto 1 do
                  write(a[i]:3);
              for i:=1 to n-1 do
                  a[i]:=a[i+1]+1;
              a[n]:=a[n]+j;
              writeln;
          end;
end.

num = int(input())

arr = []

for i in range(num):
    arr.append([])
    for j in range(num):
        arr[i].append([])

check = 1

for i in range(num-1,-1,-1):
    x = 0
    y = i
    while y != num:
        arr[x][y] = check
        check += 1
        y += 1
        x += 1

for i in range(1,num,1):
    x = i
    y = 0
    while x != num:
        arr[x][y] = check
        check += 1
        y += 1
        x += 1

string = ''

for i in range(num):
    for j in range(num):
        string += (str(arr[i][j]) + ' ')
    print(string)
    string = ''

Edited by author 31.05.2013 05:43

The same trouble was with problem 1313.

#include <iostream>
#include <iomanip>
//#include <conio.h>

using namespace std;

#define size 105

int main()
{
    //const int size = 105;
    int mas[size][size];

    int xSize;
    cout << "Input array size: ";
    cin >> xSize;

    if ( xSize <= 100 && xSize >=1 )
    {

    //заполняемые элементы
    int ch = 1;

    // правая половина + диагональ; top right corner + main diagonal
    for ( int f = 0; f < xSize; f++ )
    {

        for( int i = 0, j = xSize - 1, d = f; d >= 0; i++, d-- )
        {
            mas[ i ][ j - d ] = ch++;
        }

    }

    // левая половина; left down corner
    for ( int f = 1; f < xSize; f++ )
    {

        for( int i = f, j = 0, d = 0; i < xSize; i++, d++ )
        {
            mas[ i ][ j + d ] = ch++;
        }

    }

    //output array
    for ( int i = 0; i < xSize; i++ )
    {
        for ( int j = 0; j < xSize; j++ )
        {
        cout << setw(4) << mas[i][j];
        }
        cout << endl;

    }

    }
    //_getch();
   return 0;
}

coolface.jpg

program Project2;
var a:array[1..100,1..100] of integer;
    k,p,n,i,j,s:integer;
begin
      readln(n);
      k:=0;
      p:=n-1;
      for s:=1 to (n*2-1) do begin
                                  for i:=1 to n do for j:=1 to n do if j-i=p then begin
                                                                                       k:=k+1;
                                                                                       a[i,j]:=k
                                                                                  end;
                                  p:=p-1
                              end;
      for i:=1 to n do begin
                            for j:=1 to n do begin
                                                  write(a[i,j]);
                                                  write(' ')
                                             end;
                            writeln
                       end;
end.

#include<iostream.h>
int  i,j;
long a[101][101],n;
 int main(){
    cin>>n;
   for(i=1;i<n+1;i++)
 {   a[i][n]=i*(i+1)/2;
  }
   for(i=1;i<n;i++)
 {  for(j=n-1;j>=i;j--)
  {  a[i][j]=a[i][j+1]+n-j+i-1;
   }
 }
   for(i=2;i<n+1;i++)
 {  for(j=i-1;j>0;j--)
  {  a[i][j]=a[i][j+1]+n+j-i;
   }
 }
   for(i=1;i<n+1;i++)
 { for(j=1;j<n+1;j++)
    cout<<a[i][j]<<" ";
    cout<<"\n";
  }
 return 0;
}