Definition

Competitive Programming is a sport, which requires participants to program to solve computational problems. The score a participant gets is normally calculated based on how many problems he solved, the difficulty of the problems, the time he spends on each problem and the number of attempts he made before successfully solve each problem. Each problem is well-defined, clear and has concrete limits and constraints.

A competition can be held locally or globally. There are some annual global competitions, like IOI (International Olympiad in Informatics) – an individual-based contest for high-school students, ICPC (International Collegiate Programming Contest) – a team-based contest for college students, Google Code Jam – hosted by Google, Facebook Hacker Cup – from Facebook.

Example

Here is an example of a problem:

Problem statement | Alice has n bags of candies. Each bag contains a number of candies. As she is going for a long vacation soon, she wants to prepare some candies to eat during the vocation. We know that her vocation will last m days, and she wants to eat 1 candy each day. Could you help her find out the least number of bags that she can bring so that her sweet tooth is satisfied? |

Input format | The first line contains 2 space-separated integers: n and m. The second line contains n space-separated integer. The i-th integer represents the number of candies Alice has in the i-th bag. |

Output format | Print the minimum number of bags Alice can bring so that she has a candy to eat for each day of her vocation. |

Constraints | . . The number of candies in each bag . The total number of candies in all the bags . |

Time limit | 1 second. (This means that your program should run in at most 1 seconds) |

Memory limit | 64 megabytes. (Your program should use at most 64 MB of memory) |

Example 1 | Input: 5 9 8 2 6 4 3 Output: 2 |

Example 2 | Input: 3 10 3 4 3 Output: 3 |

There are many ways to solve the above problem. I will present the one I think is the most simple:

First, we sort all the bags in the non-increasing order of the number of candies.

Then, we check if the number of candies in the biggest bag is . If it is, we output *1* as the result. If it is not, then we check if the total number of candies in the 2 biggest bags is . If it is, we output *2* as the result. If it is not, then we check the total number of candies in the 3 biggest bags and so on, until we find that the total number of candies in *k* biggest bags is .

Here is out solution written in C++:

#include<bits/stdc++.h> using namespace std; int a[105]; int n, m; int main() { cin >> n >> m; for (int i = 1; i <= n; ++i) cin >> a[i]; sort(a + 1, a + n + 1); reverse(a + 1, a + n + 1); int sum_of_candies = 0; for (int i = 1; i <= n; ++i) { sum_of_candies += a[i]; if (sum_of_candies >= m) { cout << i << endl; break; } } return 0; }

Some websites to learn and practice Competitive Programming

and many others.