Thursday, December 27, 2012

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;
}
Posted by at No comments:

Monday, October 22, 2012

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;
}



Posted by at No comments:

Friday, July 6, 2012

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;
}
Posted by at No comments:
Subscribe to: Posts (Atom)