USACO 2024 January Contest Bronze Division - Cannonball

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

Simulate the process about \(n \log n\) times as we'll either get out, or the power will get big enough to kick us out right away because of the harmonic sum \((n/1 + n/2 + \dots + n/n)\)

Given the problem constraints, running it for about \(10^6\) steps is good enough to give us full credits.

Source codes

The source codes in C++ and Python can be seen below.

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

int n, s, pw = 1, dir = 1;

bool typ[100001];
bool visited[100001];
int pwr[100001];

int cnt = 0;
int main()
{
    cin >> n >> s;
    for(int i = 1; i <= n; i++)
    {
        int a, b;
        cin >> a >> b;
        typ[i] = a;
        pwr[i] = b;
    }

    if(typ[s] == 1 && pw >= pwr[s])
        cnt++, visited[s] = 1;
    if(typ[s] == 0)
    {
        pw += pwr[s];
        dir = -1;
    }

    for(int i = 1; i <= 1000000; i++)
    {
        s += pw * dir;
        if(s <= 0 || s > n)
            break;
        if(typ[s] == 1 && pw >= pwr[s] && visited[s] == 0)
        {
            visited[s] = 1;
            cnt++;
        }
        if(typ[s] == 0)
        {
            pw += pwr[s];
            dir *= -1;
        }
    }

    cout << cnt;
    return 0;
}

n, s = map(int, input().split())
typ = [False] * (n + 1)
visited = [False] * (n + 1)
pwr = [0] * (n + 1)

for i in range(1, n + 1):
    a, b = map(int, input().split())
    typ[i] = bool(a)
    pwr[i] = b

pw = 1
dir = 1
cnt = 0

if typ[s] and pw >= pwr[s]:
    cnt += 1
    visited[s] = True
if not typ[s]:
    pw += pwr[s]
    dir = -1
for _ in range(1000000):
    s += pw * dir
    if s <= 0 or s > n:
        break
    if typ[s] and pw >= pwr[s] and not visited[s]:
        visited[s] = True
        cnt += 1
    if not typ[s]:
        pw += pwr[s]
        dir *= -1
print(cnt)