logoChat01.ai

#include <bits/stdc++.h> #pragma GCC optimize("O3"...

Créé le : 16 mai 2026

Répondu en utilisant GPT-5.5 par Chat01

Question

image.png

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC target("avx2")
#pragma GCC target("popcnt")
using namespace std;

#define endl "\n"
#define pb emplace_back
#define pii pair<int, int>
#define all(v) v.begin(), v.end()
#define uset unordered_set
#define umap unordered_map
typedef long double ld;
typedef long long ll;
#define int long long
int const N = 1e6 + 5, M = 1e3 + 5, INF = 2e9, INFLL = 3e18;
int P = 137, MOD = 1e9 + 7, MOD2 = 1e9 + 9;
mt19937 rnd(time(nullptr));

inline int rand(int l, int r) {
return rnd() % (r - l) + l;
}

void solve1() {
int a, n; cin >> a >> n;
int d1, d2; cin >> d1 >> d2;
if (d1 > d2) swap(d1, d2);

}

void solve() {
int n, x1, x2, k;
cin >> n >> x1 >> x2 >> k;
if (x1 > x2) swap(x1, x2);
int a1 = abs(x1 - x2);
int a2 = x1 + (n - x2);
cout << (min(a1, a2)) + k << endl;
}

int32_t main() {
ios_base::sync_with_stdio(0);
cin.tie(0);

text
int t; cin >> t;

while (t--) {
    solve();
}


return 0;

}

что не так

Python

python
from functools import lru_cache

def val(n,a,m): # a cw distance C->R, b=n-a
    b=n-a
    @lru_cache(None)
    def V(a,m):
        b=n-a
        # state noncaptured a in 1..n-1
        opts=[]
        acts=[a] # stay no budget
        if m>0:
            if a+1<=n-1: acts.append(a+1)
            # if a+1 == n means robber onto cop -> captured by stay
            if a-1>=1: acts.append(a-1)
        best=-10**9
        for ap in acts:
            bp=n-ap
            if min(ap,bp)<=1:
                t=1
            else:
                # cop choices cw/counter
                # after moving cw if ap==1 capture handled, state ap-1? actually nonzero
                nexts=[]
                nexts.append(ap-1) # cw, valid >=1 since ap>1
                nexts.append(ap+1) # ccw, valid <=n-1 since bp>1
                t=1+min(V(x, m-(ap!=a)) for x in nexts)
            best=max(best,t)
        return best
    return V(a,m)

for n in range(3,11):
    print("n",n)
    for a in range(1,n):
        row=[val(n,a,k) for k in range(0,5)]
        print(a,row)
    print()

Réflexion

from functools import lru_cache

def val(n,a,m): # a cw distance C->R, b=n-a b=n-a @lru_cache(None) def V(a,m): b=n-a # state noncaptured a in 1..n-1 opts=[] acts=[a] # stay no budget if m>0: if a+1<=n-1: acts.append(a+1) # if a+1 == n means robber onto cop -> captured by stay if a-1>=1: acts.append(a-1) best=-10**9 for ap in acts: bp=n-ap if min(ap,bp)<=1: t=1 else: # cop choices cw/counter # after moving cw if ap==1 capture handled, state ap-1? actually nonzero nexts=[] nexts.append(ap-1) # cw, valid >=1 since ap>1 nexts.append(ap+1) # ccw, valid <=n-1 since bp>1 t=1+min(V(x, m-(ap!=a)) for x in nexts) best=max(best,t) return best return V(a,m)

for n in range(3,11): print("n",n) for a in range(1,n): row=[val(n,a,k) for k in range(0,5)] print(a,row) print()

Thought for 1m 48s

Réponse

Ошибка в маленьких n.

Для n = 2 или n = 3 любые две разные позиции соседние, поэтому Рейму поймает Ремилию уже за 1 секунду, независимо от k. Твоя формула dist + k даст слишком большой ответ.

Для n >= 4 идея минимальное расстояние + k верная.

Исправь так:

cpp
void solve() {
    long long n, x1, x2, k;
    cin >> n >> x1 >> x2 >> k;

    if (n <= 3) {
        cout << 1 << '\n';
        return;
    }

    long long d = abs(x1 - x2);
    d = min(d, n - d);

    cout << d + k << '\n';
}

Почему: каждый ход Ремилии может максимум “отменить” один ход Рейму, то есть добавить не больше 1 секунды. Таких ходов максимум k. Но при n <= 3 убежать невозможно: после любого действия Ремилия всё равно будет на той же или соседней позиции, и Рейму сразу её ловит.

Question

image.png

c++

Réflexion

Thought for a couple of seconds

Réponse

Так как n = 2, разрешены только две цифры x и y. Нужно найти число b, состоящее только из этих цифр, максимально близкое к a.

Достаточно проверить кандидатов длины len(a)-1, len(a), len(a)+1, потому что дальше точно хуже.

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

using ll = long long;

ll best;
string A;
int d[2];

void gen(string cur, int len, ll a) {
    if ((int)cur.size() == len) {
        if (cur.size() > 1 && cur[0] == '0') return;
        ll b = stoll(cur);
        best = min(best, llabs(a - b));
        return;
    }

    for (int i = 0; i < 2; i++) {
        gen(cur + char('0' + d[i]), len, a);
    }
}

void solve() {
    ll a;
    int n;
    cin >> a >> n;

    cin >> d[0] >> d[1];

    A = to_string(a);
    best = LLONG_MAX;

    int len = A.size();

    for (int l = max(1, len - 1); l <= len + 1; l++) {
        gen("", l, a);
    }

    cout << best << '\n';
}

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

    int t;
    cin >> t;

    while (t--) {
        solve();
    }

    return 0;
}

Здесь максимум длина числа a — 18, значит перебор около 2^19, что нормально для простой версии.

Partager cette Q&R