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

№	Пользователь	Рейтинг
1	ecnerwala	3648
2	Benq	3580
3	orzdevinwang	3570
4	cnnfls_csy	3569
5	Geothermal	3568
6	tourist	3565
7	maroonrk	3530
8	Radewoosh	3520
9	Um_nik	3481
10	jiangly	3467

№	Пользователь	Вклад
1	maomao90	174
2	awoo	164
2	adamant	164
4	TheScrasse	159
4	nor	159
6	maroonrk	156
7	-is-this-fft-	150
8	SecondThread	147
9	orz	146
10	pajenegod	145

This is the problem I want to discuss : 1661B - Получение нуля

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

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

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