# Prize equalizer:

**Author:** Arpit Mishra

# DIFFICULTY:

Simple

# PROBLEM:

You are both a shop keeper and a shop assistant at a small nearby shop. You have n goods, the i-th good costs ai coins.

You got tired of remembering the price of each product when customers ask for it, thus you decided to simplify your life. More precisely you decided to set the same price for all n goods you have.

However, you don’t want to lose any money so you want to choose the price in such a way that the sum of new prices is not less than the sum of the initial prices. It means that if you sell all n goods for the new price, you will receive at least the same (or greater) amount of money as if you sell them for their initial prices.

On the other hand, you don’t want to lose customers because of big prices so among all prices you can choose you need to choose the minimum one.

So you need to find the minimum possible equal price of all n goods so if you sell them for this price, you will receive at least the same (or greater) amount of money as if you sell them for their initial prices.

You have to answer q independent queries.

# EXPLANATION:

In this problem, we need to find the minimum possible price such that price⋅n≥sum, where sum is the sum of all ai. price equals to ⌈sum/n⌉, where ⌈x/y⌉ is x divided by y rounded up.

# SOLUTION:

## Setter's Solution

```
#include <bits/stdc++.h>
using namespace std;
int main()
{
int q;
cin >> q;
for (int i = 0; i < q; ++i)
{
int n;
cin >> n;
int sum = 0;
for (int j = 0; j < n; ++j)
{
int x;
cin >> x;
sum += x;
}
cout << (sum + n - 1) / n << endl;
}
return 0;
}
```

# Find The Student:

**Author:** Arpit Mishra

Mudit Mahajan

# DIFFICULTY:

Simple

# PROBLEM:

There are n students in the class numbered 1 to n. The teacher is

collecting the homework assignments from the student in the class.

But there is one student who has not completed the assignment and the

teacher wants to find that student.

The teacher has a list of values a_i which denote the students who have

submitted the assignment. This list might contain duplicates.

Help the teacher determine if he can find the student who has not

submitted the assignment or determine if not possible.

If possible, print YES otherwise NO.

If the list a contain all n student, then the student copied the

assignment and submitted it. It is not possible to catch him and thus

you should print NO.

If there is more than 1 student who has not submitted the assignment,

then also you should print NO as the teacher wants to find only the

unique student.

# EXPLANATION:

In the problem, we need to find if there is *only* 1 unique student who

has not submitted the assignment.

If there is more than 1 student who has not submitted the assignment,

then our answer is **NO** otherwise it is **YES**.

If the list contains all the students, then also our answer will be

**NO**.

This can be solved by using *set*(set does not allow duplicates).

if the size of our set is *exactly* 1 less than the number of students,

then only our answer will be **YES**.

# SOLUTION:

## Setter's Solution

```
#include<bits/stdc++.h>
using namespace std;
int main()
{
ll k, n, i;
cin >> k >> n;
ll arr[n];
unordered_set<ll> s;
for(i = 0; i < n; i++)
{
cin >> arr[i];
s.insert(arr[i]);
}
temp = s.size();
if(k - temp == 1)
{
cout << "YES" << endl;
}
else
{
cout << "NO" << endl;
}
}
```

# The Jumbled Addition

**Author:** Arpit Mishra

Mudit Mahajan

# DIFFICULTY:

Simple

# PROBLEM:

Alice and Bob are playing a game. Bob has a number *n*.

Bob challenges Alice to obtain another number *s* by adding some number

*t* to *n*. But the number *t* can only comprise of digits of the number

*n* (there can be no leading zeros).

In other words, Alice will win the game if she can find a number *t*

that is obtained by reordering the digits (the rearrangement can be

equal to the initial number) of the initial number *n* such that *t* +

*n* = *s*.

If Alice can find such the number, then she wins the game and you should

print “Alice”, otherwise Bob wins the game and you should print “Bob”

(without quotes).

# EXPLANATION:

We need to find if the difference between *s* and *n* is a permutation

of the digits of number *n*.

There are numerous ways to solve this problem, but the easiest way would

be to convert the given number *n* and *t*(*s* - *n*) into strings, then

sort the strings.

If the sorted strings are equal then, Alice can find the required number

otherwise she cannot.

# SOLUTIONS:

## Setter's Solution

```
#include<bits/stdc++.h>
using namespace std;
int main()
{
ll number, target, temp;
cin >> number >> target;
temp = target - number;
string num, tem;
num = to_string(number);
tem = to_string(temp);
sort(num.begin(), num.end());
sort(tem.begin(), tem.end());
if(num == tem)
{
cout << "Alice" << endl;
}
else
{
cout << "Bob" << endl;
}
return 0;
}
```

# Postman and the Letters

**Author:** Arpit Mishra

Akshat Agrawal

# DIFFICULTY:

Easy

# PROBLEM:

There are n towns (numbered 1 through n). Each town consists of

houses, i-th town having a_i houses (numbered 1 through a_i).

Letters are to be delivered by a postman. Sometimes instead of writing

specific town and house number on letter’s envelope, only a house number

among all houses of all n towns is written. Assume all houses are

numbered from 1 to a_1 + a_2 + ... + a_n.

Given k letters with house number h_i, find the particular town and

house of that town where postman should deliver the letter.

# EXPLANATION:

We should use that the letter queries are given in increasing order of

house numbers. We will store in a variable sum the number of houses in

already considered towns (this variable should have 64-bit type) and in

a variable idx we will store the minimum number of town where the

house from the current letter possibly is.

We will iterate through the letters. Let the current letter should be

delivered to the house h. While sum + a_{idx} < h, we increase sum

by a_{idx} and increase idx by one. So, we got the town number where

house h is. It only remains to print two integers: idx (the town

number) and h−sum (the house number in this town).

# SOLUTIONS:

## Setter's Solution

```
#include <bits/stdc++.h>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin >> t;
while (t--)
{
int n, k;
cin >> n >> k;
long long a[n];
for (int i = 0; i < n; i++)
cin >> a[i];
long long h[k];
for (int i = 0; i < k; i++)
cin >> h[i];
long long sum = 0;
int idx = 0;
for (int i = 0; i < k; i++)
{
while (sum + a[idx] < h[i])
{
sum += a[idx];
idx++;
}
cout << idx + 1 << " " << h[i] - sum << "\n";
}
}
return 0;
}
```

# Common Factors

**Author:** Arpit Mishra

Akshat Agrawal

# DIFFICULTY:

Easy

# PROBLEM:

You are given an array A consisting of N integers. Find the number

of positive integers k such that k is a factor of every number in

the array.

# EXPLANATION:

Let g=gcd(A_1,A_2,...,A_N) is the greatest common divisor of all

elements of the array. You can find it by Euclidean algorithm or some

standard library functions. Then the answer is just the number of

divisors of g.

# SOLUTIONS:

## Setter's Solution

```
#include <bits/stdc++.h>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin >> t;
while (t--)
{
int n;
cin >> n;
long long g = 0;
for (int i = 0; i < n; i++)
{
long long a;
cin >> a;
g = __gcd(g, a);
}
int ans = 0;
for (long long i = 1; i * i <= g; i++)
{
if (g % i == 0)
{
ans++;
if (i != g / i)
ans++;
}
}
cout << ans << "\n";
}
return 0;
}
```

# Resistors

**Author:** Arpit Mishra

Akshat Agrawal

# DIFFICULTY:

Easy-Medium

# PROBLEM:

Max is building a machine. He requires a resistor of a certain

resistance value.

There are infinite number of resistors with resistance equal to 1. You

can combine several of these resistors in series and/or parallel.

Max needs a resistor with a resistance equal to \frac{A}{B}. Find the

minimum number of resistors required to get desired resistance.

# EXPLANATION:

If a fraction \frac{A}{B} can be obtained with k resistors, then it

is simple to calculate that we can obtain fractions \frac{A+B}{B}(by

adding one resistor in series) and \frac{A}{A+B}(by adding one

resistor in parallel) with k + 1 resistors.

\frac{A}{B} could be obtained by 1 + resistors required to create

\frac{A-B}{B} resistance assuming A>B and if b>a,\frac{A}{B}

could be obtained by 1 + resistors required to create \frac{A}{B-A}.

Assuming A>B so resistorRequired(A,B) = 1 + resistorRequired(A-B,B).

resistorReqiored(A-B,B) = 1 + resistorRequired(A-2*B,B) …
resistorRequired(A-(q-1) B,B) = 1 + resistorRequired(A-qB,B) let say r
= A-q*B == A%B now at this point, one resistance needs to be connected

in parallel to the \frac{B}{r} resistance. So again problem becomes

calculating the requiredResistance(B,r) similar to above problem, which

is similar to the gcd problem(gcd(a,b) = gcd(a-b,b)). So adding one

resistor means performing one operation backwards in Euclidean

algorithm. That means that the answer is equal to the number of steps in

standard Euclidean algorithm.

# SOLUTIONS:

## Setter's Solution

```
#include <iostream.h>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin >> t;
while (t--)
{
long long a, b, r;
cin >> a >> b;
long long ans = 0;
if (a < b)
swap(a, b);
while (1)
{
ans += a / b;
r = a % b;
if (r == 0)
break;
a = b;
b = r;
}
cout << ans << "\n";
}
return 0;
}
```