# Data Structures and Algorithms (CS F211) Lab Sheet 4 solved

\$35.00

## Description

5/5 - (1 vote)

1. You go to the Egyptian market to get souvenirs for your friends and family. The market has weird rules. It
has n different items numbered from 1 to n. Each item i has a base cost of a[i] Egyptian pounds. If you buy
k different items with indices x1, x2, x3, …, xk then the cost of each item is a[i]+xj*k where j varies from 1 to
k. In other words, the cost of an item is equal to its base cost in addition to its index multiplied by the factor
k.
You want to buy as many souvenirs as possible and your budget is S Egyptian dollars. Find the maximum
number of items you can buy. In case the number of items is same, choose the one with the lowest total
cost.
Input:
First line contains n and your total budget S.
Second line contains n different integers each of which denotes the cost of each item.
Output:
Two integers which denote the number of items and total cost you will be spending.
Example:
3 14
2 3 5
2 11
Explanation:
You cannot get 3 items because they will cost you [5,9,14] and the total cost would be 28. If you get 2 items,
then the items would cost [4,7]. So, you can get items costing 4,7 which will cost you a total of 11 Egyptian
dollars.
2. You are trying to solve questions for the DSA lab exam. The question set consists of a large number of
different questions. You are exhausted today, so you decide to solve the problems like this:
You first solve v problems, the drink a cup of tea and solve floor(v/k) problems (where floor() function
returns the largest possible integer value which is less than or equal to the given argument), then
floor(v/(k*k) ), then floor(v/k*k*k) and so on…
The moment the value floor(v/(k^p) ) is equal to zero you stop and go to sleep.
Find the minimum value of v such that you solve not less than n questions.
Input:
Two integers n and k.
Output:
Print only one integer – the minimum value of v that lets you solve n questions.
Example:
7 2
4
Explanation:
When v = 4, then he solves the questions like this: 4, 2, 1.
Thus, he manages to solve 4+2+1 = 7 questions.
3. You are given a sorted list of elements. All of the elements in the array occur twice except for one element.
Find the element that occurs only once.
Example:
1 1 4 4 5 6 6
5
4. You and your friends are playing the game of stacking a pile of dominos. There are several towers of
dominos each with some height. You are given with some initial configuration of the towers. To
increase/decrease the height you need to add/remove the dominos. The number of dominos in the game
remains the same. Adding/removing incurs a cost which is different for different towers. You are assigned
with the task of making a set of towers such that all the towers have same height and the cost incurred is as
minimum as possible. Note that the initial number of towers and final number of towers may not be the
same.
Input:
First line contains the number of towers.
Second line contains the number of dominos in each tower.
Third line contains the cost incurred for each tower when adding/removing a domino.
Output:
Minimum cost, number of towers, height of each tower
Example:
3
1 2 3
10 100 200
110, 2, 3
Explanation: Remove a domino from Tower 1 (Cost 10) and add it to Tower 2 (Cost 100). Total cost is 110.
Note that the number of dominos (6) remains the same, however, the number of towers has become 2 and
the height of each tower is 3.
5. You are working in a factory and you have n machines running simultaneously. Each of the machinestakes
a certain time (in secs) to produce an item. The time is different for different machines. Your task is to find
the minimum time required to produce m items using Binary Search.
Input: First line contains n and m.
Second line contains an array which denotes how much each machine takes to produce an item.
Output:
Single integer denoting the minimum time to produce m items.
Example:
3 11
1 2 3