LightOJ - 1217 - Neighbor House (II)

A soap company wants to advertise their product in a local area. In this area, there are n houses and the houses are placed in circular fashion, such that house 1 has two neighbors: house 2 and n. House 5 has two neighbors: house 4 and 6. House n has two neighbors, house n-1 and 1.

Now the soap company has an estimation of the number of soaps they can sell on each house. But for their advertising policy, if they sell soaps to a house, they can't sell soaps to its two neighboring houses. No your task is to find the maximum number of estimated soaps they can sell in that area.

Input

Input starts with an integer T (≤ 100), denoting the number of test cases.

Each case starts with a line containing an integer n (2 ≤ n ≤ 1000). The next line contains n space separated integers, where the i^th integer denotes the estimated number of soaps that can be sold to the i^th house. Each of these integers will lie in the range [1, 1000].

Output

For each case, print the case number and the maximum number of estimated soaps that can be sold in that area.

Sample Input	Output for Sample Input
3 2 10 100 3 10 2 11 4 8 9 2 8	Case 1: 100 Case 2: 11 Case 3: 17

Solution:

1. #include <bits/stdc++.h>
2. #define pb push_back
3. using namespace std;
4. typedef long long LL;
5. const int RNG = 1003;
6. const int MOD = 1e9+7;
7. const double pi = 2 * acos( 0.0 );
8.  
9. inline int _Int(){ int x; scanf( "%d", &x ); return x; }
10. inline LL _LLi(){ LL x; scanf( "%lld", &x ); return x; }
11. void pruts(){ puts( "NO" ); exit( EXIT_SUCCESS ); }
12.  
13. int dirX[] = { 1, 0, -1, 0, 1, -1, 1, -1 };
14. int dirY[] = { 0, 1, 0, -1, 1, -1, -1, 1 };
15. int rX[] = { 1, 1, 2, 2, -1, -1, -2, -2 };
16. int rY[] = { 2, -2, 1, -1, 2, -2, 1, -1 };
17.  
18. template < class T > T tri_Area( T x1, T y1, T x2, T y2, T x3, T y3 ){
19.         return abs( x1*( y2-y3 ) - y1*( x2-x3 ) + ( x2*y3-x3*y2 ) );
20. };
21. template < class T > T Distance( T x1, T y1, T x2, T y2 ){
22.         return sqrt( ( x1-x2 ) * ( x1-x2 ) + ( y1-y2 ) * ( y1-y2 ) );
23. };
24. template < class T > T bigMod( T n, T p, T m ){
25.         if( p == 0 )return 1; if( p&1 )return ( n*bigMod( n, p-1, m ) )%m; T x = bigMod( n, p/2, m ); return ( x*x )%m;
26. };
27. int Case = 0;
28. int sset(int N, int pos){return N=N|(1<<pos);}
29. bool check(int N, int pos){return (bool)(N&(1<<pos));}
30. int reset(int N, int pos){return N=N&~(1<<pos);}
31. /**************************************###########################################***************************************
32. ***************************************##    MD. YA-SEEN ARAFAT(MuradTaakla)    ##***************************************
33. ***************************************##    CSE, University of Asia Pacific    ##***************************************
34. ***************************************###########################################***************************************/
35.  
36. int A[ RNG ], n;
37. LL dp[ RNG ][ 2 ];
38.  
39. LL NII( int ind, bool Ok ){
40.         if( Ok && ind == n-1 )return 0;
41.         if( ind >= n )return 0;
42.         LL &R = dp[ ind ][ Ok ];
43.         if( R != -1LL )return R;
44.         R = 0LL;
45.         R = max( NII( ind+1, Ok ), A[ ind ]+NII( ind+2, Ok|( !ind ) ) );
46.         return R;
47. }
48.  
49. void Hunger(){
50.         int t = _Int();
51.         while( t-- ){
52.                 memset( dp, -1LL, sizeof( dp ) );
53.                 n = _Int();
54.                 for( int i = 0; i < n; i++ )A[ i ] = _Int();
55.                 LL ans = NII( 0, 0 );
56.                 printf( "Case %d: %lld\n", ++Case, ans );
57.         }
58. }
59.  
60. int main(){
61.         #ifndef ONLINE_JUDGE
62.         //        freopen("in.txt", "r", stdin);
63.         //        freopen("n.txt", "w", stdout);
64.         #endif
65.         Hunger();
66.         return 0;
67. }

101 Hack 44 - Picking Numbers

Given an array of integers, find and print the maximum number of integers you can select from the array such that the absolute difference between any two of the chosen integers is .

Input Format

The first line contains a single integer, , denoting the size of the array. 
The second line contains  space-separated integers describing the respective values of .

Constraints

• The answer will be .

Output Format

A single integer denoting the maximum number of integers you can choose from the array such that the absolute difference between any two of the chosen integers is .

Sample Input 0

6
4 6 5 3 3 1

Sample Output 0

3

Explanation 0

We choose the following multiset of integers from the array: . Each pair in the multiset has an absolute difference  (i.e.,  and ), so we print the number of chosen integers, , as our answer.

Sample Input 1

6
1 2 2 3 1 2

Sample Output 1

5

Explanation 1

We choose the following multiset of integers from the array: . Each pair in the multiset has an absolute difference  (i.e., , , and ), so we print the number of chosen integers, , as our answer.

Solution:

1. #include <bits/stdc++.h>
2. #define pb push_back
3. using namespace std;
4. typedef long long LL;
5. const int S = 100003;
6. const int MOD = 1e9+7;
7. const double pi = 2 * acos( 0.0 );
8.  
9. inline int _Int(){ int x; scanf( "%d", &x ); return x; }
10. inline LL _LLi(){ LL x; scanf( "%lld", &x ); return x; }
11. void pruts(){ puts( "-1" ); exit( EXIT_SUCCESS ); }
12.  
13. int dirX[] = { 1, 0, -1, 0, 1, -1, 1, -1 };
14. int dirY[] = { 0, 1, 0, -1, 1, -1, -1, 1 };
15. int rX[] = { 1, 1, 2, 2, -1, -1, -2, -2 };
16. int rY[] = { 2, -2, 1, -1, 2, -2, 1, -1 };
17.  
18. template < class T > T tri_Area( T x1, T y1, T x2, T y2, T x3, T y3 ){ return abs( x1*( y2-y3 ) - y1*( x2-x3 ) + ( x2*y3-x3*y2 ) );};
19. template < class T > T Distance( T x1, T y1, T x2, T y2 ){ return sqrt( ( x1-x2 ) * ( x1-x2 ) + ( y1-y2 ) * ( y1-y2 ) ); };
20. template < class T > T bigMod( T n, T p, T m ){ if( p == 0 )return 1; if( p&1 )return ( n*bigMod( n, p-1, m ) )%m; T x = bigMod( n, p/2, m ); return ( x*x )%m; };
21.  
22. int sset(int N, int pos){return N=N|(1<<pos);}
23. bool check(int N, int pos){return (bool)(N&(1<<pos));}
24. int reset(int N, int pos){return N=N&~(1<<pos);}
25. /*******************###########################################********************
26. ********************##   MD. YA-SEEN ARAFAT(ThunderStroke)   ##********************
27. ********************##    CSE, University of Asia Pacific    ##********************
28. ********************###########################################********************/
29.  
30. int frq[ 100+3 ];
31.  
32. void Love(){
33.     int n = _Int();
34.     for( int i = 0; i < n; i++ )frq[ _Int() ]++;
35.     int mx = 0;
36.     for( int i = 1; i < n; i++ )mx = max( mx, frq[ i ]+frq[ i-1 ] );
37.     cout << mx << endl;
38. }
39.  
40. int main(){
41.     #ifndef ONLINE_JUDGE
42. //        freopen("in.txt", "r", stdin);
43. //        freopen("n.txt", "w", stdout);
44.     #endif
45.     Love();
46.     return 0;
47. }