/home/toolbox/public_html/solutions/126/12621/a.c
1 #include <stdio.h>
2 #include <string.h>
3 #include <sys/types.h>
4 #include <sys/stat.h>
5 #include <fcntl.h>
6 #include <stdlib.h>
7 #include <math.h>
8 #include <stdint.h>
9
10 #define TRUE (1 == 1)
11 #define FALSE (1 != 1)
12
13 #define DEBUG if (FALSE)
14
15 /* fprintf(stderr, "functionName: message", varslist); */
16
17 /*
18 * Author: Isaac Traxler
19 * Date: 2015-10-05
20 * Purpose: fun
21 * Problem: 12621 - On a Diet
22 */
23
24 /*
25 * This template reads data a specified number of times.
26 */
27
28 #define MAX_MEALS 105
29
30 int numberOfTimes;
31 int limit;
32 int meals[MAX_MEALS];
33 int mealCnt;
34
35
36 void init()
37 {
38 /* FUNCTION init */
39 scanf("%d ", &numberOfTimes);
40 } /* FUNCTION init */
41
42 void dump()
43 {
44 /* FUNCTION dump */
45 } /* FUNCTION dump */
46
47 int compare(const void *a, const void *b)
48 {
49 /* FUNCTION compare */
50 return ( *(int*)b - *(int*)a );
51 } /* FUNCTION compare */
52
53 void getInput()
54 {
55 /* FUNCTION getInput */
56 int i;
57
58 scanf(" %d %d ", &limit, &mealCnt);
59 for (i=0; i<mealCnt; i++)
60 {
61 /* get each meal */
62 scanf(" %d ", &meals[i]);
63 } /* get each meal */
64 qsort(meals, mealCnt, sizeof(int), compare);
65 } /* FUNCTION getInput */
66
67 int notEnough()
68 {
69 /* FUNCTION notEnough */
70 int tot = 0;
71 int i;
72
73 for (i=0; i<mealCnt; i++)
74 {
75 /* for each meal */
76 tot = tot + meals[i];
77 } /* for each meal */
78 return (tot >= limit);
79 } /* FUNCTION notEnough */
80
81 int calc(int x, int carry)
82 {
83 /* FUNCTION calc */
84 int i;
85 int toReturn = 0;
86 int tmp;
87
88 if (x != mealCnt)
89 {
90 /* not end of line */
91 tmp = meals[i] + calc(x+1,
92 toreturn
93 } /* not end of line */
94 } /* FUNCTION calc */
95
96 void process()
97 {
98 /* FUNCTION process */
99 int cals = 10000000;
100 int i;
101 int tmp;
102
103 if (notEnough())
104 {
105 /* not enough calories to meet minimum */
106 printf("NO SOLUTION\n");
107 } /* not enough calories to meet minimum */
108 else
109 {
110 /* find the best match */
111 for (i=1; i<mealCnt; i++)
112 {
113 /* try each meal */
114 tmp = calc(i, meals[i]);
115 if ((tmp < cals) && (tmp >=limit))
116 {
117 cals = tmp;
118 }
119 } /* try each meal */
120 } /* find the best match */
121 } /* FUNCTION process */
122
123
124 int main()
125 {
126 /* main */
127 int i;
128
129 init();
130 for (i=0; i<numberOfTimes; i++)
131 {
132 /* while */
133 getInput();
134 process();
135 } /* while */
136
137 return EXIT_SUCCESS;
138 } /* main */
139
140