The Shakuni Game
Author: artha6391
Tester: anushka_nagar
Editorialist: august_24
DIFFICULTY:
EASY
PREREQUISITES:
Prime Factorization
PROBLEM:
Given an integer N \geq 1, the following operations is performed until N becomes 1:
Choose an integer x \geq 1 that is divisible by N and divide N by x. If x is even, we get A points, else we get B points.
We need to find the maximum number of points achievable.
EXPLANATION:
Let us first do the prime factorization of N. Let the total sum of even powers be even and the total sum of odd powers be odd.
For example, if N = 180, then N = 2^2 * 3^2 * 5^1. Therefore, even = 2 and odd = 2+1 = 3.
Now the problem can be solved in various cases depending on A and B:
Case 1: A \geq 0 and B \geq 0
• In this case, since both A and B are non-negative, we want to divide N as many times as possible by both even and odd primes.
• Therefore, in this case, the answer will be even * A + odd * B
Case 2: A \leq 0 and B \leq 0
• In this case, since both A and B are not positive, we don’t want to divide N many times as this could reduce the cost. We want to get it done in one go i.e, divide N by N itself.
• Therefore, in this case, the answer will be A if N is even or else it will be B.
Case 3: A \geq 0 and B \leq 0
• In this case, we want to divide N by 2 as many times as possible. We also want to avoid dividing N by odd numbers.
• Suppose y is the maximum odd number divisible by N. If N is even, the first step we could do is divide N by 2 * y and then keep on dividing N by 2. Or else y = N and we need to divide N by N itself.
• Therefore, in this case, the answer will be even * A if N is even or else it will be B.
Case 4: A \leq 0 and B \geq 0
• In this case, we want to divide N by odd primes as many times as possible. We also want to avoid dividing N by even numbers.
• Suppose N is odd. Then we can divide N as many times as possible by odd primes. If N is even, we want to remove the even part in one operation itself. Then we can continue removing odd primes one by one.
• Therefore, in this case, the answer will be odd * B if N is odd or else it will be odd * B + A.
SOLUTIONS:
Setter’s Solution
#include <bits/stdc++.h>
using namespace std;
int main()
{
int tests;
cin >> tests;
while (tests–)
{
int n, a, b;
cin >> n >> a >> b;
int even = 0, odd = 0;
while (n % 2 == 0)
{
n /= 2;
even++;
}
for (int i = 3; i * i <= n; i++)
{
if (n % i == 0)
{
while (n % i == 0)
{
n /= i;
odd++;
}
}
}
if (n != 1)
odd++;
int ans = 0;
if (a >= 0 && b >= 0)
{
ans = even * a + odd * b;
}
else if (a <= 0 && b <= 0)
{
if (even)
ans = a;
else
ans = b;
}
else if (a >= 0 && b <= 0)
{
if (even)
ans = even * a;
else
ans = b;
}
else if (a <= 0 && b >= 0)
{
if (even)
ans = a + odd * b;
else
ans = odd * b;
}
cout << ans << endl;
}
}
Tester’s Solution
#include <bits/stdc++.h>
using namespace std;
int main()
{
int tests;
cin >> tests;
while (tests–)
{
int n, a, b;
cin >> n >> a >> b;
int even = 0, odd = 0;
while (n % 2 == 0)
{
n /= 2;
even++;
}
for (int i = 3; i * i <= n; i++)
{
if (n % i == 0)
{
while (n % i == 0)
{
n /= i;
odd++;
}
}
}
if (n != 1)
odd++;
int ans = 0;
if (a >= 0 && b >= 0)
{
ans = even * a + odd * b;
}
else if (a <= 0 && b <= 0)
{
if (even)
ans = a;
else
ans = b;
}
else if (a >= 0 && b <= 0)
{
if (even)
ans = even * a;
else
ans = b;
}
else if (a <= 0 && b >= 0)
{
if (even)
ans = a + odd * b;
else
ans = odd * b;
}
cout << ans << endl;
}
}
Editorialist’s Solution
#include <bits/stdc++.h>
using namespace std;
int main()
{
int tests;
cin >> tests;
while (tests–)
{
int n, a, b;
cin >> n >> a >> b;
int even = 0, odd = 0;
while (n % 2 == 0)
{
n /= 2;
even++;
}
for (int i = 3; i * i <= n; i++)
{
if (n % i == 0)
{
while (n % i == 0)
{
n /= i;
odd++;
}
}
}
if (n != 1)
odd++;
int ans = 0;
if (a >= 0 && b >= 0)
{
ans = even * a + odd * b;
}
else if (a <= 0 && b <= 0)
{
if (even)
ans = a;
else
ans = b;
}
else if (a >= 0 && b <= 0)
{
if (even)
ans = even * a;
else
ans = b;
}
else if (a <= 0 && b >= 0)
{
if (even)
ans = a + odd * b;
else
ans = odd * b;
}
cout << ans << endl;
}
}