 Prize equalizer:

Practice

Author: Arpit Mishra

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:

Practice

Author: Arpit Mishra
Mudit Mahajan

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;
}
}

Practice

Author: Arpit Mishra
Mudit Mahajan

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

Practice

Author: Arpit Mishra
Akshat Agrawal

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

Practice

Author: Arpit Mishra
Akshat Agrawal

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

Practice

Author: Arpit Mishra
Akshat Agrawal

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
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-2B,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;
}