Slow but Steady: 8월 2013

2013년 8월 11일 일요일

ClockSync

Initial think

#include <stdio.h>

int c;
int clkTime[16];
int clkOfSW[10][5] = {
{0,1,2,-1,-1},//0
{3,7,9,11,-1},
{4,10,14,15,-1},
{0,4,5,6,7},
{6,7,8,10,12},
{0,2,14,15,-1},//5
{3,14,15,-1,-1},
{4,5,7,14,15},
{1,2,3,4,5},
{3,4,5,9,13}//9
};
int swSize2[10] = {3,4,4,5,5,4,3,5,5,5};

int swOfClk[16][4] = {
{0,3,5,-1},
{0,8,-1,-1},
{0,5,8,-1},
{1,6,8,9},
{2,3,5,8},
{3,7,8,9},//5
{3,4,-1,-1},
{1,3,4,7},
{4,-1,-1,-1},
{1,9,-1,-1},
{2,4,-1,-1},//10
{1,-1,-1,-1},
{4,-1,-1,-1},
{9,-1,-1,-1},
{2,5,6,7},
{2,5,6,7}//15
};
int swSize[16]= {3,2,3,4,4,4,2,4,1,2,2,1,1,1,4,4};
int curMin,cnt;
void sub();

FILE* fin;
FILE* fout;
int press[20000];
int pressCnt;

void main()
{
fin = fopen("in.txt","r");
fout = fopen("out.txt","w");

//scanf("%d", &c);
fscanf(fin,"%d",&c);
for (int i=0; i<c; i++)
{
for (int j=0; j<16; j++)
//scanf("%d",&(clkTime[j]));
fscanf(fin,"%d",&(clkTime[j]));

curMin = 65535;
cnt= 0;
pressCnt=0;
sub();
//printf("%d\n",curMin);
fprintf(fout,"%d\n",curMin);
}

fclose(fin);
fclose(fout);
}

void sub()
{
int clk = 0;
while (clk<15)
{
if (clkTime[clk] != 12) {
break;
}
clk++;
}

if (clk == 15)
{
if(curMin > cnt)
{
curMin = cnt;
fprintf(fout,"clk=15. cnrMin=%d\n\n",curMin);
}
return;
}

for(int sw=0; sw<swSize[clk]; sw++)
{
for (int cc=0; cc<swSize2[sw]; cc++)
{
clkTime[clkOfSW[sw][cc]] += 3;
if(clkTime[clkOfSW[sw][cc]] > 12) clkTime[clkOfSW[sw][cc]] -= 12;
}
cnt++;
press[pressCnt++] = sw;
fprintf(fout, "%d press. cnt=%d\n", sw, cnt);
for(int jj=0; jj<pressCnt; jj++) fprintf(fout,"%d ", press[jj]); fprintf(fout,"\ntime: ");
for(int jj=0; jj<16; jj++) fprintf(fout,"%d ", clkTime[jj]); fprintf(fout,"\n");

sub();

for (int cc=0; cc<swSize2[sw]; cc++)
{
clkTime[clkOfSW[sw][cc]] -= 3;
if(clkTime[clkOfSW[sw][cc]] == 0) clkTime[clkOfSW[sw][cc]] = 12;
}
cnt--;
pressCnt--;
fprintf(fout, "%d unpress. cnt=%d\n", sw, cnt);
for(int jj=0; jj<pressCnt; jj++) fprintf(fout,"%d ", press[jj]); fprintf(fout,"\ntime: ");
for(int jj=0; jj<16; jj++) fprintf(fout,"%d ", clkTime[jj]); fprintf(fout,"\n");
}
}

2013년 8월 10일 토요일

BoardCover



Correct answer


#include <stdio.h>
#include <assert.h>

int testNum, row, col;
int Board[20][20];
int whiteCnt;
int ans;
void sub();


FILE *fin, *fout;
void printBoard(FILE *fp)
{    
    for (int r=0; r<row; r++)
    {        
        for(int c=0; c<col; c++)
            fprintf(fp, "%d ", Board[r][c]);
        fprintf(fp, "\n");
    }
}

int main()
{
    //fin = fopen("in.txt", "r");
    //fout = fopen("out.txt", "w");
    //fscanf(fin, "%d",&testNum);
    scanf("%d",&testNum);
    for (int ii=0; ii<testNum; ii++)
    {
        for (int r=0; r<row; r++)
            for (int c=0; c<col; c++)
                Board[r][c] = -1;
        whiteCnt = 0;
        ans = 0;
        //fscanf(fin, "%d%d",&row,&col);
        scanf("%d%d",&row,&col);
        char newline;
        //fscanf(fin, "%c", &newline);
        scanf("%c", &newline);
        for (int r=0; r<row; r++)
        {
            char buffer[20] = {0, };
            fgets(buffer, 20, stdin);
            for (int c=0; c<col; c++)
            {
                if(buffer[c]=='#')
                    Board[r][c] = 0;
                else if(buffer[c]=='.')
                {
                    Board[r][c] = 1;
                    whiteCnt++;
                }
                else assert(0);
            }
        }
        // do my work
        //printBoard(fout);
        sub();
        //fprintf(fout, "\nans = %d\n", ans);
        printf("%d\n", ans);
    }
    //fclose(fin);
    //fclose(fout);
    return 0;
}

void sub()
{
    //fprintf(fout, "--------------------\n");
    //fprintf(fout, "row=%d, col=%d, whiteCnt=%d, sR=%d, sC=%d\n", row, col, whiteCnt, sR, sC);
    //printf("row=%d, col=%d, whiteCnt=%d, sR=%d, sC=%d\n", row, col, whiteCnt, sR, sC);
    //printBoard(fout);
    if (whiteCnt == 0)
    {
        ans++;
        //fprintf(fout, "ok! return. ans=%d\n", ans);
        //printf("ok! return.\n");
        return;
    }
    if (whiteCnt < 3)
    {
        //fprintf(fout, "no room. stop here. whiteCnt=%d\n", whiteCnt);
        //printf("no room. stop here. whiteCnt=%d\n", whiteCnt);
        return;
    }
    if (whiteCnt % 3 != 0)
    {
        //fprintf(fout, "not multiple of 3. stop here. whiteCnt=%d\n", whiteCnt);
        //printf("not multiple of 3. stop here. stop here. whiteCnt=%d\n", whiteCnt);
        return;
    }
    bool find=false;
    int r=0, c=0;
    for (r=0; r<row; r++)
    {
        for (c=0; c<col; c++)
        {
            if (Board[r][c]==1)
            {
                find=true;
                break;
            }
        }
        if(find==true)  break;
    }

    if (find == false)
    {
        //printf("no white.\n");
        ans++;
        return;
    }

    //fprintf(fout, "(%d %d) ", r, c);
    // shape1
    // 1 1
    // x 1
    if (r+1<row && c+1<col && Board[r][c]==1 && Board[r][c+1]==1 && Board[r+1][c+1]==1)
    {
        //fprintf(fout, "%d row, %d col, shape 1 matched\n", r, c);
        Board[r][c]=2; Board[r][c+1]=2; Board[r+1][c+1]=2;
        whiteCnt-=3;
        sub();
        //fprintf(fout, "%d row, %d col : shape 1 roleback\n", r,c );
        whiteCnt+=3;
        Board[r][c]=1; Board[r][c+1]=1; Board[r+1][c+1]=1;
        //printBoard(fout); 
    }
    // shape2
    // x 1
    // 1 1
    if (r+1<row && c-1>=0 && Board[r][c]==1 && Board[r+1][c]==1 && Board[r+1][c-1]==1)
    {
        //fprintf(fout, "%d row, %d col, shape 2 matched\n", r, c);
        Board[r][c]=2; Board[r+1][c]=2; Board[r+1][c-1]=2;
        whiteCnt-=3;
        sub();
        //fprintf(fout, "%d row, %d col : shape 2 roleback\n", r, c);
        whiteCnt+=3;
        Board[r][c]=1; Board[r+1][c]=1; Board[r+1][c-1]=1;
    }
    // shape3
    // 1 x
    // 1 1
    if (r+1<row && c+1<col && Board[r][c]==1 && Board[r+1][c]==1 && Board[r+1][c+1]==1)
    {
        //fprintf(fout, "%d row, %d col, shape 3 matched\n", r, c);
        Board[r][c]=2; Board[r+1][c]=2; Board[r+1][c+1]=2;
        whiteCnt-=3;
        sub();
        //fprintf(fout, "%d row, %d col : shape 3 roleback\n", r, c);
        whiteCnt+=3;
        Board[r][c]=1; Board[r+1][c]=1; Board[r+1][c+1]=1;
        //printBoard(fout);
    }
    // shape4
    // 1 1
    // 1 x
    if (r+1<row && c+1<col && Board[r][c]==1 && Board[r][c+1]==1 && Board[r+1][c]==1)
    {
        //fprintf(fout, "%d row, %d col, shape 4 matched\n", r, c);
        Board[r][c]=2; Board[r][c+1]=2; Board[r+1][c]=2;
        whiteCnt-=3;
        sub();
        //fprintf(fout, "%d row, %d col : shape 4 roleback\n", r, c);
        whiteCnt+=3; 
        Board[r][c]=1; Board[r][c+1]=1; Board[r+1][c]=1; 
        //printBoard(fout);
    }
    //fprintf(fout, "no. return\n");
}

BoardCover

Timeout Answer

#include <stdio.h>
#include <assert.h>

int testNum, row, col;
int Board[20][20];
int whiteCnt;
int ans;

FILE *fin, *fout;

void sub(int sR, int sC, int prevShape);

void printBoard(FILE *fp)
{
    for (int r=0; r<row; r++)
    {
        for(int c=0; c<col; c++)
            fprintf(fp, "%d ", Board[r][c]);
        fprintf(fp, "\n");
    }
}

int main()
{
    //fin = fopen("in.txt", "r");
    //fout = fopen("out.txt", "w");

    //fscanf(fin, "%d",&testNum);
    scanf("%d",&testNum);
    for (int ii=0; ii<testNum; ii++)
    {
        for (int r=0; r<row; r++)
            for (int c=0; c<col; c++)
                Board[r][c] = -1;
        whiteCnt = 0;
        ans = 0;

        //fscanf(fin, "%d%d",&row,&col);
        scanf("%d%d",&row,&col);
        char newline;
        //fscanf(fin, "%c", &newline);
        scanf("%c", &newline);

        for (int r=0; r<row; r++)
        {
            char buffer[20] = {0, };
            fgets(buffer, 20, stdin);

            for (int c=0; c<col; c++)
            {
                if(buffer[c]=='#')  Board[r][c] = 0;
                else if(buffer[c]=='.') { Board[r][c] = 1; whiteCnt++; }
                else assert(0);
            }
        }

        // do my work
        //printBoard(fout);
        sub(0, 0, 0);
        //fprintf(fout, "\nans = %d\n", ans);
        printf("ans=%d\n", ans);
    }

    //fclose(fin);
    //fclose(fout);
    return 0;
}

void sub(int sR, int sC, int prevShape)
{
    //fprintf(fout, "--------------------\n");
    //fprintf(fout, "row=%d, col=%d, whiteCnt=%d, sR=%d, sC=%d\n", row, col, whiteCnt, sR, sC);
    //printf("row=%d, col=%d, whiteCnt=%d, sR=%d, sC=%d\n", row, col, whiteCnt, sR, sC);
    //printBoard(fout);

    if (whiteCnt == 0)
    {
        ans++;
        //fprintf(fout, "ok! return. ans=%d\n", ans);
        //printf("ok! return.\n");
        return;
    }

    if (whiteCnt < 3)
    {
        //fprintf(fout, "no room. stop here. whiteCnt=%d\n", whiteCnt);
        //printf("no room. stop here. whiteCnt=%d\n", whiteCnt);
        return;
    }

    if (whiteCnt % 3 != 0)
    {
        //fprintf(fout, "not multiple of 3. stop here. whiteCnt=%d\n", whiteCnt);
        //printf("not multiple of 3. stop here. stop here. whiteCnt=%d\n", whiteCnt);
        return;
    }

    for (int r=sR; r<row-1; r=r+1)
    {
        int c = (r==sR)? sC: 0;
        while (c < col-1)
        {
            //fprintf(fout, "(%d %d) ", r, c);
            // shape1
            // 1 1
            // x 1
            if (r+1<row && c+1<col && Board[r][c]==1 && Board[r][c+1]==1 && Board[r+1][c+1]==1) {
                //fprintf(fout, "%d row, %d col, shape 1 matched\n", r, c);
                Board[r][c]=2; Board[r][c+1]=2; Board[r+1][c+1]=2;
                whiteCnt-=3;
                if (c <= col-4)
                    sub(r, c+2, 1);
                else
                    sub(r+1, 0, 1);
                //fprintf(fout, "%d row, %d col : shape 1 roleback\n", r,c );
                whiteCnt+=3;
                Board[r][c]=1; Board[r][c+1]=1; Board[r+1][c+1]=1;
                //printBoard(fout);
            }

            // shape2
            // x 1
            // 1 1
            if (prevShape != 3 && r+1<row && c+1<col && Board[r][c+1]==1 && Board[r+1][c]==1 && Board[r+1][c-1]==1) {
                //fprintf(fout, "%d row, %d col, shape 2 matched\n", r, c);
                Board[r][c]=2; Board[r+1][c]=2; Board[r+1][c-1]=2;
                whiteCnt-=3;
                if (c <= col-4)
                    sub(r, c+2, 2);
                else
                    sub(r+1, c, 2);
                //fprintf(fout, "%d row, %d col : shape 2 roleback\n", r, c);
                whiteCnt+=3;
                Board[r][c]=1; Board[r+1][c]=1; Board[r+1][c-1]=1;
            }
            // shape3
            // 1 x
            // 1 1
            if (prevShape != 3 && r+1<row && c+1<col && Board[r][c]==1 && Board[r+1][c]==1 && Board[r+1][c+1]==1) {
                //fprintf(fout, "%d row, %d col, shape 3 matched\n", r, c);
                Board[r][c]=2; Board[r+1][c]=2; Board[r+1][c+1]=2;
                whiteCnt-=3;
                sub(r, c+1, 3);
                //fprintf(fout, "%d row, %d col : shape 3 roleback\n", r, c);
                whiteCnt+=3;
                Board[r][c]=1; Board[r+1][c]=1; Board[r+1][c+1]=1;
                //printBoard(fout);
            }
            // shape4
            // 1 1
            // 1 x
            if (prevShape != 3 && r+1<row && c+1<col && Board[r][c]==1 && Board[r][c+1]==1 && Board[r+1][c]==1) {
                //fprintf(fout, "%d row, %d col, shape 4 matched\n", r, c);
                Board[r][c]=2; Board[r][c+1]=2; Board[r+1][c]=2;
                whiteCnt-=3;
                if (c <= col-4)
                    sub(r, c+2, 4);
                else
                    sub(r+1, c, 4);
                //fprintf(fout, "%d row, %d col : shape 4 roleback\n", r, c);
                whiteCnt+=3;
                Board[r][c]=1; Board[r][c+1]=1; Board[r+1][c]=1;
                //printBoard(fout);
            }
            c = c + 1;
        }
    }

    //fprintf(fout, "no. return\n");
}

Picnic

Correct answer

#include <stdio.h>
#include <vector>

using namespace std;
void sub(vector<int> v, int N, int start);

int c, n, m;
int in[50][2];
int ans;

int relation[10][10];

int main ()
{
    int i,j;
    int tmp;

    // C = number of test case
    scanf("%d", &c);
    //printf("%d\n", c);

    for (i=0; i<c; i++) {
  for (int x=0; x<10; x++)
  for (int y=0; y<10; y++)
  relation[x][y] = 0;

        // n = number of student
        // m = number of pair
        scanf("%d %d", &n, &m);
        //printf("n = %d, m = %d\n", n,m);
        for (j=0; j<m; j++) {
            // in = array of pair
            scanf("%d %d", &in[j][0], &in[j][1]);

            if (in[j][0] > in[j][1])    {
                tmp = in[j][1];
                in[j][1] = in[j][0];
                in[j][0] = tmp;
            }
            
            // in[][0] < in[][1] is always TRUE
            //printf("(%d, %d) ", in[j][0], in[j][1]);
            relation[in[j][0]][in[j][1]] = 1;
        }

  vector<int> v;
  ans = 0;
  sub(v, n, 0);
        //printf("\n");

  printf("%d", ans);

  if (i < c-1) printf("\n");
    }
}

void sub(vector<int> v, int N, int start)
{
 if (v.size() == N)
 {
  ans++;
  return;
 }

 for(int from=start; from<N; from++)
 {
  for(int to=from+1; to<N; to++)
  {
   if( relation[from][to]==1 )
   {
    // check if vector has from or to
    bool bDup = false;
    for (int ii=0; ii<v.size(); ii++) {
     if(v.at(ii)==from || v.at(ii)==to) {
      bDup = true;
      break;
     }
    }

    if (bDup == false)
    {
     v.push_back(from);
     v.push_back(to);
     sub(v, N, from+1);
     v.pop_back();
     v.pop_back();
    }
   }
  }
 }
}

Posts List

2013년 8월 11일 일요일

ClockSync

2013년 8월 10일 토요일

BoardCover

BoardCover

Picnic