logoChat01.ai

Pregunta

WhatsApp Image 2026-03-14 at 10.42.23 PM.jpeg
WhatsApp Image 2026-03-14 at 10.42.09 PM.jpeg
WhatsApp Image 2026-03-14 at 10.41.52 PM.jpeg
WhatsApp Image 2026-03-14 at 10.43.18 PM.jpeg

code it in cpp

Python

python
from collections import deque, defaultdict
from math import gcd

def norm(t):
    a,b,c=t
    g=gcd(gcd(a,b),c)
    return tuple(sorted((a//g,b//g,c//g)))
def bfs(limit=10):
    res={}
    for a in range(1,limit+1):
        for b in range(1,limit+1):
            for c in range(1,limit+1):
                start=tuple(sorted((a,b,c)))
                # BFS
                q=deque([(start,0)])
                seen={start}
                ans=None
                while q:
                    x,y,z=d=q.popleft() if False else None
                # use Dijkstra BFS since edge 1
                q=deque([start]); dist={start:0}
                while q:
                    s=q.popleft()
                    d=dist[s]
                    if s[0]==0:
                        ans=d; break
                    a,b,c=s
                    g=gcd(gcd(a,b),c)
                    for i,v in enumerate((a,b,c)):
                        if v>=g:
                            t=list((a,b,c)); t[i]-=g
                            t=tuple(sorted(t))
                            if t not in dist:
                                dist[t]=d+1; q.append(t)
                res[start]=ans
    return res

def f(n,m):
    # reduce n to0 with other pair gcd m fixed
    cnt=0
    while n:
        g=gcd(n,m)
        n-=g
        cnt+=1
    return cnt

res=bfs(10)
bad=[]
for s,ans in res.items():
    a,b,c=s
    est=min(f(a,gcd(b,c)),f(b,gcd(a,c)),f(c,gcd(a,b)))
    if est!=ans:
        bad.append((s,ans,est))
len(bad), bad[:20]

Python

python
from collections import deque
from math import gcd

def bfs(limit=10):
    res={}
    for a in range(1,limit+1):
        for b in range(1,limit+1):
            for c in range(1,limit+1):
                start=tuple(sorted((a,b,c)))
                if start in res:
                    continue
                q=deque([start]); dist={start:0}
                ans=None
                while q:
                    s=q.popleft()
                    d=dist[s]
                    if s[0]==0:
                        ans=d; break
                    x,y,z=s
                    g=gcd(gcd(x,y),z)
                    for i,v in enumerate((x,y,z)):
                        if v>=g:
                            t=[x,y,z]; t[i]-=g
                            t=tuple(sorted(t))
                            if t not in dist:
                                dist[t]=d+1; q.append(t)
                res[start]=ans
    return res

def f(n,m):
    cnt=0
    while n:
        g=gcd(n,m)
        n-=g
        cnt+=1
    return cnt

res=bfs(10)
bad=[]
for s,ans in sorted(res.items()):
    a,b,c=s
    est=min(f(a,gcd(b,c)),f(b,gcd(a,c)),f(c,gcd(a,b)))
    if est!=ans:
        bad.append((s,ans,est))
len(bad), bad[:50]


(30,
 [((3, 3, 7), 2, 3),
  ((3, 3, 10), 2, 3),
  ((3, 6, 7), 2, 3),
  ((3, 7, 9), 2, 3),
  ((3, 9, 10), 2, 3),
  ((4, 4, 9), 2, 3),
  ((4, 5, 5), 3, 4),
  ((4, 5, 9), 3, 4),
  ((4, 6, 7), 3, 4),
  ((4, 7, 9), 3, 4),
  ((4, 7, 10), 3, 4),
  ((4, 8, 9), 2, 3),
  ((4, 9, 10), 3, 4),
  ((5, 5, 8), 3, 4),
  ((5, 5, 9), 4, 5),
  ((5, 6, 7), 4, 5),
  ((5, 7, 8), 4, 5),
  ((5, 7, 9), 4, 5),
  ((5, 8, 9), 3, 5),
  ((5, 9, 10), 4, 5),
  ((6, 7, 7), 3, 6),
  ((6, 7, 8), 3, 4),
  ((6, 8, 9), 3, 4),
  ((6, 9, 10), 3, 4),
  ((7, 8, 9), 4, 7),
  ((7, 9, 10), 4, 7),
  ((8, 9, 9), 3, 4),
  ((8, 9, 10), 3, 5),
  ((8, 10, 10), 3, 4),
  ((9, 10, 10), 3, 5)])

Python

python
from collections import deque
from math import gcd

def shortest_path(start):
    start=tuple(sorted(start))
    q=deque([start]); dist={start:0}; parent={start:None}
    while q:
        s=q.popleft(); d=dist[s]
        if s[0]==0:
            path=[s]
            while parent[path[-1]] is not None:
                path.append(parent[path[-1]][0])
            path.reverse()
            moves=[]
            cur=start
            # reconstruct moves maybe
            node=s
            path=[s]
            while parent[node] is not None:
                path.append(parent[node][0]); node=parent[node][0]
            path.reverse()
            return d,path
        x,y,z=s
        g=gcd(gcd(x,y),z)
        for i,v in enumerate((x,y,z)):
            t=[x,y,z]; t[i]-=g
            t=tuple(sorted(t))
            if t not in dist:
                dist[t]=d+1; parent[t]=(s,i)
                q.append(t)
    return None

d,path=shortest_path((5,6,7))
d,path


(4, [(5, 6, 7), (4, 6, 7), (3, 6, 7), (3, 6, 6), (0, 6, 6)])

Python

python
from functools import lru_cache
from math import gcd

def Hrec(state):
    state=tuple(sorted(state))
    @lru_cache(None)
    def dp(s):
        a,b,c=s
        if a==0: return 0
        best=10**9
        mx=max(s)
        for d in range(2,mx+1):
            r=(a%d,b%d,c%d)
            na,nb,nc=(a-r[0])//d,(b-r[1])//d,(c-r[2])//d
            if (na,nb,nc)==(a,b,c): # d=1 not possible
                continue
            cand=sum(r)+dp(tuple(sorted((na,nb,nc))))
            if cand<best:
                best=cand
        return best
    return dp(state)

bad=[]
for s,ans in sorted(res.items()):
    est=Hrec(s)
    if est!=ans:
        bad.append((s,ans,est))
len(bad), bad[:20]


(137,
 [((1, 1, 1), 1, 1000000000),
  ((1, 1, 2), 1, 2),
  ((1, 1, 3), 1, 2),
  ((1, 1, 4), 1, 2),
  ((1, 1, 5), 1, 2),
  ((1, 1, 6), 1, 2),
  ((1, 1, 7), 1, 2),
  ((1, 1, 8), 1, 2),
  ((1, 1, 9), 1, 2),
  ((1, 1, 10), 1, 2),
  ((1, 2, 3), 1, 2),
  ((1, 2, 5), 1, 2),
  ((1, 2, 7), 1, 2),
  ((1, 2, 9), 1, 2),
  ((1, 3, 4), 1, 2),
  ((1, 3, 5), 1, 3),
  ((1, 3, 7), 1, 2),
  ((1, 3, 8), 1, 2),
  ((1, 3, 10), 1, 2),
  ((1, 4, 5), 1, 2)])

Python

python
from functools import lru_cache
from math import gcd

@lru_cache(None)
def Fdp(s):
    a,b,c=s
    if a==0: return 0
    best=min(f(a,gcd(b,c)),f(b,gcd(a,c)),f(c,gcd(a,b)))
    mx=max(s)
    for d in range(2,mx+1):
        r=(a%d,b%d,c%d)
        na,nb,nc=(a-r[0])//d,(b-r[1])//d,(c-r[2])//d
        if (na,nb,nc)==(a,b,c):
            continue
        cand=sum(r)+Fdp(tuple(sorted((na,nb,nc))))
        if cand<best:
            best=cand
    return best

bad=[]
for s,ans in sorted(res.items()):
    est=Fdp(s)
    if est!=ans:
        bad.append((s,ans,est))
len(bad), bad[:50]


(2, [((6, 10, 10), 3, 2), ((7, 10, 10), 4, 3)])

Python

python
res[(3,5,5)], Fdp((3,5,5))


(3, 3)

Python

python
from functools import lru_cache
from math import gcd

def normalize_state(s):
    a,b,c=s
    g=gcd(gcd(a,b),c)
    return tuple(sorted((a//g,b//g,c//g)))

@lru_cache(None)
def DP(s):
    s=normalize_state(s)
    a,b,c=s
    if a==0: return 0
    best=min(f(a,gcd(b,c)),f(b,gcd(a,c)),f(c,gcd(a,b)))
    mx=max(s)
    for d in range(2,mx+1):
        r=(a%d,b%d,c%d)
        na,nb,nc=(a-r[0])//d,(b-r[1])//d,(c-r[2])//d
        if (na,nb,nc)==(a,b,c):
            continue
        cand=sum(r)+DP(tuple(sorted((na,nb,nc))))
        if cand<best:
            best=cand
    return best

bad=[]
for s,ans in sorted(res.items()):
    est=

(1, [((7, 10, 10), 4, 3)])

Python

python
shortest_path((7,10,10))


(4, [(7, 10, 10), (6, 10, 10), (4, 10, 10), (2, 10, 10), (0, 10, 10)])

Python

python
from functools import lru_cache
from math import gcd

def normalize(s):
    a,b,c=s
    g=gcd(gcd(a,b),c)
    return tuple(sorted((a//g,b//g,c//g)))

@lru_cache(None)
def DPrestrict(s):
    s=normalize(s)
    a,b,c=s
    if a==0:
        return 0
    # direct zero before any normalization: a unit decrements on smallest dimension? but if gcd>1 not normalized
    # In normalized state gcd1, one can always reduce smallest a to0 in a steps with maybe earlier normalization. But earliest normalization may happen sooner.
    mx=max(s)
    costs=[]
    minc=None
    for d in range(2,mx+1):
        r=(a%d,b%d,c%d)
        cst=sum(r)
        if minc is None or cst<minc:
            minc=cst; costs=[(d,r)]
        elif cst==minc:
            costs.append((d,r))
    best=a  # maybe reduce smallest to0 directly if no gcd>1 before? but we'll see
    for d,r in costs:
        vals=(a-r[0],b-r[1],c-r[2])
        g=gcd(gcd(*vals[:2]),vals[2])
        cand=minc + DPrestrict(tuple(sorted(v//g for v in vals)))
        best=min(best,cand)
    return best

bad=[]
for s,ans in sorted(res.items()):
    est=DPrestrict(s)
    if est!=ans:
        bad.append((s,ans,est))
len(bad), bad[:50]


(2, [((7, 7, 10), 4, 5), ((9, 10, 10), 3, 4)])

Python

python
shortest_path((9,10,10))


(3, [(9, 10, 10), (9, 9, 10), (9, 9, 9), (0, 9, 9)])

Python

python
from functools import lru_cache
from collections import deque
from math import gcd

def normalize_s(t):
    a,b,c=t
    g=gcd(gcd(a,b),c)
    return tuple(sorted((a//g,b//g,c//g)))

def fixed_reduce(n,m):
    cnt=0
    while n>0:
        g=gcd(n,m)
        n-=g
        cnt+=1
    return cnt

@lru_cache(None)
def solve_state(s):
    s=normalize_s(s)
    a,b,c=s
    if a==0:
        return 0
    # initial upper bound
    best=min(
        fixed_reduce(a,gcd(b,c)),
        fixed_reduce(b,gcd(a,c)),
        fixed_reduce(c,gcd(a,b))
    )
    # BFS through gcd1 states before next normalization
    q=deque([s])
    dist={s:0}
    while q:
        x,y,z=q.popleft()
        d=dist[(x,y,z)]
        if d>=best:
            continue
        for i,v in enumerate((x,y,z)):
            if v==0: continue
            t=[x,y,z]; t[i]-=1
            t=tuple(sorted(t))
            nd=d+1
            if nd>=best:
                continue
            g=gcd(gcd(t[0],t[1]),t[2])
            if g>1:
                cand=nd+solve_state(tuple(v//g for v in t))
                if cand<best:
                    best=cand
            else:
                if t[0]==0:
                    best=min(best, nd)
                elif t not in dist:
                    dist[t]=nd
                    q.append(t)
    return best

bad=[]
for s,ans in sorted(res.items()):
    est=solve_state(s)
    if est!=ans:
        bad.append((s,ans,est))
len(bad), bad[:20]


(0, [])

Python

python
import random, time
solve_state.cache_clear()
start=time.time()
for _ in range(100):
    s=tuple(sorted((random.randint(1,40),random.randint(1,40),random.randint(1,40))))
    val=solve_state(s)
end=time.time()
end-start, solve_state.cache_info()


(0.017395496368408203,
 CacheInfo(hits=856, misses=369, maxsize=None, currsize=369))

Python

python
solve_state.cache_clear()
start=time.time()
vals=[]
for s in [(100,101,103),(97,101,103),(100,150,175),(121,143,169),(200,201,203)]:
    t=time.time(); v=solve_state(tuple(sorted(s))); vals.append((s,v,time.time()-t))
time.time()-start, vals, solve_state.cache_info()


(0.012595653533935547,
 [((100, 101, 103), 4, 0.00015306472778320312),
  ((97, 101, 103), 7, 0.0006697177886962891),
  ((100, 150, 175), 3, 1.9788742065429688e-05),
  ((121, 143, 169), 9, 0.011373043060302734),
  ((200, 201, 203), 4, 9.918212890625e-05)],
 CacheInfo(hits=1176, misses=172, maxsize=None, currsize=172))

Python

python
solve_state.cache_clear()
tests=[(997,1009,1013),(999,1000,1001),(9991,10007,10009),(4999,5000,5001)]
for s in tests:
    t=time.time(); 
    v=solve_state(tuple(sorted(s)))
    print(s,v,time.time()-t)

Python

python
solve_state.cache_clear()
mx=(None,0)
for a in range(1,51):
    for b in range(a,51):
        for c in range(b,51):
            v=solve_state((a,b,c))
            if v>mx[1]:
                mx=((a,b,c),v)
mx


((17, 23, 47), 9)

Python

python
import random, time, math
solve_state.cache_clear()
mx=(None,0)
for _ in range(200):
    s=tuple(sorted((random.randint(1,10000),random.randint(1,10000),random.randint(1,10000))))
    v=solve_state(s)
    if v>mx[1]:
        mx=(s,v)
mx

Python

python
from functools import lru_cache
from math import gcd, isqrt

@lru_cache(None)
def prime_factors(m):
    x=m
    fs=[]
    d=2
    while d*d<=x:
        if x%d==0:
            fs.append(d)
            while x%d==0:
                x//=d
        d+=1 if d==2 else 2
    if x>1: fs.append(x)
    return tuple(fs)

@lru_cache(None)
def fast_f(n,m):
    if n==0:
        return 0
    g=gcd(n,m)
    if g>1:
        return 1 + fast_f(n//g - 1, m//g)
    if m==1:
        return n
    k=min(n%p for p in prime_factors(m))
    return k + fast_f(n-k, m)

for n,m in [(7,10),(9,12),(25,36),(11,12),(25,2),(9991,1)]:
    print(n,m,fast_f(n,m))

Python

python
from functools import lru_cache
from collections import deque
from math import gcd
import random, time

def norm(s):
    a,b,c=s
    g=gcd(gcd(a,b),c)
    return tuple(sorted((a//g,b//g,c//g)))

@lru_cache(None)
def solve2(s):
    s=norm(s)
    a,b,c=s
    if a==0:
        return 0
    best=min(
        fast_f(a,gcd(b,c)),
        fast_f(b,gcd(a,c)),
        fast_f(c,gcd(a,b))
    )
    q=deque([s])
    dist={s:0}
    while q:
        x,y,z=q.popleft()
        d=dist[(x,y,z)]
        if d>=best:
            continue
        # small heuristic: if d+1>=best skip
        for i,v in enumerate((x,y,z)):
            if v==0: continue
            t=[x,y,z]; t[i]-=1
            t=tuple(sorted(t))
            nd=d+1
            if nd>=best:
                continue
            g=gcd(gcd(t[0],t[1]),t[2])
            if g>1:
                nxt=(t[0]//g,t[1]//g,t[2]//g)
                cand=nd+solve2(nxt)
                if cand<best:
                    best=cand
            else:
                if t[0]==0:
                    best=min(best, nd)
                elif t not in dist:
                    dist[t]=nd
                    q.append(t)
    return best

# test vs brute small
bad=[]
for s,ans in sorted(res.items()):
    est=solve2(s)
    if est!=ans:
        bad.append((s,ans,est))
print("bad",len(bad))

solve2.cache_clear()
start=time.time()
tests=[tuple(sorted((random.randint(1,100000),random.randint(1,100000),random.randint(1,100000)))) for _ in range(100)]
vals=[]
for s in tests[:20]:
    t=time.time(); 
    v=solve2(s)
    vals.append(time.time()-t)
print("avg",sum(vals)/len(vals),"max",max(vals), "cache", solve2.cache_info())

Pensamiento

bash -lc g++ -std=c++17 /tmp/box.cpp -O2 -o /tmp/box.out && /tmp/box.out

Thought for 17m 25s

Respuesta

Use this C++17 solution for boxVolume(int input1, int input2, int input3).

Replace the throw line with this full logic:

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

struct State {
    int a, b, c;

    bool operator==(const State& other) const {
        return a == other.a && b == other.b && c == other.c;
    }
};

struct StateHash {
    size_t operator()(const State& s) const noexcept {
        size_t h = (size_t)s.a;
        h ^= (size_t)s.b + 0x9e3779b97f4a7c15ULL + (h << 6) + (h >> 2);
        h ^= (size_t)s.c + 0x9e3779b97f4a7c15ULL + (h << 6) + (h >> 2);
        return h;
    }
};

struct Solver {
    unordered_map<State, int, StateHash> memo;
    unordered_map<int, vector<int>> factorCache;
    unordered_map<unsigned long long, int> pairMemo;

    State normalize(long long x, long long y, long long z) {
        long long g = gcd(x, gcd(y, z));
        x /= g;
        y /= g;
        z /= g;
        vector<long long> v = {x, y, z};
        sort(v.begin(), v.end());
        return {(int)v[0], (int)v[1], (int)v[2]};
    }

    vector<int>& getPrimeFactors(int m) {
        auto it = factorCache.find(m);
        if (it != factorCache.end()) return it->second;

        vector<int> factors;
        int x = m;

        if (x % 2 == 0) {
            factors.push_back(2);
            while (x % 2 == 0) x /= 2;
        }

        for (int d = 3; 1LL * d * d <= x; d += 2) {
            if (x % d == 0) {
                factors.push_back(d);
                while (x % d == 0) x /= d;
            }
        }

        if (x > 1) factors.push_back(x);

        auto res = factorCache.emplace(m, std::move(factors));
        return res.first->second;
    }

    int reduceOneDimension(int n, int m) {
        if (n == 0) return 0;

        unsigned long long key =
            (static_cast<unsigned long long>(static_cast<unsigned int>(n)) << 32) |
            static_cast<unsigned int>(m);

        auto it = pairMemo.find(key);
        if (it != pairMemo.end()) return it->second;

        int ans;
        int g = gcd(n, m);

        if (g > 1) {
            ans = 1 + reduceOneDimension(n / g - 1, m / g);
        } else if (m == 1) {
            ans = n;
        } else {
            int jump = INT_MAX;
            for (int p : getPrimeFactors(m)) {
                jump = min(jump, n % p);
            }
            ans = jump + reduceOneDimension(n - jump, m);
        }

        pairMemo[key] = ans;
        return ans;
    }

    int solve(State s) {
        s = normalize(s.a, s.b, s.c);
        if (s.a == 0) return 0;

        auto it = memo.find(s);
        if (it != memo.end()) return it->second;

        int best = min({
            reduceOneDimension(s.a, gcd(s.b, s.c)),
            reduceOneDimension(s.b, gcd(s.a, s.c)),
            reduceOneDimension(s.c, gcd(s.a, s.b))
        });

        queue<State> q;
        unordered_map<State, int, StateHash> dist;
        q.push(s);
        dist[s] = 0;

        while (!q.empty()) {
            State cur = q.front();
            q.pop();

            int d = dist[cur];
            if (d >= best) continue;

            int val[3] = {cur.a, cur.b, cur.c};

            for (int i = 0; i < 3; i++) {
                if (val[i] == 0) continue;

                int nxt[3] = {val[0], val[1], val[2]};
                nxt[i]--;

                sort(nxt, nxt + 3);
                int nd = d + 1;

                if (nd >= best) continue;

                int g = gcd(nxt[0], gcd(nxt[1], nxt[2]));

                if (g > 1) {
                    State ns = {nxt[0] / g, nxt[1] / g, nxt[2] / g};
                    best = min(best, nd + solve(ns));
                } else {
                    if (nxt[0] == 0) {
                        best = min(best, nd);
                    } else {
                        State ns = {nxt[0], nxt[1], nxt[2]};
                        if (!dist.count(ns)) {
                            dist[ns] = nd;
                            q.push(ns);
                        }
                    }
                }
            }
        }

        memo[s] = best;
        return best;
    }
};

int boxVolume(int input1, int input2, int input3)
{
    Solver solver;
    return solver.solve({input1, input2, input3});
}

For the examples in your image:

  • boxVolume(4, 7, 8) = 3
  • boxVolume(9, 25, 37) = 4

If you want, I can also give a shorter version without structs, written to fit directly inside that Mettl function template.

Compartir este Q&A