Fit Squares in Triangle

What is the maximum number of squares of size 2x2 that can be fit in a right angled isosceles triangle of base B.

One side of the square must be parallel to the base of the isosceles triangle.

Base is the shortest side of the triangle

Input

First line contains T, the number of test cases.

Each of the following T lines contains 1 integer B.

Output

Output exactly T lines, each line containing the required answer.

Note:

1 ≤ T ≤ 103

1 ≤ B ≤ 104

Sample Input

11

1

2

3

4

5

6

7

8

9

10

11

Sample Output

0

0

0

1

1

3

3

6

6

10

10

Solution:

#include 

int main()

{

   int t,b,answer;

   scanf("%d",&t);

   while(t--)

   {

                   scanf("%d",&b);

                   answer=0;

                   while(b>=2)

                   {

                                  answer=answer+(b-2)/2;

                                  b-=2;

                   }

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

   }

   return 0;

}

Largest Area

There is 2D array of 1’s and 0’s having the maximum number of rows and columns not more than 100 . Write a program to find the size of the largest area.

Note: The largest area is the set of elements containing 1’s that are adjacent to each other in any of the eight directions and the largest area is linear.

Input

In the first line n is given and in the following lines , each line represents a row of 2D array.

Output

Print each answer on a new line , the answer is the size of the largest area.

Eg:

Input:7

1	0	0	0	1	0	0
0	1	0	0	0	0	0
0	0	0	1	1	1	0
0	1	0	0	0	0	1
1	0	1	0	0	0	0
0	0	1	0	0	1	0
0	0	0	1	0	1	0

Output: 5  

Soln:

#include<stdio.h>

#include<conio.h>

int n;

int AnswerN;

int tempMatrix [n][n];

int matrix[n][n];

int countforindex(int i,int  j, int n);

int main (void)

{

int k,l;

int tempmatrixconsecutiveone = 0;

            int i,j;

            scanf(“%d”,&n);

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

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

            scanf(“%d”,&matrix[i][j]);

            tempmatrixconsecutiveone=0;

            AnswerN=0;

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

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

            {

                        if(matrix[i][j]==1)

                        {

                                    for(k=0;k<n;k++)

                                    for(l=0;l<n;l++)

                                    {

                                                tempMatrix [k][l]= matrix[k][l];

                                    }

                                    tempMatrix[i][j]=0;

                                    tempmatrixconsecutiveone=1;

                                    tempmatrixconsecutiveone = tempmatrixconsecutiveone + countforindex(i,j,n);

                                    AnswerN= AnswerN> tempmatrixconsecutiveone? AnswerN :

tempmatrixconsecutiveone ;

                        }

            }

printf(“%d”, AnswerN);

return 0;

}

int  countforindex(int i,int  j, int n)
{

           int resultZ=0;
  int a_ic,b_ic,c_ic,d_ic,    e_ic,f_ic,g_ic,h_ic;

         int a_jc,b_jc,c_jc,d_jc ,e_jc,f_jc,g_jc,h_jc;

          a_ic=i-1;
          a_jc=j-1;
          b_ic=i-1;
          b_jc=j;
          c_ic=i-1;
          c_jc=j+1;
          d_ic=i;
          d_jc=j-1;
           e_ic=i;
          e_jc=j+1;
          f_ic=i+1;
          f_jc=j-1;
           g_ic=i+1;
           g_jc=j;
          h_ic=i+1;
          h_jc=j+1;

          if(a_ic>-1 && a_ic<n && a_jc>-1 && a_jc<n)

      if(tempMatrix[a_ic][a_jc] == 1)
           {
                        tempMatrix[a_ic][a_jc]=0;    
            resultZ = resultZ +1+ countforindex(a_ic,a_jc,n);

            }

          if(b_ic>-1 && b_ic<n && b_jc>-1 && b_jc<n)

          if(tempMatrix[b_ic][b_jc] == 1)             {
                      tempMatrix[b_ic][b_jc]=0;
                       resultZ = resultZ +1+ countforindex(b_ic,b_jc,n);

            }

            if(c_ic>-1 && c_ic<n && c_jc>-1 && c_jc<n)

        if(tempMatrix[c_ic][c_jc] == 1)

            {
                      tempMatrix[c_ic][c_jc]=0;

                       resultZ = resultZ+1+ countforindex(c_ic,c_jc,n);

           }

            if(d_ic>-1 && d_ic<n && d_jc>-1 && d_jc<n)

      if(tempMatrix[d_ic][d_jc] == 1)

           {

                        tempMatrix[d_ic][d_jc]=0;

                        resultZ = resultZ+1+ countforindex(d_ic,d_jc,n);

         }

          if(e_ic>-1 && e_ic<n && e_jc>-1 && e_jc<n)

        if(tempMatrix[e_ic][e_jc] == 1)

          {
                    tempMatrix[e_ic][e_jc]=0;

                        resultZ = resultZ+1+ countforindex(e_ic,e_jc,n);

            }

            if(f_ic>-1 && f_ic<n && f_jc>-1 && f_jc<n)

          if(tempMatrix[f_ic][f_jc] == 1)

            {

                      tempMatrix[f_ic][f_jc]=0;

                        resultZ = resultZ+1+ countforindex(f_ic,f_jc,n);

            }

            if(g_ic>-1 && g_ic<n && g_jc>-1 && g_jc<n)

       if(tempMatrix[g_ic][g_jc] == 1)

          {

                  tempMatrix[g_ic][g_jc]=0;

                      resultZ = resultZ+1+ countforindex(g_ic,g_jc,n);

            }

           if(h_ic>-1 && h_ic<n && h_jc>-1 && h_jc<n)

        if(tempMatrix[h_ic][h_jc] == 1)

           {

                tempMatrix[h_ic][h_ jc]=0;

                        resultZ = resultZ+1+ countforindex(h_ic,h_jc,n);

           }

           return resultZ;

}

Maximal Crosses

On the matrix A sized n×n, some cells were marked by crosses (X). For each cell (i,j) (with i – the row index, j – the column index), we define B(i,j) as the maximal number of continuous crosses “going across” the cell (i,j) in the same horizontal, vertical or diagonal; B(i,j)=0 if A(i,j) is empty ( '.' ).
[ Empty cells are marked by '.'] .

Clarification:
Continuous crosses going across cell (i,j) in horizontal direction = x1 + x2 - 1
where x1 = highest possible x such that
          j + x - 1<= n and A(i, j ... j + x - 1) are all 'X'
and x2 = highest possible x such that
          j - x + 1 > 0 and A(i, j - x + 1...j) are all 'X'

Similarily we can extend the definition for vertical and diagonal directions.(Note: 0

Task

Given matrix A as input, calculate matrix B.

Input

• The first line contains the integer n.
• Then follow n lines , each containing n characters. The j-th character of the i-th line represents the cell (i,j) of the matrix A, with A(i,j)='X' if it contains a cross, or A(i,j)='.' if it is empty.

Output

Output n lines, each contains n integers, the j-th integer of the i-th line shows the value of B(i,j).
(Each integer on a same line must be separated by exactly one space character)

Example

Input:

10

..X....XX.

XX.X..XX.X

.....XX..X

.XXX..X.X.

.....X..XX

....X....X

X.X....XX.

.X...X.X.X

X.X..X....

..XXXXX.XX

Output:

0 0 2 0 0 0 0 3 3 0

2 2 0 2 0 0 3 3 0 2

0 0 0 0 0 3 3 0 0 2

0 3 3 3 0 0 3 0 2 0

0 0 0 0 0 3 0 0 2 2

0 0 0 0 3 0 0 0 0 3

4 0 3 0 0 0 0 2 3 0

0 4 0 0 0 3 0 3 0 2

3 0 4 0 0 3 0 0 0 0

0 0 5 5 5 5 5 0 2 2

Solution:

#include  

int main()

{

   int n, i, j, x, k, m;

               char a[1001][1001], b[1001];

char s[1001][6]={"0 ","1 ","2 ","3 ","4 ","5 ","6 ","7 ","8 ","9 ","10 ","11 ","12 ","13 ","14 ","15 ","16 ","17 ","18 ","19 ","20 ","21 ","22 ","23 ","24 ","25 ","26 ","27 ","28 ","29 ","30 ","31 ","32 ","33 ","34 ","35 ","36 ","37 ","38 ","39 ","40 ","41 ","42 ","43 ","44 ","45 ","46 ","47 ","48 ","49 ","50 ","51 ","52 ","53 ","54 ","55 ","56 ","57 ","58 ","59 ","60 ","61 ","62 ","63 ","64 ","65 ","66 ","67 ","68 ","69 ","70 ","71 ","72 ","73 ","74 ","75 ","76 ","77 ","78 ","79 ","80 ","81 ","82 ","83 ","84 ","85 ","86 ","87 ","88 ","89 ","90 ","91 ","92 ","93 ","94 ","95 ","96 ","97 ","98 ","99 ","100 ","101 ","102 ","103 ","104 ","105 ","106 ","107 ","108 ","109 ","110 ","111 ","112 ","113 ","114 ","115 ","116 ","117 ","118 ","119 ","120 ","121 ","122 ","123 ","124 ","125 ","126 ","127 ","128 ","129 ","130 ","131 ","132 ","133 ","134 ","135 ","136 ","137 ","138 ","139 ","140 ","141 ","142 ","143 ","144 ","145 ","146 ","147 ","148 ","149 ","150 ","151 ","152 ","153 ","154 ","155 ","156 ","157 ","158 ","159 ","160 ","161 ","162 ","163 ","164 ","165 ","166 ","167 ","168 ","169 ","170 ","171 ","172 ","173 ","174 ","175 ","176 ","177 ","178 ","179 ","180 ","181 ","182 ","183 ","184 ","185 ","186 ","187 ","188 ","189 ","190 ","191 ","192 ","193 ","194 ","195 ","196 ","197 ","198 ","199 ","200 ","201 ","202 ","203 ","204 ","205 ","206 ","207 ","208 ","209 ","210 ","211 ","212 ","213 ","214 ","215 ","216 ","217 ","218 ","219 ","220 ","221 ","222 ","223 ","224 ","225 ","226 ","227 ","228 ","229 ","230 ","231 ","232 ","233 ","234 ","235 ","236 ","237 ","238 ","239 ","240 ","241 ","242 ","243 ","244 ","245 ","246 ","247 ","248 ","249 ","250 ","251 ","252 ","253 ","254 ","255 ","256 ","257 ","258 ","259 ","260 ","261 ","262 ","263 ","264 ","265 ","266 ","267 ","268 ","269 ","270 ","271 ","272 ","273 ","274 ","275 ","276 ","277 ","278 ","279 ","280 ","281 ","282 ","283 ","284 ","285 ","286 ","287 ","288 ","289 ","290 ","291 ","292 ","293 ","294 ","295 ","296 ","297 ","298 ","299 ","300 ","301 ","302 ","303 ","304 ","305 ","306 ","307 ","308 ","309 ","310 ","311 ","312 ","313 ","314 ","315 ","316 ","317 ","318 ","319 ","320 ","321 ","322 ","323 ","324 ","325 ","326 ","327 ","328 ","329 ","330 ","331 ","332 ","333 ","334 ","335 ","336 ","337 ","338 ","339 ","340 ","341 ","342 ","343 ","344 ","345 ","346 ","347 ","348 ","349 ","350 ","351 ","352 ","353 ","354 ","355 ","356 ","357 ","358 ","359 ","360 ","361 ","362 ","363 ","364 ","365 ","366 ","367 ","368 ","369 ","370 ","371 ","372 ","373 ","374 ","375 ","376 ","377 ","378 ","379 ","380 ","381 ","382 ","383 ","384 ","385 ","386 ","387 ","388 ","389 ","390 ","391 ","392 ","393 ","394 ","395 ","396 ","397 ","398 ","399 ","400 ","401 ","402 ","403 ","404 ","405 ","406 ","407 ","408 ","409 ","410 ","411 ","412 ","413 ","414 ","415 ","416 ","417 ","418 ","419 ","420 ","421 ","422 ","423 ","424 ","425 ","426 ","427 ","428 ","429 ","430 ","431 ","432 ","433 ","434 ","435 ","436 ","437 ","438 ","439 ","440 ","441 ","442 ","443 ","444 ","445 ","446 ","447 ","448 ","449 ","450 ","451 ","452 ","453 ","454 ","455 ","456 ","457 ","458 ","459 ","460 ","461 ","462 ","463 ","464 ","465 ","466 ","467 ","468 ","469 ","470 ","471 ","472 ","473 ","474 ","475 ","476 ","477 ","478 ","479 ","480 ","481 ","482 ","483 ","484 ","485 ","486 ","487 ","488 ","489 ","490 ","491 ","492 ","493 ","494 ","495 ","496 ","497 ","498 ","499 ","500 ","501 ","502 ","503 ","504 ","505 ","506 ","507 ","508 ","509 ","510 ","511 ","512 ","513 ","514 ","515 ","516 ","517 ","518 ","519 ","520 ","521 ","522 ","523 ","524 ","525 ","526 ","527 ","528 ","529 ","530 ","531 ","532 ","533 ","534 ","535 ","536 ","537 ","538 ","539 ","540 ","541 ","542 ","543 ","544 ","545 ","546 ","547 ","548 ","549 ","550 ","551 ","552 ","553 ","554 ","555 ","556 ","557 ","558 ","559 ","560 ","561 ","562 ","563 ","564 ","565 ","566 ","567 ","568 ","569 ","570 ","571 ","572 ","573 ","574 ","575 ","576 ","577 ","578 ","579 ","580 ","581 ","582 ","583 ","584 ","585 ","586 ","587 ","588 ","589 ","590 ","591 ","592 ","593 ","594 ","595 ","596 ","597 ","598 ","599 ","600 ","601 ","602 ","603 ","604 ","605 ","606 ","607 ","608 ","609 ","610 ","611 ","612 ","613 ","614 ","615 ","616 ","617 ","618 ","619 ","620 ","621 ","622 ","623 ","624 ","625 ","626 ","627 ","628 ","629 ","630 ","631 ","632 ","633 ","634 ","635 ","636 ","637 ","638 ","639 ","640 ","641 ","642 ","643 ","644 ","645 ","646 ","647 ","648 ","649 ","650 ","651 ","652 ","653 ","654 ","655 ","656 ","657 ","658 ","659 ","660 ","661 ","662 ","663 ","664 ","665 ","666 ","667 ","668 ","669 ","670 ","671 ","672 ","673 ","674 ","675 ","676 ","677 ","678 ","679 ","680 ","681 ","682 ","683 ","684 ","685 ","686 ","687 ","688 ","689 ","690 ","691 ","692 ","693 ","694 ","695 ","696 ","697 ","698 ","699 ","700 ","701 ","702 ","703 ","704 ","705 ","706 ","707 ","708 ","709 ","710 ","711 ","712 ","713 ","714 ","715 ","716 ","717 ","718 ","719 ","720 ","721 ","722 ","723 ","724 ","725 ","726 ","727 ","728 ","729 ","730 ","731 ","732 ","733 ","734 ","735 ","736 ","737 ","738 ","739 ","740 ","741 ","742 ","743 ","744 ","745 ","746 ","747 ","748 ","749 ","750 ","751 ","752 ","753 ","754 ","755 ","756 ","757 ","758 ","759 ","760 ","761 ","762 ","763 ","764 ","765 ","766 ","767 ","768 ","769 ","770 ","771 ","772 ","773 ","774 ","775 ","776 ","777 ","778 ","779 ","780 ","781 ","782 ","783 ","784 ","785 ","786 ","787 ","788 ","789 ","790 ","791 ","792 ","793 ","794 ","795 ","796 ","797 ","798 ","799 ","800 ","801 ","802 ","803 ","804 ","805 ","806 ","807 ","808 ","809 ","810 ","811 ","812 ","813 ","814 ","815 ","816 ","817 ","818 ","819 ","820 ","821 ","822 ","823 ","824 ","825 ","826 ","827 ","828 ","829 ","830 ","831 ","832 ","833 ","834 ","835 ","836 ","837 ","838 ","839 ","840 ","841 ","842 ","843 ","844 ","845 ","846 ","847 ","848 ","849 ","850 ","851 ","852 ","853 ","854 ","855 ","856 ","857 ","858 ","859 ","860 ","861 ","862 ","863 ","864 ","865 ","866 ","867 ","868 ","869 ","870 ","871 ","872 ","873 ","874 ","875 ","876 ","877 ","878 ","879 ","880 ","881 ","882 ","883 ","884 ","885 ","886 ","887 ","888 ","889 ","890 ","891 ","892 ","893 ","894 ","895 ","896 ","897 ","898 ","899 ","900 ","901 ","902 ","903 ","904 ","905 ","906 ","907 ","908 ","909 ","910 ","911 ","912 ","913 ","914 ","915 ","916 ","917 ","918 ","919 ","920 ","921 ","922 ","923 ","924 ","925 ","926 ","927 ","928 ","929 ","930 ","931 ","932 ","933 ","934 ","935 ","936 ","937 ","938 ","939 ","940 ","941 ","942 ","943 ","944 ","945 ","946 ","947 ","948 ","949 ","950 ","951 ","952 ","953 ","954 ","955 ","956 ","957 ","958 ","959 ","960 ","961 ","962 ","963 ","964 ","965 ","966 ","967 ","968 ","969 ","970 ","971 ","972 ","973 ","974 ","975 ","976 ","977 ","978 ","979 ","980 ","981 ","982 ","983 ","984 ","985 ","986 ","987 ","988 ","989 ","990 ","991 ","992 ","993 ","994 ","995 ","996 ","997 ","998 ","999 ","1000 "};

         for(i=!scanf("%d",&n); i

         for(j=!scanf("%s",b); j++

         for(i=0; i

         for(j=0; j

         if(a[i][j]=='.')

         fputs("0 ",stdout);

               else

               {

                              for(k=j-(x=1); k>-1&&a[i][k]!='.'; k--, x++);

                        for(k=j+1; k

                         for(m=x,k=i-(x=1); k>-1&&a[k][j]!='.'; k--, x++);

                               for(k=i+1; k

                               for(m=(m-1&&j-k>-1&&a[i-k][j-k]!='.'; k++, x++);

                               for(k=1; i+k; k++, x++);

                         for(m=(m-1&&j+k'; k++, x++);

                               for(k=1; i+k-1&&a[i+k][j-k]!='.'; k++, x++);

                         m=(m

                         fputs(s[m],stdout);

         } 

return 0;

}

               OR

#include

#include

int main()

{

  int i,j,n,k,l,count=0,old_count=0;

  char **c;

  scanf("%d",&n);

   c=(char **)malloc(n*sizeof(char*));

   i=0;

   while(i

{

   c[i]=(char *)malloc(n*sizeof(char));

   scanf("%s",c[i]);

   i++;

      } 

for(i=0;i

{

   for(j=0;j

   {

                   //printf("%c",c[i][j]);

                   count=0;

                   if(c[i][j]=='x'||c[i][j]=='X')

                   {

                                  k=i;

                                  while(k>=0&&(c[k][j]=='x'||c[k][j]=='X'))

                                              {

                                                             k--;

                                                             count++;

                                              }

                                  k=i;

                                              while(k[j]=='X'))

                                              {

                                                             k++;

                                                             count++;

                                  }

                                              old_count=count;

                                  //printf("a%d",old_count);

                                  count=0;

                                  l=j;

                                  while(l>=0&&(c[i][l]=='x'||c[i][l]=='X'))

                                  {

                                                 l--;

                                                             count++;

                                              }

                                  l=j;

                                              while(l[l]=='X'))

                                  {

                                                             l++;

                                                             count++;

                                              }

                                  if(count>old_count)

                                              old_count=count;

                                  //printf("b%d",old_count);

                                  count=0;

                                  k=i;

                                              l=j;

                                              while(k>=0&&l>=0&&(c[k][l]=='x'||c[k][l]=='X'))

                                  {

                                                 k--;

                                                 l--;

                                                 count++;

                                  }

                                              k=i;

                                  l=j;

                                  while(k|c[k][l]=='X'))

                                  {

                                                             k++;

                                                             l++;

                                                 count++;

                                  }

                                  if(count>old_count)

                                  old_count=count;

                                  //printf("c%d",old_count);

                                  count=0;

                                  k=i;

                                  l=j;

                                  while(k>=0&&l||c[k][l]=='X'))

                                  {

                                                 k--;

                                                 l++;

                                                 count++;

                                  }

                                  k=i;

                                  l=j;

                                  while(l>=0&&k||c[k][l]=='X'))

                                  {

                                                 k++;

                                                 l--;

                                                 count++;

                                  }

                                  if(count>old_count)

                                  old_count=count;

                                  //printf("d%d",old_count);

                                  count=0;

                                  printf("%d",old_count-1);

                   }

                   else

                   printf("0");

                   printf(" ");

   }

   printf("\n");

}

return 0;

}