Description
Efficient Adding
You are tasked with writing a program that adds a sequence of numbers. But the added challenge is to do so efficiently!
The cost of adding two numbers a and b is equal to their sum a+b . For example: to add 1, 2, and 3, you can do it as
follows:
1 + 2 = 3, cost of 3
3 + 3 = 6, cost of 6
Total cost = 9
or
2 + 3 = 5, cost of 5
1 + 5 = 6, cost of 6
Total cost = 11
or
1 + 3 = 4, cost of 4
2 + 4 = 6, cost of 6
Total cost = 10
Your goal is to add the numbers so that the cost is as small as possible.
Input
The first line of input contains a positive number N ( 2 <= N <= 5000 ) that tells you how many numbers there are to
add.
The second line of input contains those N numbers 0 <= n_1, n_2, …, n_N <= 100,000 .
Output
The minimum total cost of addition followed by a newline.
Example 1
Input:
3
1 2 3
Output:
9
Example 2
Input:
4
1 2 3 4
Output:
19
Page 1/2
Grocery Delivery
Nia hates shopping and she really despises grocery shopping. She orders her groceries from a local store. In preparation
for drone deliveries, the store has new rules about packing items for delivery:
they will deliver exactly two boxes to the customer (even if the order is small and one of the boxes is empty)
the capacity of each box is the same and equal to W.
Nia knows the volume occupied by each item on her shopping list: the i
th
item has the volume vi
. With the new rules, she has
to prioritize the items that she orders since not everything can fit in the two boxes. Her list is arranged in the order of priority:
from the most important item to the least important one (i.e., the i
th
item is always more important than the i+1
st
item). As
she prepares the list to send to the store, she only orders the highest priority items and as soon as she comes to an item
that is too large to fit in the remaining space in the boxes, she skips that item and all the items below.
The question is how many items from her list she will be able to order and which item should be placed in which box.
Input
The first line contains 2 integers N and W, indicating the number of items and the capacity of a box, 1 <= N <= 200, 1 <= W
<= 10000.
The second line contains N integers, indicating the volume of items in Nia’s list. They are in the order of priority as described
above.
Output
The first line of output should specify the number of items that can be ordered.
For each item that can be ordered, output a line containing “1st” if the item is to be placed in the 1st box and “2nd” if the
item is to be placed in the 2nd box. If several arrangements of the items are possible, any one will do.
Example 1
Input:
5 10
1 2 100 3 4
Output:
2
1st
1st
Page 2/2
Explanation of example 1:
Nia has to remove the 3rd item since it’s too large (this means that the 4th and the 5th items are also removed from the
order, even though they could fit in the second box).
The first 2 items will be ordered. Any arrangement of the items in boxes will do.
Example 2
Input:
7 50
25 30 10 10 15 7 8
Output:
6
1st
2nd
2nd
2nd
1st
1st
Page 1/1
Ayu’s Shopping
Ayu is keen on desserts. She found that she will run out of them soon so she decided to buy some more today. Her favorite
dessert shop offers several flavors (banana, grape, vanilla, etc.) for every kind of dessert (candy, cake, ice-cream, etc.). Ayu
has M dollars and she wants to spend as much of that money as possible. She also doesn’t want to get too fat so she
decided to buy only one flavor of each kind of dessert. The question is how much money will she spend.
Input
The first line of the input contains two integers M (1 <= M <= 200) and N (1 <= N <= 20), indicating the amount of money
Ayu has and the number of different kinds of desserts. Each of the following N lines contains K + 1 integers where K is the
first integer of that line (1 <= K <= 20), indicating the number of flavors for this kind of dessert. The following K integers
indicate the price for each flavor of the dessert (these are integers).
Output
Print one line consisting of one integer indicating the maximum amount of money spent to buy one flavor of each kind of
dessert, or no solution if there is no solution.
Example 1
Input:
100 4
3 8 6 4
2 5 10
4 1 3 3 7
4 50 14 23 8
Output:
75
by picking 8, 10, 7 and 50.
Example 2
Input:
20 3
3 4 6 8
2 5 10
4 1 3 5 5
Output:
19
Example 3
Input:
5 3
3 6 4 8
2 10 6
4 7 3 1 7
Output:
no solution
Page 1/1
Word Counter
Morty has an essay assignment with a minimum word count, one of the worst assignments in the universe. He feels really
bad when he believes that he has finished but finds that he’s still well below the minimum word count.
To check if his essay meets the requirement, he needs to count the number of words in the essay. It’s pretty cumbersome.
Please help poor Morty, he can hardly wait to be done with it!
Input
Input to your program will consist of a single line, containing multiple words (at least one).
A “word” is defined as a consecutive sequence of letters (upper and/or lower case).
Output
Please output the word count for the input.
Example 1
Input:
wubba lubba dub dubs
Output:
4
Example 2
Input:
Lorem ipsum dolor sit amet, consectetur adipisicing elit.
Output:
8
Example 3
Input:
printf(“This string has %d words\n”, 7);
Ouput:
7
The words are: “printf”, “This”, “string”, “has”, “d”, “words”, “n”
Page 1/1
Laughing Monsters
The world has been attacked by Laughing Monsters . They camouflage as humans at movie theaters. Anybody sitting
within D feet from a Laughing Monster will get infected and will have to endure uncontrollable laughter attacks for the
next week. Moreover, once infected, these people will infect other humans sitting within D feet of them.
The movie theater owners need to be able to provide information about anybody who might have been exposed to this
infection if the authorities identify a particular person to be really a camouflaged Laughing Monster .
Your job is to write a program that will identify the number the groups of theater guests who are in risk of infection if one of
them is identified as a Laughing Monster .
Two theater guests belong to the same group if distance between their seats is less than or equal to D feet.
Input
The first line contains the number of theater guests N ( 0 <= N <= 1,000 ) and the distance D (a real number
0.0 <= D <= 1,000.00 ). Next N lines have a pair of real coordinates X Y (where –
1,000.00 <= X, Y <= 1,000.00 ) for location of each guest in the theater.
All real numbers in the input will have at most 2 (two) digits after a decimal point.
Output
Output the number of distinct groups.
Example 1
Input:
5 1.5
1.0 0.1
2.0 0.0
5.0 0.2
6.0 0.4
3.0 -0.1
Output:
2
Example 2
Input:
3 4.0
121.12 254.06
645.04 301.85
912.49 568.96
Output:
3