/home/toolbox/public_html/solutions/126/12663/b.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*)b - *(int*)a );
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 = 0;
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 if (depth < bridges[j])
91 {
92 /* if water was below bridge */
93 if (a >= bridges[j])
94 {
95 /* water go to bridge */
96 floods[j]++;
97 } /* water go to bridge */
98 } /* if water was below bridge */
99 } /* for each flood */
100 depth = b;
101 } /* for each flood */
102 for (i=0; i<n; i++)
103 {
104 /* count bridges that flooded enough */
105 if (k <= floods[i])
106 {
107 cnt++;
108 }
109 } /* count bridges that flooded enough */
110 printf("%d\n", cnt);
111
112 } /* FUNCTION process */
113
114 int main()
115 {
116 /* main */
117 int i = 1;
118
119 getInput();
120 while (moreToDo)
121 {
122 /* while */
123 printf("Case %d: ", i);
124 i++;
125 process();
126 getInput();
127 } /* while */
128
129 return EXIT_SUCCESS;
130 } /* main */
131
132