Blog entries - Codeforces

#	User	Rating
1	jiangly	4039
2	tourist	3841
3	jqdai0815	3682
4	ksun48	3590
5	ecnerwala	3542
6	Benq	3535
7	orzdevinwang	3526
8	gamegame	3477
9	heuristica	3357
10	Radewoosh	3355

#	User	Contrib.
1	cry	168
2	-is-this-fft-	165
3	atcoder_official	160
3	Um_nik	160
5	djm03178	157
6	Dominater069	156
7	adamant	153
8	luogu_official	152
9	awoo	151
10	TheScrasse	147

This is the problem I want to discuss : 1661B - Getting Zero

I have this answer, It's not mine but I made it cleaner (I think).

The answer

#include <bits/stdc++.h>
using namespace std;

int main() {
 
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int M = 32768;
    vector<int> ans(M, -1);
    ans[0] = 0;

    function<int(int)> dfs = [&](int x) {
        if(ans[x] != -1) return ans[x];
        ans[x] = 1 + dfs(2 * x % M);
        ans[x] = min(ans[x], 1 + dfs((x + 1) % M));
        return ans[x];
    };
 
    int T; cin >> T;
    while (T--) {
        int n; cin >> n;
        cout << dfs(n) << "\n";
    }
    return 0;
}

I have two questions and thank you in advance.

1) Why deleting this line : return ans[x]; gives wrong answer.

2) why changing the code into the 2 code below gives wrong answer :

2 code

#include <bits/stdc++.h>
using namespace std;

int main() {
 
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int M = 32768;
    vector<int> ans(M, -1);
    ans[0] = 0;

    function<int(int)> dfs = [&](int x) {
        if(ans[x] != -1) return ans[x];

        ans[x] = min(1 + dfs(2 * x % M), 1 + dfs((x + 1) % M));
        
        return ans[x];
    };
 
    int T; cin >> T;
    while (T--) {
        int n; cin >> n;
        cout << dfs(n) << "\n";
    }
    return 0;
}

Full text and comments »

rezidentura's blog