C++

Forum

 
Need a more efficient program

Oriol Serrabassa (100)
This problem is about counting how many times the bells of a church sounds during a period of time called t (in minutes).

This church has two different types of bells, the ones that ring every hour, "g" in program, (19:00 -> 7 times) and the ones which ring every quarter of hour, "a" in program (19:00 -> 4 times, 19:15 -> 1 time, 19:30 -> 2 times, 19:45 -> 3 times). However when it is "Angelus" time which is at 12:00 the bells will ring a total of 104 times (100 times "g" bells and 4 times "a" bells). Every time the bells start playing, they always finish strictly within the next minute.

The input is the hour time (hours and minutes) followed by the period of time t.

Here is the first code I got which it was too slow

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
 
#include <iostream>
using namespace std;

int main () {
	int h, m, t;
	while (cin >> h >> m >> t) {
		int a = 0, g = 0, total = 0;
		for (int i = 0; i < t; ++i) {
			++m;
			if (m == 60) {
				m = 0;
				h += 1;
			}
			if (h == 24) h = 0;
			if (h == 12) {
				if (m == 1) {
					total += 100;
					a += 4;
				}
				if (m == 16) a += 1;
				if (m == 31) a += 2;
				if (m == 46) a += 3;
			}
			if (h != 12) {
				if (m == 1) {
					a += 4;
					if (h == 0) g += 12;
					if (h > 0 and h < 12) g += h;
					if (h > 12) {
						int ch = h;
						ch -= 12;
						g += ch;
					}
				}
				if (m == 16) a += 1;
				if (m == 31) a += 2;
				if (m == 46) a += 3;
			}
		}
		total += a+g;
		cout << total << endl;
	}
}


Since this code was too slow, I decided that to improve it and make it more efficient I would have to reduce the number of iterations in the while and I came with the following code, however, it is not fast enough...

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
 
#include <iostream>
using namespace std;

int main () {
	int h, m, t;
	while (cin >> h >> m >> t) {
		int a = 0, g = 0, total = 0;
		while (t > 0) {
			if (m%15 == 1 and t >= 15) {
				m += 15;
				t -= 15;
			}
			else {
				++m;
				--t;
			}
			if (m >= 60) {
				m -= 60;
				h += 1;
				if (h == 24) h = 0;
			}
			if (h == 12 and m == 1) {
				total += 100;
				a += 4;
			}
			if (h != 12 and m == 1) {
				a += 4;
				if (h == 0) g += 12;
				if (h > 0 and h < 12) g += h;
				if (h > 12) {
					int ch = h-12;
					g += ch;
				}
			}
			if (m == 16) a += 1;
			if (m == 31) a += 2;
			if (m == 46) a += 3;
		}
		total += a+g;
		cout << total << endl;
	}
}


I do not have any more ideas on how to improve this code so I would like advices on what to do.
Last edited on
jlb (4973)
Here is the first code I got which it was too slow

What do you mean by "too slow"?

it is not fast enough

Again what do you mean by not fast enough?

Probably the biggest bottle neck in this code is the user input.

Oriol Serrabassa (100)
It means that it takes too much time to output the result. This means that there are other methods that can output the result in less time.

Basically, I need a code that outputs faster with the correct solution than those previous two.

To put it more clearly, with the following input: 23 57 1234567890
My first program took 4,89 seconds approximately to output the result, meanwhile my second program only took 0,42 seconds. With some maths, we can say that my second program was 1160% faster than my first program and since my second program isnt fast enough, I need a program that beats that time in outputting the result.
Last edited on
keskiverto (10402)
Why do you have a loop at all?

Within each 60 minutes you do get 10a. Only the t%60 needs special handling.
Similar with the d's.
Oriol Serrabassa (100)
I am not probably quite getting what you are trying to say keskiverto but are you saying it is possible to solve this problem without a loop?

Within each 60 minutes I always get 10a that's right but if I get 59 minutes for example it can change from 9a (maximum -> X:16) to 6a (minimum -> X:46) so how is that helpful?

If possible I would like you to explain better
Last edited on
Pattako (74)
Did you try to run your program in Release mode?
Debug mode is very famous for very terrible performance.
Pattako (74)
while (cin >> h >> m >> t) {
Inputs slow down your whole program, and they would make time measure inaccurate.
JLBorges (13770)
Hint:

1. How many times would the bells ring in a complete day (12:01 am to midnight). This is a constant, known at compile-time.

2. How many complete days are there in 1234567890 minutes starting at 23:57 on a particular day?

3. How many times would the bells ring, starting from a particular time hh:mm till midnight on that day

4. How many times would the bells ring, starting from 12:01 am till a particular time hh:mm on that day

Note: if "Angelus" is both at 12:00 noon and 12:00 midnight, instead of dealing in 24-hour periods as above, we can deal in 12-hour intervals.
Last edited on
Oriol Serrabassa (100)
Okay, new entry to this post.

I got a code that is faster than those previous two (probably fast enough this time) but it gives incorrect outputs in some results and I have no idea why.

Some examples:
Input: 13 0 12113940
Output (my program): 4071600
Output (correct): 4071584
Difference of 16 bells (probably something related to 00:00 h because 12g + 4a = 16)

I believe this is the cause but tested it with smaller numbers and had no problem (4071600 is divisible by 60 and not for 1440):

1
2
3
4
5
6
7
8
9
10
11
12
 
                                 if (ct == 60) {
					a -= 4;
					if (h == 12) angelus -= 100;
					if (h != 12) {
						if (h == 0) g -= 12;
						if (h > 0 and h < 12) g -= h;
						if (h > 12) {
							int ch = h-12;
							g -= ch;
						}
					}
                                }


Input: 12 30 47625111
Output (my program): 16007421
Output (correct): 16007332
Difference of 89 bells (no idea how why such big range and why it happened)

Lastly, the code (I know it is horrible, no need to tell me);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
 
#include <iostream>
using namespace std;

int main () {
	int h, m, t;
	while (cin >> h >> m >> t) {
		int a = 0, g = 0, angelus = 0, total = 0;
		while (t > 0) {
			if (t >= 1440) {
				int nd = t/1440;
				int cd = t;
				t = t%1440;
				for (int i = 0; i < nd; ++i) {
					a += 240;
					g += 144;
					angelus += 100;
				}
				if (cd == 1440) {
					a -= 4;
					if (h == 12) angelus -= 100;
					if (h != 12) {
						if (h == 0) g -= 12;
						if (h > 0 and h < 12) g -= h;
						if (h > 12) {
							int ch = h-12;
							g -= ch;
						}
					}
				}
			}
			if (t >= 60 and t < 1440) {
				int nh = t/60;
				int ct = t;
				m += (60*nh);
				t = t%60;
				for (int i = 0; i < nh; ++i) {
					if (h == 12) {
						angelus += 100;
						a += 10;
					}
					if (h != 12) {
						a += 10;
						if (h == 0) g += 12;
						if (h > 0 and h < 12) g += h;
						if (h > 12) {
							int ch = h-12;
							g += ch;
						}
					}
					if (m >= 60) {
						m -= 60;
						h += 1;
						if (h == 24) h = 0;
					}
				}
				if (ct == 60) {
					a -= 4;
					if (h == 12) angelus -= 100;
					if (h != 12) {
						if (h == 0) g -= 12;
						if (h > 0 and h < 12) g -= h;
						if (h > 12) {
							int ch = h-12;
							g -= ch;
						}
					}
				}
			}
			if (t < 60) {
				if (m%15 == 1 and t >= 15) {
					m += 15;
					t -= 15;
				}
				else {
					++m;
					--t;
				}
				if (m >= 60) {
					m -= 60;
					h += 1;
					if (h == 24) h = 0;
				}
				if (h == 12 and m == 1) {
					angelus += 100;
					a += 4;
				}
				if (h != 12 and m == 1) {
					a += 4;
					if (h == 0) g += 12;
					if (h > 0 and h < 12) g += h;
					if (h > 12) {
						int ch = h-12;
						g += ch;
					}
				}
				if (m == 16) a += 1;
				if (m == 31) a += 2;
				if (m == 46) a += 3;
			}
		}
		total += a+g+angelus;
		cout << total << endl;
	}
}


If anyone has an idea of what is happening I would like to know, meanwhile I will try to figure myself what is wrong in the code. My previous two programs give me correct output so it means that the error in this program has to be in the new added code lines.
Last edited on
Oriol Serrabassa (100)
Finally got it to work, YEEEY

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
 
#include <iostream>
using namespace std;

int main () {
	int h, m, t;
	while (cin >> h >> m >> t) {
		int a = 0, g = 0, angelus = 0, total;
		while (t > 0) {
			if (t >= 1440) {
				int nd = t/1440;
				t = t%1440;
				for (int i = 0; i < nd; ++i) {
					a += 240;
					g += 144;
					angelus += 100;
				}
			}
			if (t >= 60) {
				int nh = t/60;
				m += (60*nh);
				t = t%60;
				while (m >= 60) {
					if (m%60 == 0) {
						if (h == 12) {
							angelus += 100;
							a += 10;
						}
						if (h != 12) {
							a += 10;
							if (h == 0) g += 12;
							if (h > 0 and h < 12) g += h;
							if (h > 12) {
								int ch = h-12;
								g += ch;
							}
						}
						m -= 60;
						h += 1;
						if (h == 24) h = 0;
					}
					else {
						m -= 60;
						h += 1;
						if (h == 24) h = 0;
						if (h == 12) {
							angelus += 100;
							a += 10;
						}
						if (h != 12) {
							a += 10;
							if (h == 0) g += 12;
							if (h > 0 and h < 12) g += h;
							if (h > 12) {
								int ch = h-12;
								g += ch;
							}
						}
					}
				}
			}
			if (t > 0) {
				if (m%15 == 1 and t >= 15) {
					m += 15;
					t -= 15;
				}
				else {
					++m;
					--t;
				}
				if (m >= 60) {
					m -= 60;
					h += 1;
					if (h == 24) h = 0;
				}
				if (h == 12 and m == 1) {
					angelus += 100;
					a += 4;
				}
				if (h != 12 and m == 1) {
					a += 4;
					if (h == 0) g += 12;
					if (h > 0 and h < 12) g += h;
					if (h > 12) {
						int ch = h-12;
						g += ch;
					}
				}
				if (m == 16) a += 1;
				if (m == 31) a += 2;
				if (m == 46) a += 3;
			}
		}
		total = a+g+angelus;
		cout << total << endl;
	}
}


The fun part is that there are 4 versions of this problem and this was the easiest one.

If anyone wants to share a better code than mine is welcomed.
Last edited on
Topic archived. No new replies allowed.