Question 1
- Introduction: In this problem, you will design and implement an elementary greedy algorithm used by cashiers all over the world millions of times per day.
- Task: The goal in this problem is to find the minimum number of coins needed to change the input value(an integer) into coins with denominations 1, 5, and 10.
- Input Format: The input consists of a single integer m(1 ≤ m ≤ 103)
- Output Format: Output the minimum number of coins with denominations 1, 5, 10 that changes m
import sys
def get_change(m):
#write your code here
n10 = m//10
n5 = (m%10)//5
n1 = (m%10)%5
return n1+n5+n10
### run
if __name__ == '__main__':
m = int(sys.stdin.read())
print(get_change(m))
Question 2
- Introduction: A thief finds much more loot than his bag can fit. Help him to find the most valuable combination of items assuming that any fraction of a loot item can be put into his bag.
- Task: The goal of this code problem is to implement an algorithm for the fractional knapsack problem.
- Input Format: The first line of the input contains the number n of items and the capacity W of a knapsack. The next n lines define the values and weights of the items. The i-th line contains integers vi and wi—the value and the weight of i-th item, respectively(1 ≤ n ≤ 103, 0 ≤ W ≤ 2 · 106; 0 ≤ vi ≤ 2 · 106, 0 < wi ≤ 2 · 106 for all 1 ≤ i ≤ n. All the numbers are integers)
- Output Format: Output the maximal value of fractions of items that fit into the knapsack.
import sys
def get_optimal_value(capacity, weights, values):
value = 0.
# write your code here
temp = [(w,v/w) for w,v in zip(weights, values)]
temp = sorted(temp, key=lambda s:s[1], reverse=True)
remain = capacity
for i in range(len(temp)):
if remain==0: break
w_in = min(remain, temp[i][0])
remain -= w_in
value += w_in*temp[i][1]
return value
if __name__ == "__main__":
data = list(map(int, sys.stdin.read().split()))
n, capacity = data[0:2]
values = data[2:(2 * n + 2):2]
weights = data[3:(2 * n + 2):2]
opt_value = get_optimal_value(capacity, weights, values)
print("{:.10f}".format(opt_value))
Question 3
- Introduction: You have n ads to place on a popular Internet page. For each ad, you know how much is the advertiser willing to pay for one click on this ad. You have set up n slots on your page and estimated the expected number of clicks per day for each slot. Now, your goal is to distribute the ads among the slots to maximize the total revenue.
- Task: Given two sequences a1, a2, . . . , an (ai is the profit per click of the i-th ad) and b1, b2, . . . , bn (bi is the average number of clicks per day of the i-th slot), we need to partition them into n pairs ((ai, bj ) such that the sum of their products is maximized.
- Input Format: The first line contains an integer n, the second one contains a sequence of integers a1, a2, . . . , an, the third one contains a sequence of integers b1, b2, . . . , bn(1 ≤ n ≤ 103; −105 ≤ ai, bi ≤ 105 for all 1 ≤ i ≤ n.)
- Output Format: Output the maximum value of , where c1, c2, . . . , cn is a permutation of b1, b2, . . . , bn.
import sys
def max_dot_product(a, b):
#write your code here
return sum([x*y for x,y in zip(sorted(a),sorted(b))])
if __name__ == '__main__':
input = sys.stdin.read()
data = list(map(int, input.split()))
n = data[0]
a = data[1:(n + 1)]
b = data[(n + 1):]
print(max_dot_product(a, b))
Question 4
- Introduction: You are responsible for collecting signatures from all tenants of a certain building. For each tenant, you know a period of time when he or she is at home. You would like to collect all signatures by visiting the building as few times as possible. The mathematical model for this problem is the following. You are given a set of segments on a line and your goal is to mark as few points on a line as possible so that each segment contains at least one marked point.
- Task: Given a set of n segments {[a0, b0], [a1, b1], . . . , [an−1, bn−1]} with integer coordinates on a line, find the minimum number m of points such that each segment contains at least one point. That is, find a set of integers X of the minimum size such that for any segment [ai, bi] there is a point x ∈ X such that ai ≤ x ≤ bi.
- Input Format: The first line of the input contains the number n of segments. Each of the following n lines contains two integers ai and bi (separated by a space) defining the coordinates of endpoints of the i-th segment(1 ≤ n ≤ 100; 0 ≤ ai ≤ bi ≤ 109 for all 0 ≤ i < n)
- Output Format: Output the minimum number m of points on the first line and the integer coordinates of m points (separated by spaces) on the second line. You can output the points in any order. If there are many such sets of points, you can output any set. (It is not difficult to see that there always exist a set of points of the minimum size such that all the coordinates of the points are integers.)
import sys
from collections import namedtuple
Segment = namedtuple('Segment', 'start end')
def optimal_points(segments):
points = []
#write your code here
segments = sorted(segments, key=lambda s: s.end)
points.append(segments[0].end)
for s in segments:
if s.start>points[-1]:
points.append(s.end)
return points
if __name__ == '__main__':
input = sys.stdin.read()
n, *data = map(int, input.split())
segments = list(map(lambda x: Segment(x[0], x[1]), zip(data[::2], data[1::2])))
points = optimal_points(segments)
print(len(points))
for p in points:
print(p, end=' ')
Question 5
- Introduction: You are organizing a funny competition for children. As a prize fund you have n candies. You would like to use these candies for top k places in a competition with a natural restriction that a higher place gets a larger number of candies. To make as many children happy as possible, you are going to find the largest value of k for which it is possible.
- Task: The goal of this problem is to represent a given positive integer n as a sum of as many pairwise distinct positive integers as possible. That is, to find the maximum k such that n can be written as a1 + a2 + · · · + ak where a1, . . . , ak are positive integers and ai≠aj for all 1 ≤ i < j ≤ k.
- Input Format: The input consists of a single integer n(1 ≤ n ≤ 109)
- Output Format: In the first line, output the maximum number k such that n can be represented as a sum of k pairwise distinct positive integers. In the second line, output k pairwise distinct positive integers that sum up to n (if there are many such representations, output any of them).
import sys
def optimal_summands(n):
summands = []
#write your code here
remain = n
for i in range(1,n+1):
last_c = i if remain-i>i else remain
summands.append(last_c)
remain -= last_c
if remain==0: break
return summands
if __name__ == '__main__':
input = sys.stdin.read()
n = int(input)
summands = optimal_summands(n)
print(len(summands))
for x in summands:
print(x, end=' ')
Question 6
- Introduction: As the last question of a successful interview, your boss gives you a few pieces of paper with numbers on it and asks you to compose a largest number from these numbers. The resulting number is going to be your salary, so you are very much interested in maximizing this number. How can you do this?
- Task: Compose the largest number out of a set of integers.
- Input Format: The first line of the input contains an integer n. The second line contains integers a1, a2, . . . , an(1 ≤ n ≤ 100; 1 ≤ ai ≤ 103 for all 1 ≤ i ≤ n)
- Output Format: Output the largest number that can be composed out of a1, a2, . . . , an.
import sys
from functools import cmp_to_key
def comp(a,b):
if a[0]>b[0]:
return 1
elif a[0]<b[0]:
return -1
else:
ab = a+b
ba = b+a
return 1 if ab>ba else -1 if ab<ba else 0
def largest_number(a):
#write your code here
a = sorted(a, key=cmp_to_key(comp), reverse=True)
return ''.join(a)
if __name__ == '__main__':
input = sys.stdin.read()
data = input.split()
a = data[1:]
print(largest_number(a))