Advertisement
Guest User

Ballon Problem

a guest
Apr 20th, 2019
102
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.22 KB | None | 0 0
  1. #include<iostream>
  2. #include<stdio.h>
  3.  
  4. #define size 20
  5. using namespace std;
  6. int N;
  7. int flag[size];
  8. int flag1[size];
  9. int visit[size];
  10. int Ballon[size];
  11. int Arr[size];
  12. int T;
  13. int point;
  14. int Max_Value;
  15. int sum;
  16. int val;
  17.  
  18. void readCase()
  19. {
  20.     int i;
  21.     scanf("%d", &N);
  22.     for(i=0; i<N; i++){
  23.         scanf("%d",&Ballon[i]);
  24.     }
  25.  
  26. }
  27. int left(int x)
  28. {
  29.     int i;
  30.     if(x >= 0){
  31.         //printf("Enter left x is %d\n",x);
  32.         for(i=x; i>=0; i--){
  33.             if(!visit[i]){
  34.                 return Ballon[i];
  35.             }
  36.         }
  37.     }else{
  38.         return 0;
  39.     }
  40.     return 0;
  41. }
  42. int right(int x)
  43. {
  44.     int i;
  45.     if(x<N){
  46.         //printf("Enter right x is %d\n",x);
  47.         for(i=x; i<N; i++){
  48.             if(!visit[i]){
  49.                 //printf("Enter right Again again\n");
  50.                 return Ballon[i];
  51.             }
  52.         }
  53.     }else{
  54.         return 0;
  55.     }
  56.     return 0;
  57. }
  58. int solve(int i)
  59. {
  60.     int l,r;
  61.     visit[i] = 1;
  62.     l = left(i-1);
  63.     //printf("left is %d\n", l);
  64.     r = right(i+1);
  65.     //printf("Right is %d\n",r);
  66.     if(l==0 && r==0){
  67.         sum = sum+0;
  68.     }
  69.     if(l==0 && r>0){
  70.         sum += r;
  71.     }
  72.     if(r==0 && l>0){
  73.         sum += l;
  74.     }
  75.     if(r>0 && l>0){
  76.         sum = sum+(l*r);
  77.     }
  78.     //printf("%d\n",sum);
  79.     return sum;
  80. }
  81.  
  82. void testCase()
  83. {
  84.     int i;
  85.     sum = 0;
  86.     for(i=0; i<N; i++){
  87.         point = Arr[i];
  88.         //printf("point is %d\n",point);
  89.         val = solve(point);
  90.         //printf("Value is %d\n", val);
  91.     }
  92.     //printf("\n");
  93.     for(i=0;i<N;i++){
  94.         visit[i] = 0;
  95.     }
  96.     if(Max_Value<val){
  97.         Max_Value = sum;
  98.     }
  99. }
  100.  
  101. void initCase(int i)
  102. {
  103.     int j;
  104.     for(j=0; j<N; j++){
  105.         visit[i] = 0;
  106.     }
  107.     if(i==N){
  108.         testCase();
  109.         return;
  110.     }
  111.     for(j=0; j<N;j++){
  112.         if(0==flag[j]){
  113.         Arr[i] = j;
  114.         flag[j] = 1;
  115.         initCase(i+1);
  116.         flag[j] = 0;
  117.     }
  118.     }
  119. }
  120.  
  121. int main()
  122. {
  123.     freopen("bal.txt", "r", stdin);
  124.     int i;
  125.     scanf("%d",&T);
  126.     for(i=1;i<=T;i++){
  127.         Max_Value = 0;
  128.         readCase();
  129.         initCase(0);
  130.         printf("Case# %d is %d\n",i, Max_Value);
  131.     }
  132.     return 0;
  133. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement