Codeforces 1661B Getting Zero

題目

https://codeforces.com/contest/1661/problem/B

給你nn個數字，每個數字vv可以有兩種操作。

  • v:=(v+1)%32768v:=(v+1)\%32768
  • v:=(2×v)%32768v:=(2\times v)\%32768

其中%\%是取餘數的意思。

請你輸出對於每個數字，最少需要操作幾次才能把該數字變成0。

Solution

不難發現，每個數字需要操作的最多次數是1515次，為什麼呢？因為3276832768是22的1515次方，所以對於所有數字vv，v×215≡0(mod32768)v\times 2^{15}\equiv 0 (mod 32768)

然後我們就可以試著用dpdp來解這題了，令dp(i,j)dp(i,j)為目前數字為ii並且已經操作了jj次，然後要讓ii變成00的最少方法數是多少。

則dp(i,j)=min((dp((i+1)%32768,j+1),dp((i×2)%32678),j+1))+1dp(i,j) = min((dp((i+1)\% 32768,j+1),dp((i\times 2)\% 32678),j+1))+1

因為jj一定不會>15\gt 15，所以狀態數只有32768×1532768\times 15，足夠快去AC這道題目。

AC Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <bits/extc++.h>
#include <bits/stdc++.h>
/*
#pragma gcc optimize("ofast, unroll-loops, no-stack-protector, fast-math")
#pragma gcc target("abm, bmi, bmi2, mmx, sse, sse2, sse3, ssse3, sse4, popcnt, avx, avx2, fma, tune=native")
#pragma comment(linker, "/stack:200000000")
*/
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define int long long
#define double long double
#define pb push_back
#define sz(x) (int)(x).size()
#define all(v) begin(v),end(v)
#define debug(x) cerr<<#x<<" = "<<x<<'\n'
#define LINE cout<<"\n-----------------\n"
#define endl '\n'
#define VI vector<int>
#define F first
#define S second
#define MP(a,b) make_pair(a,b)
#define rep(i,m,n) for(int i = m;i<=n;++i)
#define res(i,m,n) for(int i = m;i>=n;--i)
#define gcd(a,b) __gcd(a,b)
#define lcm(a,b) a*b/gcd(a,b)
#define Case() int _;cin>>_;for(int Case = 1;Case<=_;++Case)
#define pii pair<int,int>
using namespace __gnu_cxx;
using namespace __gnu_pbds;
using namespace std;
template <typename K, typename cmp = less<K>, typename T = thin_heap_tag> using _heap = __gnu_pbds::priority_queue<K, cmp, T>;
template <typename K, typename M = null_type> using _hash = gp_hash_table<K, M>;
template <typename K, typename M = null_type, typename cmp = less<K>, typename T = rb_tree_tag> using _tree = tree<K, M, cmp, T, tree_order_statistics_node_update>;
template <typename K, typename M = null_type, typename cmp = less_equal<K>, typename T = rb_tree_tag> using _multitree = tree<K, M, cmp, T, tree_order_statistics_node_update>;
const int N = 1e6+5,L = 20,mod = 32768,inf = 5e15+5;
const double eps = 1e-7;
int ans = inf;
vector<int>vis(mod);
int dp[32768][25] = {};
int f(int n,int dis = 0){
	if(dis>20)return inf;
	if(n==0)return 0;
	if(dp[n][dis])return dp[n][dis];
	return dp[n][dis] = min(f((n+1)%mod,dis+1),f((n*2)%mod,dis+1))+1;
}
void solve(){
	int n;
	cin>>n;
	for(int i = 0;i<n;++i){
		ans = inf;
		int t;
		cin>>t;
		cout<<f(t)<<' ';
	}
	cout<<endl;
}
signed main(){
	IOS;
	solve();
}