fork download
copy 
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #define INFINITY 99999
  4.  
  5. int min[1000] = {0, };
  6.  
  7. int count( int arr[], int m, int value )
  8. {
  9.     int i,j;
  10.  
  11.     for(i=0; i<=value; i++)
  12.         min[i] = INFINITY;
  13.  
  14.     min[0] = 0;
  15.  
  16.     for(i=0; i < m; i++)
  17.         min[arr[i]] = 1;
  18.  
  19.     for(i=0; i<=value; i++)
  20.     {
  21.         for(j=0; j < m; j++)
  22.         {
  23.             int index = i-arr[j];
  24.             if(index < 0)
  25.                 continue;
  26.  
  27.             if(min[index]+1 < min[i])
  28.                 min[i] = min[index]+1;
  29.         }
  30.     }
  31.  
  32.     return min[value];
  33. }
  34.  
  35. int main()
  36. {
  37.     int test,n,i,j,sum = 0;
  38.     int *arr,*val;
  39.  
  40.     scanf("%d",&test);
  41.  
  42.     for(i = 0; i<test ; i++)
  43.     {
  44.         sum = 0;
  45.         scanf("%d",&n);
  46.         arr = (int *)malloc(sizeof(int)*n);
  47.         val = (int *)malloc(sizeof(int)*n);
  48.         for(j = 0; j<n ; j++)
  49.             scanf("%d",arr+j);
  50.         for(j = 0; j<n ; j++)
  51.             scanf("%d",val+j);
  52.         for(j = 0; j<n ; j++)
  53.             sum += count(val, n, 2*arr[j]);
  54.  
  55.         printf("%d\n",sum);
  56.     }
  57.  
  58.     return 0;
  59. }
Success #stdin #stdout 0.02s 1812KB
comments (?)
stdin
copy 
1
4
1 2 3 4
1 4 2 3
stdout
copy 
6
https://ideone.com/km9749
language:
C (gcc 8.3)
created:
11 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!