/home/toolbox/public_html/solutions/126/12663/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-18
20 * Purpose: fun
21 * Problem: 12663 - High Bridge, low bridge
22 */
23
24 /*
25 * This template reads data a specified number of times.
26 */
27
28 #define MAX_BRIDGES 100001
29
30 int moreToDo;
31 int n;
32 int m;
33 int k;
34 int bridges[MAX_BRIDGES];
35 int floods[MAX_BRIDGES];
36
37 void init()
38 {
39 /* FUNCTION init */
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*)a - *(int*)b );
51 } /* FUNCTION compare */
52
53 void getInput()
54 {
55 /* FUNCTION getInput */
56 int i;
57
58 moreToDo = (3 == scanf(" %d %d %d ", &n, &m, &k));
59 if (moreToDo)
60 {
61 /* more data to process */
62 for (i=0; i<n; i++)
63 {
64 /* get each bridge */
65 scanf(" %d ", &bridges[i]);
66 floods[i] = 0;
67 } /* get each bridge */
68 qsort(bridges, n, sizeof(int), compare);
69 } /* more data to process */
70 } /* FUNCTION getInput */
71
72 void process()
73 {
74 /* FUNCTION process */
75 int i;
76 int j;
77 int a;
78 int b;
79 int depth = 1;
80 int cnt = 0;
81
82 for (i=0; i<m; i++)
83 {
84 /* for each flood */
85 scanf(" %d %d ", &a, &b);
86 /* a is the max water height, b is after flood */
87 for (j=0; j<n; j++)
88 {
89 /* for each flood */
90 DEBUG printf(" bridge[%d] = %d\n", j, bridges[j]);
91 if (depth < bridges[j])
92 {
93 /* if water was below bridge */
94 if (a >= bridges[j])
95 {
96 /* water go to bridge */
97 floods[j]++;
98 } /* water go to bridge */
99 else
100 {
101 /* found higher bridghe -- quit */
102 j = n;
103 } /* found higher bridghe -- quit */
104 } /* if water was below bridge */
105 } /* for each flood */
106 depth = b;
107 } /* for each flood */
108 for (i=0; i<n; i++)
109 {
110 /* count bridges that flooded enough */
111 if (k <= floods[i])
112 {
113 cnt++;
114 }
115 } /* count bridges that flooded enough */
116 printf("%d\n", cnt);
117
118 } /* FUNCTION process */
119
120 int main()
121 {
122 /* main */
123 int i = 1;
124
125 getInput();
126 while (moreToDo)
127 {
128 /* while */
129 printf("Case %d: ", i);
130 i++;
131 process();
132 getInput();
133 } /* while */
134
135 return EXIT_SUCCESS;
136 } /* main */
137
138