logoChat01.ai

solve in cpp

Erstellt am: 5. Juli 2025

Beantwortet mit O3 von Chat01

Frage

image.pngimage.png
image.pngimage.png

solve in cpp

Python

python
from PIL import Image
import matplotlib.pyplot as plt

img = Image.open('/mnt/data/image.png')
plt.imshow(img); plt.axis('off')

(-0.5, 999.5, 584.5, -0.5)

Python

python
# crop left part where text on white background
w, h = img.size
crop = img.crop((0,0,int(w*0.62), h))
plt.imshow(crop); plt.axis('off')

(-0.5, 619.5, 584.5, -0.5)

Python

python
# crop bottom area
crop2 = img.crop((0,int(h*0.55), int(w*0.62), h))
plt.imshow(crop2); plt.axis('off')

(-0.5, 619.5, 263.5, -0.5)

Python

python
def maxCandiesArray(arr, c):
    n=len(arr)
    pref=[0]*(n+1)
    for i in range(1,n+1):
        pref[i]=pref[i-1]+arr[i-1]
    l=1
    from collections import deque
    dq=deque()
    maxSum=0
    for r in range(1,n+1):
        # add r
        while dq and pref[dq[-1]]>=pref[r]:
            dq.pop()
        dq.append(r)
        # ensure l valid
        while l<=r and pref[dq[0]] < pref[l-1]-c:
            if dq[0]==l:
                dq.popleft()
            l+=1
        # compute current sum if valid
        if l<=r:
            s=pref[r]-pref[l-1]
            if s>maxSum:
                maxSum=s
    return maxSum + c  # final candies
print(maxCandiesArray([10,-5,20],0))

Python

python
def maxCandies(a,k,c):
    n=len(a)
    overall=c
    for start in range(k):
        # gather subsequence indices start, start+k, ...
        seq=[]
        i=start
        while i<n:
            seq.append(a[i])
            i+=k
        res=maxCandiesArray(seq,c) # but careful: c should not double for each residue
        # Wait: starting c remains unchanged for start; but across residue classes new starting candies still c. our function returns c+maxSegmentSum. So we can just use.
        if res>overall:
            overall=res
    return overall

print(maxCandies([10,-5,20],2,0))

Python

python
print(maxCandies([1,-2,3,-4,5],1,6))

Python

python
def maxCandiesArray_debug(arr,c):
    n=len(arr)
    pref=[0]*(n+1)
    for i in range(1,n+1):
        pref[i]=pref[i-1]+arr[i-1]
    l=1
    from collections import deque
    dq=deque()
    maxSum=0
    for r in range(1,n+1):
        while dq and pref[dq[-1]]>=pref[r]:
            dq.pop()
        dq.append(r)
        while l<=r and pref[dq[0]] < pref[l-1]-c:
            if dq[0]==l:
                dq.popleft()
            l+=1
        if l<=r:
            s=pref[r]-pref[l-1]
            if s>maxSum:
                maxSum=s
    return maxSum+c

print(maxCandiesArray_debug([1,-2,3,-4,5],6))

Python

python
def brute(arr,c):
    n=len(arr)
    best=c
    for l in range(n):
        s=0
        good=True
        cur=c
        for r in range(l,n):
            # step to r
            if arr[r]<0 and cur < -arr[r]:
                good=False
                break
            cur+=arr[r]
            if cur>best: best=cur
    return best
print("brute:", brute([1,-2,3,-4,5],6))

Python

python
def algorithm(arr,c):
    n=len(arr)
    pref=[0]*(n+1)
    for i in range(1,n+1):
        pref[i]=pref[i-1]+arr[i-1]
    l=1
    dq=[]
    maxSum=0
    for r in range(1,n+1):
        while dq and pref[dq[-1]]>=pref[r]:
            dq.pop()
        dq.append(r)
        while l<=r and pref[dq[0]] < pref[l-1]-c:
            if dq[0]==l:
                dq.pop(0)
            l+=1
        if l<=r:
            s=pref[r]-pref[l-1]
            if s>maxSum: maxSum=s
        print("r",r,"l",l,"max",maxSum)
    return maxSum+c
print(algorithm([1,-2,3,-4,5],6))

Python

python
def maxCandiesSimple(arr,c):
    best=0
    cur=0
    for val in arr:
        if cur + val < -c:
            # can't continue; restart
            cur=0
            # Could start new segment at this index
            if val>= -c:
                cur=val
        else:
            cur += val
        if cur>best:
            best=cur
    return best+c

print(maxCandiesSimple([10,-5,20],0))
print(maxCandiesSimple([1,-2,3,-4,5],6))

Python

python
def maxCandiesKadane(arr,c):
    best=0
    cur=0
    for val in arr:
        cur += val
        # ensure not dropping below -c
        if cur < -c:
            # restart cannot include this val maybe if val>= -c; handle
            if val >= -c:
                cur = val
            else:
                cur = 0
            # but may still -c?? Already handled
        if cur < 0:
            cur = 0
        if cur > best:
            best = cur
    return best + c

print(maxCandiesKadane([1,-2,3,-4,5],6))

Python

python
print(maxCandiesKadane([10,-5,20],0))

Python

python
print(maxCandiesKadane([10,20],0))

Python

python
import random, itertools, math
def maxCandiesBrute(a,k,c):
    n=len(a)
    best=c
    for x in range(n+1): # start index or n means no start?
        for y in range(x, n):
            if (y - x)%k==0:
                cur=c
                ok=True
                i = x
                while i<=y:
                    val=a[i]
                    if val>=0:
                        cur+=val
                    else:
                        if cur < -val:
                            ok=False
                            break
                        cur+=val
                    i+=k
                if ok and cur > best:
                    best=cur
    return best

def solve(a,k,c):
    n=len(a)
    best=c
    for start in range(k):
        seq=[]
        idxs=[]
        i=start
        while i<n:
            seq.append(a[i])
            idxs.append(i)
            i+=k
        # run algorithm on seq
        best_seq = maxCandiesKadane(seq,c)
        if best_seq>best:
            best = best_seq
    return best

def test():
    for n in range(1,16):
        for _ in range(1000):
            k=random.randint(1,min(5,n))
            a=[random.randint(-3,5) for _ in range(n)]
            c=random.randint(0,5)
            b=solve(a,k,c)
            brute_val=maxCandiesBrute(a,k,c)
            if b!=brute_val:
                return a,k,c,b,brute_val
    return None

res=test()
print(res)

Python

python
def test_many():
    for n in range(1,10):
        for _ in range(10000):
            k=random.randint(1,min(4,n))
            a=[random.randint(-10,10) for _ in range(n)]
            c=random.randint(0,5)
            if solve(a,k,c)!=maxCandiesBrute(a,k,c):
                return a,k,c,solve(a,k,c),maxCandiesBrute(a,k,c)
    return None
print(test_many())

Gedanke

Considering positive index overlap

It seems there are cases where starting at a later index gives the same remainder as an earlier index, making the negative value irrelevant. Resetting to 0 helps discard the negative value, but we still scan through the sequence. The key thing here is that the negative value isn’t skipped, even though we reset. It allows us to continue scanning and still find accessible positions, starting from later indices, so we don’t necessarily need the negative value.

Disregarding negative value

Resetting to 0 makes us discard the negative value, but we're still continuing to scan the sequence, so index2 remains accessible. The key point here is that although we reset the value to 0, we've still visited the negative value before resetting. Essentially, once we continue the scan, negative values are left behind, but they don’t entirely block us from reaching future positive values. The reset just starts fresh from a later position in the sequence.

Clearing negative values while scanning

When resetting after encountering a negative value, we continue scanning, but we don’t include the negative value in the new segment

Thought for 3m 2s

Antwort

Idea

  • The k-jump rule splits the array into at most k independent tracks –
    index 0 → 0+k → 0+2k …, index 1 → 1+k → …, … , index k-1 → k-1+k → ….
  • Inside one track Maku simply walks along a normal array; she may start at any position and must keep her candy - balance ≥ 0 at every step
    (balance = mom + segment-prefix, so we only have to ensure that the running sum of the chosen segment never drops below −c).
  • For every track we therefore need the maximum-sum contiguous segment whose running sum never goes below −c.
    A slightly modified Kadane scan does that in O(length):
text
cur = current segment sum     (relative to its start)
best = best segment sum found so far (relative to its start)
for each value v in the track
        if cur + v < -c          // continuing would throw her in jail
                // either start a new segment here (if legal) or skip
                cur = (v >= -c) ? v : 0
        else
                cur += v         // safe to continue
        if cur < 0               // negative prefix only hurts later sums
                cur = 0          // drop it – start after this position
        best = max(best , cur)
answer for this track = best + c      // add mom’s candies back
  • Scan every track; the global maximum is the answer.

The whole procedure is O(n) (≤ 10⁵) and uses O(1) extra memory.

Code

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

int ninja(vector<int> a, int k, int c)
{
    const long long C = c;          // work with 64-bit
    long long answer = C;           // taking nothing at all is always legal

    int n = (int)a.size();
    for (int start = 0; start < k && start < n; ++start)
    {
        long long cur = 0;          // current segment sum (relative to its start)
        for (int idx = start; idx < n; idx += k)
        {
            int v = a[idx];

            // can we safely continue the current segment?
            if (cur + v < -C) {                 // would go to jail
                // try to start a new segment at idx (only if legal)
                cur = (v >= -C) ? v : 0;
            } else {
                cur += v;                       // keep going
            }

            if (cur < 0) cur = 0;               // discard hurting prefix
            answer = max(answer, cur + C);      // best candies so far
        }
    }
    return (int)answer;                         // fits in 32-bit per constraints
}

/* ------------------ simple I/O wrapper ------------------ */
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;                     // number of banks
    if (!(cin >> n)) return 0;
    vector<int> a(n);
    for (int &x : a) cin >> x;
    int k, c;                  // jump length and mom's candies
    cin >> k >> c;

    cout << ninja(a, k, c) << '\n';
    return 0;
}

Time-complexity: O(n)  Memory: O(1) (apart from the input array)

Diesen Q&A teilen