코난도일의 자유로이~!

문제 링크 : http://algospot.cafe24.com/zbxe/?mid=aoj&action=problem&no=132




제출한 답안 :


#include <iostream>
#include <stdlib.h>

using namespace std;

class Mat
{
public:

 long long **matrix;
 long long size;

 Mat();
 Mat(long long n);
 Mat(const Mat& mat);
 ~Mat();

 Mat operator*(const Mat& mat);
 void operator=(const Mat& mat);

};

Mat::Mat()
{
}

Mat::Mat(long long n)
{
 size = n;

 matrix = new long long*[n];

 for(long long j = 0; j < n; j++)
 {
  matrix[j] = new long long[n];
 }
}

Mat::Mat(const Mat& mat)
{
 long long i, j;

 size = mat.size;

 matrix = new long long*[size];

 for(i = 0; i < size; i++)
 {
  matrix[i] = new long long[size];
 }

 for(i = 0; i < size; i++)
 {
  for(j = 0; j < size; j++)
  {
   matrix[i][j] = mat.matrix[i][j];
  }
 }
}

Mat::~Mat()
{
  for(long long i = 0; i < size; i++)
  {
   delete [] matrix[i];
  }

  delete [] matrix;
}

Mat Mat::operator*(const Mat& mat)
{
 long long i, j, k;

 Mat c(size);

 for(i = 0; i < size; i++)
 {
  for(j = 0; j < size; j++)
  {
   c.matrix[i][j] = 0;
   
   for(k = 0; k < size; k++)
    c.matrix[i][j] += matrix[i][k] * mat.matrix[k][j];

   c.matrix[i][j] %= 10007;
  }
 }

 return c;

}

void Mat::operator=(const Mat& mat)
{
 long long i, j;

 size = mat.size;

 matrix = new long long*[size];

 for(i = 0; i < size; i++)
 {
  matrix[i] = new long long[size];
 }

 for(i = 0; i < size; i++)
 {
  for(j = 0; j < size; j++)
  {
   matrix[i][j] = mat.matrix[i][j];
  }
 }
}

Mat matrix_pow(Mat a, long long p)
{
 long long i, j;

 if(p == 0)
 {
  Mat E(a.size);

  for(i = 0; i < a.size; i++)
  {
   for(j = 0; j < a.size; j++)
   {
    E.matrix[i][j] = 0;

    if(i == j)
     E.matrix[i][j] = 1;
   }   
  }

  return E;
 }
 else if(p % 2 == 1)
 {
  return a * matrix_pow(a, p - 1);

 }
 else
 {
  Mat b = matrix_pow(a, p / 2);

  return b*b;
 }
}

int main(void)
{
 
 int ncase, n, i = 0, j, k;
 long long p;

 Mat* M;
 Mat* result;

 cin >> ncase;

 while(i < ncase)
 {
  cin >> n;
  cin >> p;

  M = new Mat(n);
  result = new Mat(n);

  for(j = 0; j < n; j++)
  {
   for(k = 0; k < n; k++)
    cin >> M->matrix[j][k];
  }

  *result = matrix_pow(*M, p);

  for(j = 0; j < n; j++)
  {
   for(k = 0; k < n; k++)
    cout << result->matrix[j][k] % 10007 << " ";

   cout << "\n";
  }
 
 
  delete M;
  delete result;

  i++;
 }

 return 0;
}


변수 타입 long long으로 지정하는걸 몰라서 한참 고생했다.ㅡㅜ

문제 링크 : http://algospot.cafe24.com/zbxe/?mid=aoj&action=problem&no=100

제출한 답안 :

#include <iostream>
#include <fstream>
#include <stdlib.h>

using namespace std;

#define SWAP(a,b) { int t;t=a;a=b;b=t; }

void QuickSort(int *ar, int num)
{
     int left,right;

     int key;

     if (num <= 1) return;

     key=ar[num-1];

     for (left=0,right=num-2;;left++,right--) {

          while (ar[left] < key) { left++; }

          while (ar[right] > key) { right--; }

          if (left >= right) break;

          SWAP(ar[left],ar[right]);

     }

     SWAP(ar[left],ar[num-1]);

     QuickSort(ar,left);                           // 왼쪽 구간 정렬

     QuickSort(ar+left+1,num-left-1);        // 오른쪽 구간 정렬

}

int main(void)
{
 
 int ncase, num, result = 0, i = 0, j;
 int *m, *w;

 cin >> ncase;

 while(i < ncase)
 {
  cin >> num;

  m = new int[num];
  w = new int[num];

  for(j = 0; j < num; j++)
   cin >> m[j];

  for(j = 0; j < num; j++)
   cin >> w[j];

  QuickSort(m, num);
  QuickSort(w, num);
  
  for(j = 0; j < num; j++)
   result += abs(m[j] - w[j]);

  cout << result << endl;

  result = 0;

  delete [] m;
  delete [] w;

  i++;
 }
 

 return 0;
}