算法日志 - Code | Value's Blog = 繁華落盡似水流年 = 寄予厚望还请善待

# 1759D - Make It Round

贝兰迪亚发生了通货膨胀，因此商店需要改变商品价格。

给出了商品 $n$ 的当前价格。允许将商品价格提高 $k$ 倍，其中 $1 \le k \le m$ ，k 为整数。输出该商品最可能的新价格。也就是最后有最多零的价格。

例如，数字 481000 比数字 1000010 更圆 (481000 末尾有三个 0，而 1000010 末尾只有一个 0)。

如果有几种可能的变式，则输出新价格最大的变式。

如果不可能得到更圆的价格，则输出 $n \cdot m$ (即最大可能价格)。

输入

第一行包含一个整数 $t$ ( $1 \le t \le 10^4$ ) -- 测试中的测试用例数。

每个测试用例包含一行。

这一行包含两个整数： $n$ 和 $m$ ( $1 \le n, m \le 10^9$ )。其中， $n$ 是商品的旧价格，而数字 $m$ 表示商品价格 $n$ 的增长不能超过 $m$ 倍。

输出

针对每个测试用例，另起一行输出形式为 $n \cdot k$ ( $1 \le k \le m$ , $k$ - 整数)。

如果存在多个可能的变量，则输出新价格 (值 $n \cdot k$ ) 最大的变量。

如果不可能得到更圆整的价格，则输出 $n \cdot m$ (即最大可能价格)。

样例

Input
10
6 11
5 43
13 5
4 16
10050 12345
2 6
4 30
25 10
2 81
1 7
Output
60
200
65
60
120600000
10
100
200
100
7

Note

第一种情况是 $n = 6$ ， $m = 11$ 。我们不能得到末尾有两个 0 或更多 0 的数字，因为我们需要把价格提高 $50$ 倍，而不是 $50 \gt m = 11$ 。 $10$ 的最大价格倍数是 $6 \cdot 10 = 60$ 。

第二种情况是 $n = 5$ ， $m = 43$ 。 $100$ 的最大价格倍数是 $5 \cdot 40 = 200$ 。

第三种情况是 $n = 13$ 、 $m = 5$ 。所有可能的新价格都不会以 $0$ 结尾，那么应该输出 $n \cdot m = 65$ 。

在第四种情况下，应将价格提高 $15$ 倍。

在第五种情况下，应将价格提高 $12000$ 倍。

AC Code

	#include <iostream>
	#include <cstring>
	#include <cstdio>
	#include <algorithm>
	#include <vector>
	#include <map>
	#include <set>
	#include <queue>
	#include <cmath>
	#include <numeric>
	#define rint register int
	#define ull unsigned long long
	#pragma GCC optimize(3,"Ofast","inline")
	using namespace std;
	using ll = long long;
	constexpr int N = 3e5 + 10;
	typedef pair<int, int> pii;
	pii decompose(int x){
	pii cur = {0, 0};
	while(x != 0 && x % 2 == 0) x /= 2, cur.first ++ ;
	while(x != 0 && x % 5 == 0) x /= 5, cur.second ++ ;
	return cur;
	}
	void solve(){
	int n, k; cin >> n >> k;
	pii t1 = decompose(n);
	ll u = 1;
	if(max(t1.first, t1.second) == 0){
	while(u * 10 <= k) u *= 10;
	u = k / u * u;
	}else{
	if(t1.first <= t1.second){
	int diff = t1.second - t1.first;
	for(int i = 0; i < diff && u * 2 <= k; i ++ ) u *= 2;
	while(u * 10 <= k) u *= 10;
	u = k / u * u;
	}else{
	int diff = t1.first - t1.second;
	for(int i = 0; i < diff && u * 5 <= k; i ++ ) u *= 5;
	while(u * 10 <= k) u *= 10;
	u = k / u * u;
	}
	}
	cout << u * n << endl;
	}
	int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int T; cin >> T;
	while(T -- ) solve();
	return 0;
	}

# 991C - Candies

time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

After passing a test, Vasya got himself a box of $n$ candies. He decided to eat an equal amount of candies each morning until there are no more candies. However, Petya also noticed the box and decided to get some candies for himself.

This means the process of eating candies is the following: in the beginning Vasya chooses a single integer $k$ , same for all days. After that, in the morning he eats $k$ candies from the box (if there are less than $k$ candies in the box, he eats them all), then in the evening Petya eats $10\%$ of the candies remaining in the box. If there are still candies left in the box, the process repeats — next day Vasya eats $k$ candies again, and Petya — $10\%$ of the candies left in a box, and so on.

If the amount of candies in the box is not divisible by $10$ , Petya rounds the amount he takes from the box down. For example, if there were $97$ candies in the box, Petya would eat only $9$ of them. In particular, if there are less than $10$ candies in a box, Petya won't eat any at all.

Your task is to find out the minimal amount of $k$ that can be chosen by Vasya so that he would eat at least half of the $n$ candies he initially got. Note that the number $k$ must be integer.

Input

The first line contains a single integer $n$ ( $1 \leq n \leq 10^{18}$ ) — the initial amount of candies in the box.

Output

Output a single integer — the minimal amount of $k$ that would allow Vasya to eat at least half of candies he got.

Example

Input
68
Output
3

Note

In the sample, the amount of candies, with $k=3$ , would change in the following way (Vasya eats first):

68→65→59→56→51→48→44→41→37→34→31→28→26→23→21→18→17→14→13→10→9→6→6→3→3→068→65→59→56→51→48→44→41→37→34→31→28→26→23→21→18→17→14→13→10→9→6→6→3→3→0.

In total, Vasya would eat $39$ candies, while Petya — $29$ .

AC Code

	#include <iostream>
	#include <cstring>
	#include <cstdio>
	#include <algorithm>
	#include <vector>
	#include <map>
	#include <set>
	#include <queue>
	#include <cmath>
	#include <numeric>
	#include <unordered_map>
	#include <unordered_set>
	#define rint register int
	#define ull unsigned long long
	#pragma GCC optimize(3,"Ofast","inline")
	using namespace std;
	using ll = long long;
	constexpr int N = 1e5 + 10;
	ll n;
	bool check(ll x){
	ll sum1 = 0, sum2 = 0;
	ll all = n;
	while(all != 0){
	if(all <= x) sum1 = sum1 + all, all = 0;
	else sum1 = sum1 + x, all = all - x;

	if(all >= 10) sum2 = sum2 + all / 10, all = all - all / 10;
	if(sum1 >= (n + 1 / 2)) return true;
	}
	return sum1 >= (n + 1) / 2;
	}
	int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cin >> n;
	ll l = 1, r = n;
	while(l < r){
	ll mid = l + r >> 1;
	if(check(mid)) r = mid;
	else l = mid + 1;
	}
	cout << l << endl;
	return 0;
	}

# 1714D - Color with Occurrences

You are given some text $t$ and a set of $n$ strings $s_1, s_2, \dots, s_n$ .

In one step, you can choose any occurrence of any string $s_i$ in the text $t$ and color the corresponding characters of the text in red. For example, if $t=\texttt{bababa}$ and $s_1=\texttt{ba}$ , $s_2=\texttt{aba}$ , you can get $t=\color{red}{\texttt{ba}}\texttt{baba}$ , $t=\texttt{b}\color{red}{\texttt{aba}}\texttt{ba}$ or $t=\texttt{bab}\color{red}{\texttt{aba}}$ in one step.

You want to color all the letters of the text $t$ in red. When you color a letter in red again, it stays red.

In the example above, three steps are enough:

Let's color $t[2 \dots 4]=s_2=\texttt{aba}$ in red, we get $t=\texttt{b}\color{red}{\texttt{aba}}\texttt{ba}$ ;
Let's color $t[1 \dots 2]=s_1=\texttt{ba}$ in red, we get $t=\color{red}{\texttt{baba}}\texttt{ba}$ ;
Let's color $t[4 \dots 6]=s_2=\texttt{aba}$ in red, we get $t=\color{red}{\texttt{bababa}}$ .

Each string $s_i$ can be applied any number of times (or not at all). Occurrences for coloring can intersect arbitrarily.

Determine the minimum number of steps needed to color all letters $t$ in red and how to do it. If it is impossible to color all letters of the text $t$ in red, output -1.

Input

The first line of the input contains an integer $q$ ( $1 \le q \le 100$ ) —the number of test cases in the test.

The descriptions of the test cases follow.

The first line of each test case contains the text $t$ ( $1 \le |t| \le 100$ ), consisting only of lowercase Latin letters, where $|t|$ is the length of the text $t$ .

The second line of each test case contains a single integer $n$ ( $1 \le n \le 10$ ) — the number of strings in the set.

This is followed by $n$ lines, each containing a string $s_i$ ( $1 \le |s_i| \le 10$ ) consisting only of lowercase Latin letters, where $|s_i|$ — the length of string $s_i$ .

Output

For each test case, print the answer on a separate line.

If it is impossible to color all the letters of the text in red, print a single line containing the number -1.

Otherwise, on the first line, print the number $m$ — the minimum number of steps it will take to turn all the letters $t$ red.

Then in the next $m$ lines print pairs of indices: $w_j$ and $p_j$ ( $1 \le j \le m$ ), which denote that the string with index $w_j$ was used as a substring to cover the occurrences starting in the text $t$ from position $p_j$ . The pairs can be output in any order.

If there are several answers, output any of them.

Example

Input
6
bababa
2
ba
aba
caba
2
bac
acab
abacabaca
3
aba
bac
aca
baca
3
a
c
b
codeforces
4
def
code
efo
forces
aaaabbbbcccceeee
4
eeee
cccc
aaaa
bbbb
Output
3
2 2
1 1
2 4
-1
4
1 1
2 6
3 3
3 7
4
3 1
1 2
2 3
1 4
2
4 5
2 1
4
3 1
4 5
2 9
1 13

Note

The first test case is explained in the problem statement.

In the second test case, it is impossible to color all the letters of the text in red.

AC Code

	#include <iostream>
	#include <cstring>
	#include <cstdio>
	#include <algorithm>
	#include <vector>
	#include <map>
	#include <set>
	#include <queue>
	#include <cmath>
	#include <numeric>
	#define rint register int
	#define ull unsigned long long
	#pragma GCC optimize(3,"Ofast","inline")
	using namespace std;
	using ll = long long;
	constexpr int N = 10;
	string s[N];
	int f[110];
	typedef pair<int, int> pii;
	pii pre[110];
	void solve(){
	string t; cin >> t;
	t = " " + t;
	int n; cin >> n;
	for(int i = 0; i < n; i ++ ) cin >> s[i];
	memset(f, 0x3f, sizeof f);
	f[0] = 0;
	int length = t.size();
	for(int i = 1; i < length; i ++){
	for(int j = 0; j < n; j ++ ){
	int m = s[j].size();
	if(m > i) continue;
	int minv = 0x3f3f3f3f;
	int index = -1;
	bool flag = true;
	int start = i + 1 - m;
	for(int k = 0; k < m; k ++ ){
	if(t[start + k] != s[j][k]) flag = false;
	else{
	if(minv >= f[start + k - 1]) minv = f[start + k - 1], index = start + k - 1;
	}
	}
	if(flag && f[i] > minv + 1){
	f[i] = minv + 1;
	pre[i] = {j, index};
	}
	}
	}
	if(f[length - 1] >= 0x3f3f3f3f) cout << -1 << endl;
	else{
	int res = f[length - 1];
	cout << res << endl;
	int index = length - 1;
	for(int i = 0; i < res; i ++ ){
	cout << pre[index].first + 1 << ' ' << index + 1 - s[pre[index].first].size() << endl;
	index = pre[index].second;
	}
	}
	}
	int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int T; cin >> T;
	while(T -- ) solve();
	return 0;
	}

# 938D - Buy a Ticket

Musicians of a popular band "Flayer" have announced that they are going to "make their exit" with a world tour. Of course, they will visit Berland as well.

There are n cities in Berland. People can travel between cities using two-directional train routes; there are exactly m routes, i-th route can be used to go from city $v_{i}$ to city $u_{i}$ (and from $u_{i}$ to $v_{i}$ ), and it costs $w_{i}$ coins to use this route.

Each city will be visited by "Flayer", and the cost of the concert ticket in i-th city is $a_{i}$ coins.

You have friends in every city of Berland, and they, knowing about your programming skills, asked you to calculate the minimum possible number of coins they have to pay to visit the concert. For every city i you have to compute the minimum number of coins a person from city i has to spend to travel to some city j (or possibly stay in city i), attend a concert there, and return to city i (if j ≠ i).

Formally, for every $i\in[1, n]$ you have to calculate $\min _{j\in[1,n]} 2 d(i, j)+a_{j}$ , where d(i, j) is the minimum number of coins you have to spend to travel from city i to city j. If there is no way to reach city j from city i, then we consider d(i, j) to be infinitely large.

Input

The first line contains two integers n and m ( $2 ≤ n ≤ 2·10^{5}, 1 ≤ m ≤ 2·10^{5}$ ).

Then m lines follow, i-th contains three integers $v_{i}$ , $u_{i}$ and $w_{i}$ ( $1 ≤ v_{i}, u_{i}≤ n, v_{i}≠ u_{i}, 1 ≤ w_{i} ≤ 10^{12}$ ) denoting i-th train route. There are no multiple train routes connecting the same pair of cities, that is, for each (v, u) neither extra (v, u) nor (u, v) present in input.

The next line contains n integers $a_{1}, a_2, ... a_k (1 ≤ a_i ≤ 10^{12})$ — price to attend the concert in i-th city.

Output

Print n integers. i-th of them must be equal to the minimum number of coins a person from city i has to spend to travel to some city j (or possibly stay in city i), attend a concert there, and return to city i (if j ≠ i).

Example

Input
4 2
1 2 4
2 3 7
6 20 1 25
Output
6 14 1 25

Input
3 3
1 2 1
2 3 1
1 3 1
30 10 20
Output
12 10 12

AC Code

	#include <iostream>
	#include <cstring>
	#include <cstdio>
	#include <algorithm>
	#include <vector>
	#include <map>
	#include <set>
	#include <queue>
	#include <cmath>
	#include <numeric>
	#include <unordered_map>
	#include <unordered_set>
	#define rint register int
	#define ull unsigned long long
	#pragma GCC optimize(3,"Ofast","inline")
	using namespace std;
	using ll = long long;
	constexpr int N = 2e5 + 10, M = 6e5 + 10;;
	int h[N], e[M], ne[M];
	ll w[M], idx;
	ll dist[N];
	bool state[N];
	typedef pair<ll, int> pii;
	void add(int a, int b, ll c){
	e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx ++ ;
	}
	void heap_dijkstra(int st){
	memset(state, 0, sizeof state);
	memset(dist, 0x3f, sizeof dist);
	dist[st] = 0;
	priority_queue<pii, vector<pii>, greater<pii>> qu;
	qu.push({dist[st], st});
	while(!qu.empty()){
	auto cur= qu.top();
	qu.pop();
	if(state[cur.second]) continue;
	state[cur.second] = true;
	for(int i = h[cur.second]; ~i; i = ne[i]){
	int j = e[i];
	if(dist[j] > dist[cur.second] + w[i]){
	dist[j] = dist[cur.second] + w[i];
	qu.push({dist[j], j});
	}
	}
	}
	}
	int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int n, m; cin >> n >> m;
	memset(h, -1, sizeof h);
	while(m -- ){
	ll a, b, c; cin >> a >> b >> c;
	add(a, b, c * 2);
	add(b, a, c * 2);
	}
	for(int i = 1; i <= n; i ++ ){
	ll c; cin >> c;
	add(0, i, c);
	}
	heap_dijkstra(0);
	for(int i = 1; i <= n; i ++ ) cout << dist[i] << ' ';
	cout << endl;
	return 0;
	}

Algorithm

# 1759D - Make It Round

# 991C - Candies

# 1714D - Color with Occurrences

# 938D - Buy a Ticket

扩展欧几里得算法

组合数