CCO '12 P5 - Sample Size

View as PDF

Submit solution

Points: 7
Time limit: 2.0s
Memory limit: 64M

Problem type
Canadian Computing Olympiad: 2012 Day 2, Problem 2:

Someone whose name I don't want to remember was reading an article in the newspaper that mentioned the results of a poll. Upon seeing that the percentages that appeared in the article were all 25\%, 50\% and 75\%, they thought that maybe the poll only included 4 people, and was then not very good.

In this problem, your task is to come up with a program that would make a similar analysis. In particular, given the percentages that appear in a newspaper article, it is your task to determine the minimum number of people that must have been interviewed in order for those percentages to be possible, assuming that percentages are rounded to the closest integer, with .5 rounded up (so, 1 of 3 people corresponds to 33\%, 2 of 3 people corresponds to 67\%, and 155 of 1\,000 people corresponds to 16\%).

Input Specification

The first line of the input file will contain an integer M between 1 and 100\,000 (inclusive). This represents the number of percentages that appear in the newspaper article you are analyzing. M lines will follow, each of them containing an integer percentage P, 0 \le P \le 100.

Output Specification

An integer N \ge 1, the minimum number of people that must be interviewed for all of the percentages in the input to correspond to a fraction of those people.

Sample Input 1

3
25
50
75

Sample Output 1

4

Sample Input 2

2
33
67

Sample Output 2

3

Comments

There are no comments at the moment.