/home/toolbox/public_html/solutions/110/11057/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 <stdint.h>
7 #include <math.h>
8 #include <stdlib.h>
9
10 #define TRUE (1 == 1)
11 #define FALSE (1 != 1)
12
13 #define DEBUG if (FALSE)
14
15 /*
16 * Author: Isaac Traxler
17 * Date: 2018-09-25
18 * Purpose: fun
19 * Problem: 11057
20 */
21
22 /*
23 * This template reads data until a terminating value is reached.
24 */
25
26 #define MAX_BOOKS 10002
27
28 int numBooks;
29 int money;
30 int prices[MAX_BOOKS];
31
32 void init()
33 {
34 /* FUNCTION init */
35 } /* FUNCTION init */
36
37 void dump()
38 {
39 /* FUNCTION dump */
40 } /* FUNCTION dump */
41
42 int getInput()
43 {
44 /* FUNCTION getInput */
45 int dataReadFlag;
46 int i;
47
48 dataReadFlag = (0 < scanf(" %d ", &numBooks));
49 if (dataReadFlag)
50 {
51 /* okay -- we have books to deal with */
52 for (i=0; numBooks>i; i++)
53 {
54 /* read each book price */
55 scanf(" %d ", &prices[i]);
56 } /* read each book price */
57 scanf(" %d ", &money);
58 } /* okay -- we have books to deal with */
59 return (dataReadFlag);
60 } /* FUNCTION getInput */
61
62 int intcmp(const void *v1, const void *v2)
63 {
64 /* FUNCTION intcmp */
65 return (*(int *)v1 - *(int *)v2);
66 } /* FUNCTION intcmp */
67
68 void process()
69 {
70 /* FUNCTION process */
71 int i;
72 int j;
73 int iBest;
74 int jBest;
75 int diff;
76 int tmp;
77
78 diff = money + 1;
79 qsort(prices, numBooks, sizeof(prices[0]), intcmp);
80 DEBUG printf("numBooks(%d) money(%d)\n", numBooks, money);
81 DEBUG printf("price[%d] = %d\n", 0, prices[0]);
82 DEBUG printf("price[%d] = %d\n", numBooks - 1, prices[numBooks - 1]);
83 i = 0;
84 j = numBooks - 1;
85 while (i < j)
86 {
87 /* look for a match */
88 DEBUG printf("prices[%d]=%d prices[%d]=%d\n", i, prices[i], j, prices[j]);
89 if ((prices[i] + prices[j]) == money)
90 {
91 /* match found */
92 tmp = prices[j] - prices[i];
93 if (tmp < diff)
94 {
95 /* better match found */
96 diff = tmp;
97 iBest = i;
98 jBest = j;
99 } /* better match found */
100 /* since a match was found, move i up and j down */
101 i++;
102 j--;
103 } /* match found */
104 else
105 {
106 /* no match -- keep going */
107 if ((prices[i] + prices[j]) < money)
108 {
109 /* total price is to low -- move up lower cost */
110 i++;
111 } /* total price is to low -- move up lower cost */
112 else
113 {
114 /* price to high -- bring down upper value */
115 j--;
116 } /* price to high -- bring down upper value */
117 } /* no match -- keep going */
118 } /* look for a match */
119 printf("Peter should buy books whose prices are %d and %d.\n\n", prices[iBest], prices[jBest]);
120 } /* FUNCTION process */
121
122 int main()
123 {
124 /* main */
125 int moreToDo;
126
127 init();
128 moreToDo = getInput();
129 while (moreToDo)
130 {
131 /* while */
132 process();
133 moreToDo = getInput();
134 } /* while */
135
136 return EXIT_SUCCESS;
137 } /* main */
138