Travel around the world

                            Solution in C :

In C++ :





#include <algorithm>
#include <bitset>
#include <cctype>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <typeinfo>
#include <utility>
#include <vector>

using namespace std;

#define output(x) cout << #x << ": " << (x) << endl;

typedef long long LL;
typedef vector<int> VI;
typedef vector<long long> VL;
typedef vector<double> VD;
typedef vector<string> VS;

const int max_n = 100000 + 10;

int n, a[max_n], b[max_n];
LL c, fuel[max_n];

int get_start() {
    int valid_start = -1;
    int start_city = 0, current_city = 0;
    LL current_fuel = 0;
    for (int i = 0; i < n * 2 + 10; ++i) {
        fuel[current_city] = current_fuel;
        int next_city = (current_city + 1) % n;
        LL next_fuel = min(current_fuel + a[current_city], c) - b[current_city];
        if (next_fuel < 0) {
            start_city = current_city = next_city;
            current_fuel = 0;
        } else if (next_city == start_city) {
            valid_start = start_city;
            break;
        } else {
            current_city = next_city;
            current_fuel = next_fuel;
        }
    }
    return valid_start;
}

int count_start() {
    int start = get_start();
    if (start == -1)
        return 0;
    int current = start;
    while (true) {
        int pre = (current + n - 1) % n;
        LL tmp = min(max(fuel[current] + b[pre] - a[pre], 0LL), c);
        if (tmp == fuel[pre])
            break;
        fuel[pre] = tmp;
        current = pre;
    }
    return count(fuel, fuel + n, 0);
}

void solve() {
    cin >> n >> c;
    for (int i = 0; i < n; ++i)
        scanf("%d", &a[i]);
    for (int i = 0; i < n; ++i)
        scanf("%d", &b[i]);
    printf("%d\n", count_start());
}

int main() {
    solve();
    return 0;
}








In Java :





import java.util.Scanner;

public class Solution {

    public static void main(String args[]) {

        Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt();
        long c = scanner.nextLong();
        int a[] = new int[n];
        int b[] = new int[n];

        for (int i = 0; i < n; i++)
            a[i] = scanner.nextInt();

        for (int i = 0; i < n; i++)
            b[i] = scanner.nextInt();

        int currInd = 0;
        long fuel = 0;


        for (int i = 0; i < n; i++) {
//            System.out.println("i is " + i);
            int j = 0;
            while (j < n) {
//                System.out.println(i + " " + j);
                fuel += a[i % n];
                fuel = Math.min(fuel, c);

                if (fuel >= b[i % n])
                    fuel -= b[i % n];
                else {
                    fuel = 0;
                    break;
                }
                i++;
                j++;
            }

            if (j == n)
                currInd = i % n;
            else currInd = -1;
        }

//        System.out.println("index is " + currInd);

//        System.out.println("Answers: ");
        int res = 0;
        if (currInd >= 0) {
            res = 1;
            long ans[] = new long[n];
            ans[currInd] = 0;
            for (int j = 0; j < n - 1; j++) {
                int i = (currInd - j - 1 + n) % n;
                if (Math.min(a[i], c) - b[i] >= ans[(i + 1) % n]) {
                    ans[i] = 0;
                    res++;
                } else {
                    ans[i] = ans[(i + 1) % n] - (Math.min(a[i], c) - b[i]);
                }
//                System.out.println(i + " " + ans[i]);
            }
        }

        System.out.println(res);
    }
}








In C :





#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

int main() {
    int N,i,flag=0;
    long long C,*dp;
    int *a,*b,ans=0;
    scanf("%d%lld",&N,&C);
    a=(int*)malloc(N*sizeof(int));
    b=(int*)malloc(N*sizeof(int));
    dp=(long long*)malloc(2*N*sizeof(long long));
    for(i=0;i<N;i++)
        scanf("%d",a+i);
    for(i=0;i<N;i++)
        scanf("%d",b+i);
    for(i=0;i<2*N;i++)
        dp[i]=1;
    for(i=0;i<N;i++){
if(!i)
dp[i]=0;
else if(a[N-1-i]<=C)
dp[i]=dp[i-1]-a[N-1-i]+b[N-1-i];
    else
    dp[i]=dp[i-1]-C+b[N-1-i];
        if(dp[i]<0)dp[i]=0;
if(dp[i]+((a[N-1-i]>C)?C:a[N-1-i])>C){
flag=1;
    //printf("break at %d\n",i);
break;
}
}
if(!flag){
for(i=0;i<N;i++){
    if(a[N-1-i]<=C)
dp[i+N]=dp[i-1+N]-a[N-1-i]+b[N-1-i];
    else dp[i+N]=dp[i-1+N]-C+b[N-1-i];
    if(dp[i+N]<0)dp[i+N]=0;
if(dp[i+N]+((a[N-1-i]>C)?C:a[N-1-i])>C){
dp[i+N]=1;//printf("break at %d\n",i);
break;
}
}

}

    //for(i=0;i<2*N;i++)
        //printf("%lld ",dp[i]);
    //printf("\n");
    
    for(i=0;i<N;i++)
        if(dp[i+N]<=0)
        ans++;
        printf("%d",ans);
    return 0;
}








In Python3 :





#!/usr/bin/env python3

def travel(cap, fuel, costs):
    fuel = list(fuel)
    costs = list(costs)

    n = len(fuel)
    req = [0] * n
    
    # first iter
    for _ in range(2):
        for i in reversed(range(n)):
            nexti = (i + 1) % n
            req[i] = max(0, req[nexti] + costs[i] - fuel[i])
            if min(req[i] + fuel[i], cap) - costs[i] < req[nexti]:
                return 0

    return sum(1 for r in req if r == 0)

def main():
    cities, capacity = map(int, input().split())
    fuel = map(int, input().split())
    costs = map(int, input().split())
    print(travel(capacity, fuel, costs))
    
if __name__ == '__main__':
    main()