2014
03-23

Triangles

Mr. Cooper was a celebrated scientist who had a really big lab. There were N sticks in this lab and the length of the i-th stick was i millimeters. One day, when Mr. Cooper decided to do research on triangles, he found that M of the sticks were missed. Mr. Cooper wanted to know how many kinds of triangles could be constructed by three of the remaining sticks. Two triangles are different if and only if they are formed by different sets of sticks.
For Example, there were 8 sticks in the lab originally and the second and the sixth sticks were missed. The 7 different triangles can be constructed were (3,4,5), (3,5,7), (4,5,7), (3,7,8), (4,7,8), (5,7,8), (4,5,8).

The first line contains an integer T (T<=25) indicating the number of test cases. The first line of each test case contains two integers N (1<=N<=1000000000) and M (0<=M<=1000). If M is not zero, there is an additional line containing M distinct integers between 1 and N indicating the missed sticks.

The first line contains an integer T (T<=25) indicating the number of test cases. The first line of each test case contains two integers N (1<=N<=1000000000) and M (0<=M<=1000). If M is not zero, there is an additional line containing M distinct integers between 1 and N indicating the missed sticks.

3
3 0
8 2
2 6
58 3
23 5 3

Case 1: 0
Case 2: 7
Case 3: 13861

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
#include <stack>
#define LL long long
using namespace std;
#define mod 1000000007
#define x first
#define y second
#define pb push_back
#define mp make_pair
#define LL long long
const LL INFL = 1e17;
const int INF = 1e9;

int n;
char g[210][210];
int s[210][210];

int main(){

//  freopen("1.txt","r",stdin);
int cas = 1;
while(scanf("%d",&n)&&n){
getchar();
memset(g,0,sizeof(g));
for(int i = 1; i <= n; i++)
gets(g[i]+1);

memset(s,0,sizeof(s));
for(int i = 1; i <= n; i++){
for(int j = 1; j <= 2*n-1; j++){
//  printf("%c",g[i][j]);
s[i][j] = s[i][j-1]+(g[i][j]=='-'?1:0);
}
// printf("\n");
}

int maxn = 0,tot;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= 2*n-1; j++){
if(g[i][j]=='-'){
// printf("i = %d j = %d\n",i,j);
tot = 1;
if((i+j)%2==0){
int p = j-1,q = j+1;
for(int k = i-1; k > 0; k--){
//  printf("k = %d %d %d %d\n",k,p,q,s[k][q]-s[k][p-1]);
if(p>=1 && q <= 2*n-1 && s[k][q]-s[k][p-1]==q-p+1){
tot += q-p+1;
q++,p--;
}else break;
}
maxn = max(maxn,tot);
}else{
int p = j-1,q = j+1;
for(int k = i+1; k <= n; k++){
if(p>=1 && q <= 2*n-1 && s[k][q]-s[k][p-1]==q-p+1){
tot += q-p+1;
q++,p--;
}else break;
}
maxn = max(maxn,tot);
}
}
}
printf("Triangle #%d\n",cas++);
printf("The largest triangle area is %d.\n\n",maxn);
}
return 0;
}

1. 租的房子，空调不会给你买很好的，都是电器回收买回来的，所以很旧，功耗也大，一晚上3、4度电都有。楼上一周全日开才50块的，是自己买的变频空调吗？

2. 租的房子，空调不会给你买很好的，都是电器回收买回来的，所以很旧，功耗也大，一晚上3、4度电都有。楼上一周全日开才50块的，是自己买的变频空调吗？

3. 租的房子，空调不会给你买很好的，都是电器回收买回来的，所以很旧，功耗也大，一晚上3、4度电都有。楼上一周全日开才50块的，是自己买的变频空调吗？

4. 租的房子，空调不会给你买很好的，都是电器回收买回来的，所以很旧，功耗也大，一晚上3、4度电都有。楼上一周全日开才50块的，是自己买的变频空调吗？

5. 租的房子，空调不会给你买很好的，都是电器回收买回来的，所以很旧，功耗也大，一晚上3、4度电都有。楼上一周全日开才50块的，是自己买的变频空调吗？

6. 租的房子，空调不会给你买很好的，都是电器回收买回来的，所以很旧，功耗也大，一晚上3、4度电都有。楼上一周全日开才50块的，是自己买的变频空调吗？

7. 租的房子，空调不会给你买很好的，都是电器回收买回来的，所以很旧，功耗也大，一晚上3、4度电都有。楼上一周全日开才50块的，是自己买的变频空调吗？

8. 租的房子，空调不会给你买很好的，都是电器回收买回来的，所以很旧，功耗也大，一晚上3、4度电都有。楼上一周全日开才50块的，是自己买的变频空调吗？