Записи в блоге

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;
}

Полный текст и комментарии »

№	Пользователь	Рейтинг
1	Benq	3792
2	VivaciousAubergine	3647
3	Kevin114514	3603
4	jiangly	3583
5	strapple	3515
6	tourist	3470
7	dXqwq	3436
8	Radewoosh	3415
9	Otomachi_Una	3413
10	Um_nik	3376

№	Пользователь	Вклад
1	Qingyu	158
2	adamant	152
3	Proof_by_QED	146
3	Um_nik	146
5	Dominater069	144
6	errorgorn	141
7	cry	139
8	YuukiS	135
9	chromate00	134
9	TheScrasse	134

Блог пользователя rezidentura