Codeforces Round 949 (Div. 2 ABCD) 视频讲解

A. Turtle and Piggy Are Playing a Game

Problem Statement

Turtle and Piggy are playing a number game.

First, Turtle will choose an integer $x$, such that $l\le x\le r$, where $l,r$ are given. It’s also guaranteed that $2l\le r$.

Then, Piggy will keep doing the following operation until $x$ becomes $1$:

• Choose an integer $p$ such that $p\ge 2$ and $p\mid x$ (i.e. $x$ is a multiple of $p$).
• Set $x$ to $\frac{x}{p}$, and the score will increase by $1$.

The score is initially $0$. Both Turtle and Piggy want to maximize the score. Please help them to calculate the maximum score.

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1\le t\le 10^4$). The description of the test cases follows.

The first line of each test case contains two integers $l,r$ ($1\le l\le r\le 10^9,2l\le r$) — The range where Turtle can choose the integer from.

Output

For each test case, output a single integer — the maximum score.

Example

Example

input
5
2 4
3 6
2 15
6 22
114514 1919810

output
2
2
3
4
20

Note

In the first test case, Turtle can choose an integer $x$, such that $2\le x\le 4$. He can choose $x=4$. Then Piggy can choose $p=2$ for $2$ times. After that, $x$ will become $1$, and the score will be $2$, which is maximized.

In the second test case, Turtle can choose an integer $3\le x\le 6$. He can choose $x=6$. Then Piggy can choose $p=2$, then choose $p=3$. After that, $x$ will become $1$, and the score will be $2$, which is maximum.

In the third test case, Turtle can choose $x=12$.

In the fourth test case, Turtle can choose $x=16$.

Solution

具体见文后视频。

---

Code

#include <bits/stdc++.h>
#define fi first
#define se second
#define int long long

using namespace std;

typedef pair<int, int> PII;
typedef long long LL;

void solve() {
	int l, r;
	cin >> l >> r;

	int x = 0;
	while ((1ll << x) <= r) x ++;
	x --;

	cout << x << endl;
}

signed main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(0);

	int dt;
	
	cin >> dt;

	while (dt --)
		solve();

	return 0;
}

---

B. Turtle and an Infinite Sequence

Problem Statement

There is a sequence $a_0,a_1,a_2,\dots$ of infinite length. Initially $a_i=i$ for every non-negative integer $i$.

After every second, each element of the sequence will simultaneously change. $a_i$ will change to $a_{i-1}\mid a_i\mid a_{i+1}$ for every positive integer $i$. $a_0$ will change to $a_0\mid a_1$. Here, $|$ denotes bitwise OR.

Turtle is asked to find the value of $a_n$ after $m$ seconds. In particular, if $m=0$, then he needs to find the initial value of $a_n$. He is tired of calculating so many values, so please help him!

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1\le t\le 10^4$). The description of the test cases follows.

The first line of each test case contains two integers $n,m$ ($0\le n,m\le 10^9$).

Output

For each test case, output a single integer — the value of $a_n$ after $m$ seconds.

Example

Example

input
9
0 0
0 1
0 2
1 0
5 2
10 1
20 3
1145 14
19198 10

output
0
1
3
1
7
11
23
1279
19455

Note

After $1$ second, $[a_0,a_1,a_2,a_3,a_4,a_5]$ will become $[1,3,3,7,7,7]$.

After $2$ seconds, $[a_0,a_1,a_2,a_3,a_4,a_5]$ will become $[3,3,7,7,7,7]$.

Solution

具体见文后视频。

---

Code

#include <bits/stdc++.h>
#define fi first
#define se second
#define int long long

using namespace std;

typedef pair<int, int> PII;
typedef long long LL;

void solve() {
	int n, m;
	cin >> n >> m;

	int l = max(0ll, n - m), r = n + m;
	if (l == r) cout << l << endl;
	for (int i = 30; i >= 0; i --)
		if ((r >> i & 1) && !(l >> i & 1)) {
			cout << (l | ((1ll << i + 1) - 1)) << endl;
			return;
		}
}

signed main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(0);

	int dt;
	
	cin >> dt;

	while (dt --)
		solve();

	return 0;
}

---

C. Turtle and an Incomplete Sequence

Problem Statement

Turtle was playing with a sequence $a_1,a_2,\dots ,a_n$ consisting of positive integers. Unfortunately, some of the integers went missing while playing.

Now the sequence becomes incomplete. There may exist an arbitrary number of indices $i$ such that $a_i$ becomes $-1$. Let the new sequence be $a^{\prime }$.

Turtle is sad. But Turtle remembers that for every integer $i$ from $1$ to $n-1$, either $a_i=\lfloor \frac{a_{i+1}}{2}\rfloor$ or $a_{i+1}=\lfloor \frac{a_i}{2}\rfloor$ holds for the original sequence $a$.

Turtle wants you to help him complete the sequence. But sometimes Turtle makes mistakes, so you need to tell him if you can’t complete the sequence.

Formally, you need to find another sequence $b_1,b_2,\dots ,b_n$ consisting of positive integers such that:

• For every integer $i$ from $1$ to $n$, if $a_i^{\prime }\ne -1$, then $b_i=a_i^{\prime }$.
• For every integer $i$ from $1$ to $n-1$, either $b_i=\lfloor \frac{b_{i+1}}{2}\rfloor$ or $b_{i+1}=\lfloor \frac{b_i}{2}\rfloor$ holds.
• For every integer $i$ from $1$ to $n$, $1\le b_i\le 10^9$.

If there is no sequence $b_1,b_2,\dots ,b_n$ that satisfies all of the conditions above, you need to report $-1$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1\le t\le 10^5$). The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($2\le n\le 2\cdot 10^5$) — the length of the sequence.

The second line of each test case contains $n$ integers $a_1^{\prime },a_2^{\prime },\dots ,a_n^{\prime }$ ($a_i^{\prime }=-1$ or $1\le a_i^{\prime }\le 10^8$) — the elements of the sequence $a^{\prime }$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot 10^5$.

Output

For each test case, if there is no sequence $b_1,b_2,\dots ,b_n$ that satisfies all of the conditions, output a single integer $-1$.

Otherwise, output $n$ integers $b_1,b_2,\dots ,b_n$ — the elements of the sequence $b_1,b_2,\dots ,b_n$ you find. The sequence should satisfy that $1\le b_i\le 10^9$ for every integer $i$ from $1$ to $n$. If there are multiple answers, print any of them.

Example

input
9
8
-1 -1 -1 2 -1 -1 1 -1
4
-1 -1 -1 -1
6
3 -1 -1 -1 9 -1
4
-1 5 -1 6
4
2 -1 -1 3
4
1 2 3 4
2
4 2
5
-1 3 -1 3 6
13
-1 -1 3 -1 -1 -1 -1 7 -1 -1 3 -1 -1

output
4 9 4 2 4 2 1 2
7 3 6 13
3 1 2 4 9 18
-1
-1
-1
4 2
6 3 1 3 6
3 1 3 1 3 7 3 7 3 1 3 1 3

Note

In the first test case, $[4,2,1,2,1,2,1,3]$ can also be the answer, while $[4,2,5,10,5,2,1,3]$ and $[4,2,1,2,1,2,1,4]$ cannot.

In the second test case, $[1,2,5,2]$ can also be the answer.

From the fourth to the sixth test cases, it can be shown that there is no answer, so you should output $-1$.

Solution

具体见文后视频。

---

Code

#include <bits/stdc++.h>
#define fi first
#define se second
#define int long long

using namespace std;

typedef pair<int, int> PII;
typedef long long LL;

void solve() {
	int n;
	cin >> n;
	std::vector<int> a(n + 1), b(n + 1, -1);

	bool cs = 1;
	for (int i = 1; i <= n; i ++) cin >> a[i], cs &= (a[i] == -1);

	if (cs) {
		for (int i = 1, j = 1; i <= n; i ++, j ^= 1)
			if (j) cout << 1 << " ";
			else cout << 2 << " ";
		cout << endl;
		return;
	}

	int lst = -1, pos, cnt = 0;
	for (int i = 1; i <= n; i ++)
		if (a[i] != -1) {
			if (lst != -1) {
				std::vector<int> avl;
				int tmp = lst;
				while (tmp) avl.emplace_back(tmp), tmp /= 2;
				bool flg = 0;
				for (int j = 0; j < avl.size(); j ++) {
					for (int x = 0; avl[j] * (1ll << x) <= a[i]; x ++) {
						tmp = a[i] - avl[j] * (1ll << x);
						if (tmp >= (1ll << x) || x + j > i - pos || (i - pos - x - j) % 2 != 0) continue;
						for (int k = pos, v = lst; k <= pos + j; k ++, v /= 2)
							b[k] = v;
						for (int k = pos + j + 1; k <= i - x; k += 2)
							b[k] = avl[j] * 2, b[k + 1] = avl[j];
						for (int k = i - x + 1, v = x - 1; k <= i; k ++, v --)
							if (tmp >> v & 1) b[k] = b[k - 1] * 2 + 1;
							else b[k] = b[k - 1] * 2;
						flg = 1;
						break;
					}
					if (flg) break;
				}
			}
			lst = a[i], pos = i, cnt ++;
		}

	if (cnt == 1) {
		for (int i = 1; i <= n; i ++)
			if (a[i] != -1)
				b[i] = a[i];
	}

	for (int i = 1; i <= n; i ++)
		if (a[i] != -1) {
			for (int j = i - 1, k = 1; j >= 1; j --, k ^= 1)
				if (k) b[j] = a[i] * 2;
				else b[j] = a[i];
			break;
		}

	for (int i = n; i >= 1; i --)
		if (a[i] != -1) {
			for (int j = i + 1, k = 1; j <= n; j ++, k ^= 1)
				if (k) b[j] = a[i] * 2;
				else b[j] = a[i];
			break;
		}
	for (int i = 1; i < n; i ++)
		if (b[i] <= 0 || b[i] / 2 != b[i + 1] && b[i + 1] / 2 != b[i]) {
			cout << -1 << endl;
			return;
		}

	for (int i = 1; i <= n; i ++)
		cout << b[i] << " ";
	cout << endl;
}

signed main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(0);

	int dt;
	
	cin >> dt;

	while (dt --)
		solve();

	return 0;
}

---

D. Turtle and Multiplication

Problem Statement

Turtle just learned how to multiply two integers in his math class, and he was very excited.

Then Piggy gave him an integer $n$, and asked him to construct a sequence $a_1,a_2,\dots ,a_n$ consisting of integers which satisfied the following conditions:

• For all $1\le i\le n$, $1\le a_i\le 3\cdot 10^5$.
• For all $1\le i<j\le n-1$, $a_i\cdot a_{i+1}\ne a_j\cdot a_{j+1}$.

Of all such sequences, Piggy asked Turtle to find the one with the minimum number of distinct elements.

Turtle definitely could not solve the problem, so please help him!

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1\le t\le 10^4$). The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($2\le n\le 10^6$) — the length of the sequence $a$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^6$.

Output

For each test case, output $n$ integers $a_1,a_2,\dots ,a_n$ — the elements of the sequence $a$.

If there are multiple answers, print any of them.

Example

input
3
2
3
4

output
114514 114514
1 2 2
3 3 4 4

Note

In the third test case, $a=[3,4,2,6]$ violates the second condition since $a_1\cdot a_2=a_3\cdot a_4$. $a=[2,3,4,4]$ satisfy the conditions but its number of distinct elements isn’t minimum.

Solution

具体见文后视频。

Code

#include <bits/stdc++.h>
#define fi first
#define se second
#define int long long

using namespace std;

typedef pair<int, int> PII;
typedef long long LL;

const int N = 4e6 + 10;

int n;
int h[N], e[N], ne[N], idx, vis[N];
std::vector<int> path, prm;
vector<int> Prime(int n) {
	std::vector<int> st(n + 1, 0), prm;
	for (int i = 2; i <= n; i ++) {
		if (!st[i]) prm.emplace_back(i);
		for (int j = 0; prm[j] * i <= n; j ++) {
			st[prm[j] * i] = true;
			if (i % prm[j] == 0) break;
		}
	}
	return prm;
}
void dfs(int u) {
	for (int &i = h[u]; ~i;) 
		if (!vis[i]) {
			int j = e[i];
			vis[i] = vis[i ^ 1] = 1, i = ne[i], dfs(j);
		} else
			i = ne[i];
	path.emplace_back(u);
}
void add(int a, int b) {
	e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

void solve() {
	cin >> n;

	int l = 1, r = n;
	while (l < r) {
		int mid = l + r >> 1;
		if ((mid & 1) && mid * (mid + 1) / 2 >= n - 1) r = mid;
		else if ((mid % 2 == 0) && mid * mid / 2 + 1 >= n - 1) r = mid;
		else l = mid + 1;
	}

	path.clear();
	for (int i = 0; i < r; i ++)
		for (int j = i; j < r; j ++)
			if ((r & 1) || j != i + 1 || i % 2 == 0)
				add(i, j), add(j, i);
	dfs(0), reverse(path.begin(), path.end());

	for (int i = 0; i < n; i ++)
		cout << prm[path[i]] << " ";
	cout << endl;
	for (int i = 0; i < r; i ++)
		h[i] = -1;
	for (int i = 0; i < idx; i ++) vis[i] = false;
	idx = 0;
}

signed main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(0);

	prm = Prime(100000);
	memset(h, -1, sizeof h);
	
	int dt;
	cin >> dt;

	while (dt -- )
		solve();

	return 0;
}

---

---

视频讲解

---

最后祝大家早日