Tic-Tac-Toe-Tomek(Qualification Round code jam-2013 )

Problem

Tic-Tac-Toe-Tomek is a game played on a 4 x 4 square board. The board starts empty, except that a single 'T' symbol may appear in one of the 16 squares. There are two players: X and O. They take turns to make moves, with X starting. In each move a player puts her symbol in one of the empty squares. Player X's symbol is 'X', and player O's symbol is 'O'.
After a player's move, if there is a row, column or a diagonal containing 4 of that player's symbols, or containing 3 of her symbols and the 'T' symbol, she wins and the game ends. Otherwise the game continues with the other player's move. If all of the fields are filled with symbols and nobody won, the game ends in a draw. See the sample input for examples of various winning positions.
Given a 4 x 4 board description containing 'X', 'O', 'T' and '.' characters (where '.' represents an empty square), describing the current state of a game, determine the status of the Tic-Tac-Toe-Tomek game going on. The statuses to choose from are:

• "X won" (the game is over, and X won)
• "O won" (the game is over, and O won)
• "Draw" (the game is over, and it ended in a draw)
• "Game has not completed" (the game is not over yet)

If there are empty cells, and the game is not over, you should output "Game has not completed", even if the outcome of the game is inevitable.

Input

The first line of the input gives the number of test cases, T. T test cases follow. Each test case consists of 4 lines with 4 characters each, with each character being 'X', 'O', '.' or 'T' (quotes for clarity only). Each test case is followed by an empty line.

Output

For each test case, output one line containing "Case #x: y", where x is the case number (starting from 1) and y is one of the statuses given above. Make sure to get the statuses exactly right. When you run your code on the sample input, it should create the sample output exactly, including the "Case #1: ", the capital letter "O" rather than the number "0", and so on.

Limits

The game board provided will represent a valid state that was reached through play of the game Tic-Tac-Toe-Tomek as described above.

Small dataset

1 ≤ T ≤ 10.

Large dataset

1 ≤ T ≤ 1000.


Sample

Input	Output
6 XXXT .... OO.. .... XOXT XXOO OXOX XXOO XOX. OX.. .... .... OOXX OXXX OX.T O..O XXXO ..O. .O.. T... OXXX XO.. ..O. ...O	Case #1: X won Case #2: Draw Case #3: Game has not completed Case #4: O won Case #5: O won Case #6: O won

code:

#include <stdio.h>
#include <stdlib.h>
char A[16];
int sta(int a,int b,int c,int d);
 int main()
 {
 char msg[8]="Case #",ch=':',chr,win;
 FILE *fp,*fp1;
 int tc,i,j,k;
 char file[10];
 printf("Enter the input file name : ");
 scanf("%s",file);
 fp=fopen(file,"r");
 fp1=fopen("output2.txt","w");
 fscanf(fp,"%d",&tc);
 for(i=0;i<tc;i++)
 {
   k=0;
   while(k<16)
   {
     fscanf(fp,"%c",&chr);
     if(chr=='.'||chr=='T'||chr=='X'||chr=='O')
     A[k++]=chr;
   }
/*1*/  if(sta(0,1,2,3))
       {
    win=A[0];
    if(win=='T')
    win=A[1];
    fprintf(fp1,"%s%d%c %c %s\n",msg,i+1,ch,win,"won");
    }

/*2*/  else if(sta(4,5,6,7))
       {
       win=A[4];
       if(win=='T')
       win=A[5];
       fprintf(fp1,"%s%d%c %c %s\n",msg,i+1,ch,win,"won");
       }

/*3*/  else if(sta(8,9,10,11))
       {
       win=A[8];
       if(win=='T')
       win=A[9];
       fprintf(fp1,"%s%d%c %c %s\n",msg,i+1,ch,win,"won");
       }

/*4*/  else if(sta(12,13,14,15))
       {
    win=A[12];
       if(win=='T')
       win=A[13];
       fprintf(fp1,"%s%d%c %c %s\n",msg,i+1,ch,win,"won");
       }

/*5*/  else if(sta(0,4,8,12))
      {
       win=A[0];
       if(win=='T')
       win=A[4];
       fprintf(fp1,"%s%d%c %c %s\n",msg,i+1,ch,win,"won");
      }

/*6*/  else if(sta(1,5,9,13))
       {
       win=A[1];
       if(win=='T')
       win=A[5];
       fprintf(fp1,"%s%d%c %c %s\n",msg,i+1,ch,win,"won");
       }

/*7*/  else if(sta(2,6,10,14))
       {
    win=A[2];
    if(win=='T')
    win=A[6];
    fprintf(fp1,"%s%d%c %c %s\n",msg,i+1,ch,win,"won");
       }
/*8*/  else if(sta(3,7,11,15))
       {
    win=A[3];
    if(win=='T')
    win=A[7];
    fprintf(fp1,"%s%d%c %c %s\n",msg,i+1,ch,win,"won");
    }

/*9*/  else if(sta(0,5,10,15))
       {
    win=A[0];
    if(win=='T')
    win=A[5];
    fprintf(fp1,"%s%d%c %c %s\n",msg,i+1,ch,win,"won");
    }

/*10*/ else if(sta(12,9,6,3))
     {
     win=A[12];
     if(win=='T')
     win=A[3];
     fprintf(fp1,"%s%d%c %c %s\n",msg,i+1,ch,win,"won");
     }
     else if((A[0]=='.')||(A[1]=='.')||(A[2]=='.')||(A[3]=='.')||(A[4]=='.')||(A[5]=='.')||(A[6]=='.')||(A[7]=='.')||(A[8]=='.')||(A[9]=='.')||(A[10]=='.')||(A[11]=='.')||(A[12]=='.')||(A[13]=='.')||(A[14]=='.')||(A[15]=='.'))
     {
     fprintf(fp1,"%s%d%c %s\n",msg,i+1,ch,"Game has not completed");
     }
     else
     {
      fprintf(fp1,"%s%d%c %s\n",msg,i+1,ch,"Draw");
     }
 }
 fclose(fp);
 fclose(fp1);
 return(0);
 }


 int sta(int a,int b,int c,int d)
 {
 if(A[a]=='.'||A[b]=='.'||A[c]=='.'||A[d]=='.')
 return(0);

 if(A[a]==A[b]&&A[b]==A[c]&&A[c]==A[d])
 return(1);

 if(A[a]==A[b]&&A[b]==A[c]&&A[d]=='T')
 return(1);

 if(A[a]==A[b]&&A[b]==A[d]&&A[c]=='T')
 return(1);

 if(A[d]==A[b]&&A[b]==A[c]&&A[a]=='T')
 return(1);

 if(A[a]==A[d]&&A[d]==A[c]&&A[b]=='T')
 return(1);

 return(0);
 }

Africa 2010, Qualification Round: Store Credit(CODE JAM)

Problem

You receive a credit C at a local store and would like to buy two items. You first walk through the store and create a list L of all available items. From this list you would like to buy two items that add up to the entire value of the credit. The solution you provide will consist of the two integers indicating the positions of the items in your list (smaller number first).

Input

The first line of input gives the number of cases, N. N test cases follow. For each test case there will be:

• One line containing the value C, the amount of credit you have at the store.
• One line containing the value I, the number of items in the store.
• One line containing a space separated list of I integers. Each integer P indicates the price of an item in the store.
• Each test case will have exactly one solution.

Output

For each test case, output one line containing "Case #x: " followed by the indices of the two items whose price adds up to the store credit. The lower index should be output first.

Limits

5 ≤ C ≤ 1000
1 ≤ P ≤ 1000

Small dataset

N = 10
3 ≤ I ≤ 100

Large dataset

N = 50
3 ≤ I ≤ 2000

Sample

Input	Output
3 100 3 5 75 25 200 7 150 24 79 50 88 345 3 8 8 2 1 9 4 4 56 90 3	Case #1: 2 3 Case #2: 1 4 Case #3: 4 5

 /*http://code.google.com/codejam/contest/351101/dashboard#s=p0*/
/*download input file from above link*/
/*Output is stored in out.txt file*/
CODE:
#include<stdio.h>
int main()
{
int tc,noi[100],cri[100],a[100][100],f=0,i,j,z,l,m;
FILE *fp,*op;
op=fopen("out.txt","w");
char msg[9]="Case #";
char ch=':';
fp=fopen("Alp.in","r");
fscanf(fp,"%d",&tc);
for(i=0;i<tc;i++)
{
fscanf(fp,"%d",&cri[i]);
fscanf(fp,"%d",&noi[i]);
for(j=0;j<noi[i];j++)
fscanf(fp,"%d",&a[i][j]);

}
for(z=0;z<tc;z++)
{
    for(l =0;l<noi[z];l++)
     {
        for(m=l+1;m<noi[z];m++)
        {
            if(a[z][l]+a[z][m]==cri[z])
             {
             fprintf(op,"%s%d%c%d  %d\n",msg,z+1,ch,l+1,m+1);
               f=1;
               break;
             }
        }
         if(f)
        {
         f=0;break;
         }
     }
}
return(0);
}

Not a Triangle

Problem Statement: 

You have N  wooden sticks, which are labeled from 1 to N. The i-th stick has a length of L_i . Your friend has challenged you to a simple game: you will pick three sticks at random, and if your friend can form a triangle with them (degenerate triangles included), he wins; otherwise, you win. You are not sure if your friend is trying to trick you, so you would like to determine your chances of winning by computing the number of ways you could choose three sticks (regardless of order) such that it is impossible to form a triangle with them.

Input:

The input file consists of multiple test cases. Each test case starts with the single integer N, followed by a line with the integers L₁, ..., L_N. The input is terminated with N = 0, which should not be processed.

Output:

For each test case, output a single line containing the number of triples.

Example:

Input:
3
4 2 10
3
1 2 3
4
5 2 9 6
0

Output:
1
0
2

For the first test case, 4 + 2 < 10, so you will win with the one available triple. For the second case, 1 + 2 is equal to 3; since degenerate triangles are allowed, the answer is 0.


 Solution:
#include<iostream>
using namespace std;
void noways(unsigned int *a,unsigned int l);
int main()
{
unsigned int p[10][10],len[10],k=0,i;
cout<<"Enter the inputs:\n";
while(1)
{
cin>>len[k];
if(len[k]==0)
break;
for(i=0;i<len[k];i++)
cin>>p[k][i];
k++;
}
for(i=0;i<k;i++)
noways(*(p+i),len[i]);
return(0);
}


void noways(unsigned int * a,unsigned int l)
{
unsigned int i,j,k,n=0;
for(i=0;i<l;i++)
for(j=0;(j<l)&&(j!=i);j++)
for(k=0;(k<l)&&(k!=j)&&(k!=i);k++)
{
if(*(a+i) + *(a+j) < *(a+k))
n++;
if(*(a+k) + *(a+j) < *(a+i))
n++;
if(*(a+i) + *(a+k) < *(a+j))
n++;
}
cout<<"All possible ways:"<<n<<endl;
}

2 Player Tic Tac Toe game! (C-language)

#include <stdio.h>
#include <stdlib.h>
#include<string.h>

char A[9]={' ' ,' ',' ',' ',' ',' ',' ',' ',' ',};
 void draw();
int main()
{
    int i,j,n,p=0;
    int status=1;
    char a[20],b[20];
    clrscr();
    printf("First player name:");
    scanf("%s",a);
    strupr(a);
    printf("Second player name:");
    scanf("%s",b);
    strupr(b);
    clrscr();
    printf("The numbers below represent the point no.\n\n");
    printf("1 | 2 | 3\n_________\n4 | 5 | 6\n_________\n7 | 8 | 9");


    for(i=0;i<9;i++)
    {
    char s;
    if(status==1)
    printf("\n\n%s\t",a);
    else
    printf("\n\n%s\t",b);
    printf("Enter the point:\n");
    scanf("%d",&n);
    n=n-1;
    if((A[n]!='X'&&A[n]!='O')&&n<9)
    {
        if(status==1)
        {
        A[n]='X';
        status=0;
        s='X';
        }
        else
        {
        A[n]='O';
        status=1;
        s='O';
        }
    }
    else
    {
        i--;
        if(n<9)
        {
        printf("\nCan't replace the previous entry\n");
        }
        else
        {
        printf("\nEnter number between 1-9\n");
        }
    }


    if(A[0]==s &&(A[4]==s &&A[8]==s))
    {
       p=1;
       break;
    }
       else if(A[2]==s &&(A[4]==s &&A[6]==s)){
       p=1;break;
       }
       else if(A[0]==s &&(A[3]==s &&A[6]==s)){
       p=1;break;

       }
       else if(A[1]==s &&(A[4]==s &&A[7]==s)){
       p=1;break;
       }
       else if(A[2]==s &&(A[5]==s &&A[8]==s)){
       p=1;break;
       }
       else if(A[0]==s &&(A[1]==s &&A[2]==s)){
       p=1;break;
       }
       else if(A[3]==s &&A[4]==s &&A[5]==s){
       p=1;break;
       }
       else if(A[6]==s &&A[7]==s &&A[8]==s){
       p=1;break;
       }
       else
       draw();
    }
    if(p==1)
    {
    if(A[n]=='x')
    printf("\n\t\tThe winner is %s \n\n",b);
    else
    printf("\n\t\tThe winner is %s \n\n",a);
    draw();
    getch();

    }
    else
    printf("\n\t\t\Draw Match\n\n");

    getch();
    return 0;
}
void draw()
{
    printf("\t\t%c | %c | %c \t\t1 | 2 | 3 \n\t\t_________\n\t\t%c | %c | %c \t\t4 | 5 | 6 \n\t\t_________\n\t\t%c | %c | %c \t\t7 | 8 | 9 \n",A[0],A[1],A[2],A[3],A[4],A[5],A[6],A[7],A[8]);
}


  

Permutation of string (without repetition)

#include<stdio.h>

#include<conio.h>

void swap (char *x,char *y);

void permit(char *a,int i,int n);

int k=0;

main()

{

char a[]="ABCDE";

clrscr();

permit(a,0,4);

printf("\n%d",k);

getch();

return(0);

}

void swap (char *x,char *y)

{

char temp;

temp=*x;

*x=*y;

*y=temp;

}

void permit (char *a,int i,int n)

{

int j;

if(i==n)          {

printf("%s\t",a);    k++;}

else

{

for(j=i;j<=n;j++)

{

swap((a+i),(a+j));

permit(a,i+1,n);

swap((a+i),(a+j));

}

}

}

                         Download C program