[problem:668948A]↵
↵
<spoiler summary="Solution">↵
The square root of $x^2$ when $x$ is an integer is also an integer. We can use this and print $1^2, \ 2^2, \ 3^2, \dots, n^2$ ↵
</spoiler>↵
↵
↵
<spoiler summary="Code"> ↵
~~~~~ ↵
n = int(input())↵
for i in range(1, n + 1):↵
print(i * i, end = ' ')↵
~~~~~↵
</spoiler>↵
↵
[problem:668948B]↵
↵
<spoiler summary="Solution">↵
$A = a \cdot b \to a = \frac{A}{b}$↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```py↵
#include <bits/stdc++.h>↵
using namespace std;↵
int main() {↵
int A, b; cin >> A >> b;↵
cout << A / b;↵
}↵
```↵
</spoiler>↵
↵
[problem:668948C]↵
↵
<spoiler summary="Solution">↵
To find $y$ we can find the first prime factor of $x$ by checking each integer from $2$ to $\sqrt{x}$, and if there aren't any divisors of $x$ in this range, then the answer is $x$.↵
↵
Why this works?↵
$y$ shares exactly one prime factor with $x$ ( itself ), and the first divisor of any integer $\neq 1$ is a prime.↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```c++↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
↵
int main() {↵
int x; cin >> x;↵
↵
for (int i = 2; i * i <= x; i++) {↵
if (x % i == 0) {↵
cout << i << "\n";↵
return 0;↵
}↵
}↵
cout << x << "\n";↵
}↵
```↵
</spoiler>↵
↵
[problem:668948D]↵
↵
<spoiler summary="Solution">↵
We can express $x = l \cdot a + r \cdot b$ and $y = l \cdot b + r \cdot a$ then:↵
$$x + y = l \cdot ( a + b ) + r \cdot (a + b)$$↵
$$l + r = \frac{x + y}{a + b} = d$$↵
↵
$$x - y = l \cdot ( a - b ) - r \cdot ( a - b )$$↵
$$l - r = \frac{x - y}{a - b} = c$$↵
↵
$$r = \frac{d - c}{2}$$↵
$$l = \frac{d + c}{2}$$↵
↵
Then we have to check:↵
↵
- is $x + y$ divisible by $a + b$↵
- is $x - y$ divisible by $a - b$↵
- is $d + c$ divisible by $2$↵
- is $d - c$ divisible by $2$↵
- $l \ge 0$ and $r \ge 0$↵
↵
If all conditions are met, the answer is $l + r = d$. Otherwise, output $-1$.↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```c++↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
↵
int main() {↵
int t;↵
cin >> t;↵
while (t--) {↵
int x, y, a, b;↵
cin >> x >> y >> a >> b;↵
if (x > y) swap(x, y);↵
if (a > b) swap(a, b);↵
↵
if ((x + y) % (a + b) != 0 or↵
(a == b and (x % a != 0 or y % a != 0) or (y - x) % (b - a) != 0)) {↵
cout << "-1\n";↵
continue;↵
}↵
int c = (x + y) / (a + b);↵
int d = (y - x) / (b - a);↵
int l = (c + d) / 2;↵
int r = (c - d) / 2;↵
if (l < 0 or r < 0 or (c + d) % 2 == 1 or (c - d) % 2 == 1) {↵
cout << "-1\n";↵
continue;↵
}↵
cout << (x + y) / (a + b) << "\n";↵
}↵
}↵
```↵
</spoiler>↵
↵
[problem:668948E]↵
↵
<spoiler summary="Solution">↵
We can use a DP approach. Let $dp[i][j]$ mean if we consider a subset of the first $i$ coins what is the maximum number of different coin types we can use to make $j$. Then $dp[0][0] = 0$ and $dp[i][j] = -\infty$.↵
↵
For each type $i$ and amount $j$ we have two choices↵
↵
1. Dont use type $i$: $dp[i][j] = dp[i - 1][j]$↵
2. Use coin type $i$:↵
↵
- We need to use at least one coin of type $j$ so we subtract $d[i]$ from $j$.↵
- Then $dp[i][j] = \max (dp[i - 1][j - d[i]] + 1, \ dp[i][j - d[i]])$.↵
↵
So $dp[i][j] = \max (dp[i - 1][j], \ dp[i - 1][j - d[i]] + 1, \ dp[i][j - d[i]])$. The answer is $dp[n][x]$ if it isn't $-\infty$ or $-1$ else.↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```c++↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
↵
#define vec vector↵
↵
int main()↵
{↵
int n, x;↵
cin >> n >> x;↵
↵
vec<vec<int>> dp(n + 1, vec<int>(x + 1, INT_MIN));↵
vec<int> d(n);↵
for (int i = 0; i < n; i++)↵
cin >> d[i];↵
dp[0][0] = 0;↵
for (int i = 1; i <= n; i++)↵
{↵
for (int j = d[i - 1]; j <= x; j++)↵
{↵
dp[i][j] = max(dp[i - 1][j - d[i - 1]] + 1, dp[i][j - d[i - 1]]);↵
}↵
for (int j = 0; j <= x; j++)↵
dp[i][j] = max(dp[i][j], dp[i - 1][j]);↵
}↵
if (dp[n][x] < 0)↵
cout << -1 << "\n";↵
else↵
cout << dp[n][x] << "\n";↵
}↵
```↵
</spoiler>↵
↵
[problem:668948F]↵
↵
<spoiler summary="Solution">↵
Key Observation: If vertex $u$ meets $v$ at any point, it will always be equal to $v$ from that point onward (since the graph is functional — each vertex has exactly one outgoing edge). So if we simulate at least $n$ steps and check if they're equal, we'll know if they ever met.↵
↵
How to simulate at least $n$ steps fast?↵
We can use jump pointers to simulate $\ge n$ steps in O(1) time.↵
Let $jmp[v][k]$ = the vertex we reach after taking $2^k$ steps starting from $v$.↵
- Base case: $jmp[v][0] = a[v]$ (the direct neighbor of $v$)↵
- Recurrence: $jmp[v][k] = jmp[jmp[v][k-1]][k-1]$↵
This works because taking $2^k$ steps = taking $2^{k-1}$ steps, then taking another $2^{k-1}$ steps.↵
↵
To answer each query: Find the smallest $k$ such that $2^k \ge n$. Then check if $jmp[u][k]$ == $jmp[v][k]$. If yes, they will meet, otherwise, they will never meet.↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```c++↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
#define vec vector↵
↵
const int K = 20;↵
int main()↵
{↵
int n;↵
cin >> n;↵
vec<int> next(n);↵
vec<vec<int>> jmp(K, vec<int>(n));↵
↵
for (int i = 0; i < n; i++)↵
{↵
cin >> next[i];↵
jmp[0][i] = next[i] - 1;↵
}↵
↵
for (int k = 1; k < K; k++)↵
{↵
for (int i = 0; i < n; i++)↵
{↵
jmp[k][i] = jmp[k - 1][jmp[k - 1][i]];↵
}↵
}↵
↵
int q;↵
cin >> q;↵
while (q--)↵
{↵
int a, b;↵
cin >> a >> b;↵
a--;↵
b--;↵
if (jmp[K - 1][a] == jmp[K - 1][b])↵
{↵
cout << "YES\n";↵
}↵
else↵
{↵
cout << "NO\n";↵
}↵
}↵
}↵
```↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
The square root of $x^2$ when $x$ is an integer is also an integer. We can use this and print $1^2, \ 2^2, \ 3^2, \dots, n^2$ ↵
</spoiler>↵
↵
↵
<spoiler summary="Code"> ↵
~~~~~ ↵
n = int(input())↵
for i in range(1, n + 1):↵
print(i * i, end = ' ')↵
~~~~~↵
</spoiler>↵
↵
[problem:668948B]↵
↵
<spoiler summary="Solution">↵
$A = a \cdot b \to a = \frac{A}{b}$↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```py↵
#include <bits/stdc++.h>↵
using namespace std;↵
int main() {↵
int A, b; cin >> A >> b;↵
cout << A / b;↵
}↵
```↵
</spoiler>↵
↵
[problem:668948C]↵
↵
<spoiler summary="Solution">↵
To find $y$ we can find the first prime factor of $x$ by checking each integer from $2$ to $\sqrt{x}$, and if there aren't any divisors of $x$ in this range, then the answer is $x$.↵
↵
Why this works?↵
$y$ shares exactly one prime factor with $x$ ( itself ), and the first divisor of any integer $\neq 1$ is a prime.↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```c++↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
↵
int main() {↵
int x; cin >> x;↵
↵
for (int i = 2; i * i <= x; i++) {↵
if (x % i == 0) {↵
cout << i << "\n";↵
return 0;↵
}↵
}↵
cout << x << "\n";↵
}↵
```↵
</spoiler>↵
↵
[problem:668948D]↵
↵
<spoiler summary="Solution">↵
We can express $x = l \cdot a + r \cdot b$ and $y = l \cdot b + r \cdot a$ then:↵
$$x + y = l \cdot ( a + b ) + r \cdot (a + b)$$↵
$$l + r = \frac{x + y}{a + b} = d$$↵
↵
$$x - y = l \cdot ( a - b ) - r \cdot ( a - b )$$↵
$$l - r = \frac{x - y}{a - b} = c$$↵
↵
$$r = \frac{d - c}{2}$$↵
$$l = \frac{d + c}{2}$$↵
↵
Then we have to check:↵
↵
- is $x + y$ divisible by $a + b$↵
- is $x - y$ divisible by $a - b$↵
- is $d + c$ divisible by $2$↵
- is $d - c$ divisible by $2$↵
- $l \ge 0$ and $r \ge 0$↵
↵
If all conditions are met, the answer is $l + r = d$. Otherwise, output $-1$.↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```c++↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
↵
int main() {↵
int t;↵
cin >> t;↵
while (t--) {↵
int x, y, a, b;↵
cin >> x >> y >> a >> b;↵
if (x > y) swap(x, y);↵
if (a > b) swap(a, b);↵
↵
if ((x + y) % (a + b) != 0 or↵
(a == b and (x % a != 0 or y % a != 0) or (y - x) % (b - a) != 0)) {↵
cout << "-1\n";↵
continue;↵
}↵
int c = (x + y) / (a + b);↵
int d = (y - x) / (b - a);↵
int l = (c + d) / 2;↵
int r = (c - d) / 2;↵
if (l < 0 or r < 0 or (c + d) % 2 == 1 or (c - d) % 2 == 1) {↵
cout << "-1\n";↵
continue;↵
}↵
cout << (x + y) / (a + b) << "\n";↵
}↵
}↵
```↵
</spoiler>↵
↵
[problem:668948E]↵
↵
<spoiler summary="Solution">↵
We can use a DP approach. Let $dp[i][j]$ mean if we consider a subset of the first $i$ coins what is the maximum number of different coin types we can use to make $j$. Then $dp[0][0] = 0$ and $dp[i][j] = -\infty$.↵
↵
For each type $i$ and amount $j$ we have two choices↵
↵
1. Dont use type $i$: $dp[i][j] = dp[i - 1][j]$↵
2. Use coin type $i$:↵
↵
- We need to use at least one coin of type $j$ so we subtract $d[i]$ from $j$.↵
- Then $dp[i][j] = \max (dp[i - 1][j - d[i]] + 1, \ dp[i][j - d[i]])$.↵
↵
So $dp[i][j] = \max (dp[i - 1][j], \ dp[i - 1][j - d[i]] + 1, \ dp[i][j - d[i]])$. The answer is $dp[n][x]$ if it isn't $-\infty$ or $-1$ else.↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```c++↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
↵
#define vec vector↵
↵
int main()↵
{↵
int n, x;↵
cin >> n >> x;↵
↵
vec<vec<int>> dp(n + 1, vec<int>(x + 1, INT_MIN));↵
vec<int> d(n);↵
for (int i = 0; i < n; i++)↵
cin >> d[i];↵
dp[0][0] = 0;↵
for (int i = 1; i <= n; i++)↵
{↵
for (int j = d[i - 1]; j <= x; j++)↵
{↵
dp[i][j] = max(dp[i - 1][j - d[i - 1]] + 1, dp[i][j - d[i - 1]]);↵
}↵
for (int j = 0; j <= x; j++)↵
dp[i][j] = max(dp[i][j], dp[i - 1][j]);↵
}↵
if (dp[n][x] < 0)↵
cout << -1 << "\n";↵
else↵
cout << dp[n][x] << "\n";↵
}↵
```↵
</spoiler>↵
↵
[problem:668948F]↵
↵
<spoiler summary="Solution">↵
Key Observation: If vertex $u$ meets $v$ at any point, it will always be equal to $v$ from that point onward (since the graph is functional — each vertex has exactly one outgoing edge). So if we simulate at least $n$ steps and check if they're equal, we'll know if they ever met.↵
↵
How to simulate at least $n$ steps fast?↵
We can use jump pointers to simulate $\ge n$ steps in O(1) time.↵
Let $jmp[v][k]$ = the vertex we reach after taking $2^k$ steps starting from $v$.↵
- Base case: $jmp[v][0] = a[v]$ (the direct neighbor of $v$)↵
- Recurrence: $jmp[v][k] = jmp[jmp[v][k-1]][k-1]$↵
This works because taking $2^k$ steps = taking $2^{k-1}$ steps, then taking another $2^{k-1}$ steps.↵
↵
To answer each query: Find the smallest $k$ such that $2^k \ge n$. Then check if $jmp[u][k]$ == $jmp[v][k]$. If yes, they will meet, otherwise, they will never meet.↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```c++↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
#define vec vector↵
↵
const int K = 20;↵
int main()↵
{↵
int n;↵
cin >> n;↵
vec<int> next(n);↵
vec<vec<int>> jmp(K, vec<int>(n));↵
↵
for (int i = 0; i < n; i++)↵
{↵
cin >> next[i];↵
jmp[0][i] = next[i] - 1;↵
}↵
↵
for (int k = 1; k < K; k++)↵
{↵
for (int i = 0; i < n; i++)↵
{↵
jmp[k][i] = jmp[k - 1][jmp[k - 1][i]];↵
}↵
}↵
↵
int q;↵
cin >> q;↵
while (q--)↵
{↵
int a, b;↵
cin >> a >> b;↵
a--;↵
b--;↵
if (jmp[K - 1][a] == jmp[K - 1][b])↵
{↵
cout << "YES\n";↵
}↵
else↵
{↵
cout << "NO\n";↵
}↵
}↵
}↵
```↵
</spoiler>↵
↵
