Overtaking
Source: aizu

Problem B
Overtaking

Two athletes run a long-distance race, but the race is different from usual athletics events. They run for a predetermined duration, and the one who runs longer will be the winner. At every minute after the start, the distances both runners ran in the previous one minute are recorded. You are expected to write a program that, given the record of a race, counts the number of overtakings by either runner during the race. You should assume that both runners keep constant paces for every one minute before their distances are recorded.

Here, the term overtaking stands for the event where the runner previously behind takes the lead. Note that, before overtaking, the two runners may run side by side for a while, during which neither takes the lead. Figure B-1 shows the times and the positions of two runners for the third dataset of Sample Input. The number of overtakings in this case is two.

Figure B-1: The third dataset of Sample Input
Input

The input consists of multiple datasets, each in the following format.

n
a1 ⋯ an 
b1 ⋯ bn 


n is an integer between 2 and 1000, inclusive. It represents the duration of the race in minutes. Each of ak (k = 1, , n) is an integer between 1 and 1000, inclusive. It represents the distance the first runner ran between k − 1 minutes and k minutes after the start of the race, in meters. Similarly, bk (k = 1, , n) represent the distances the second runner ran.

The end of the input is indicated by a line consisting of a zero. The number of datasets does not exceed 100.

Output

For each dataset, output the number of overtakings on a line.

Sample Input
3
5 15 5
10 5 15
9
10 10 10 10 10 10 10 10 10
5 15 10 5 15 10 5 15 10
9
10 10 10 5 15 10 10 10 10
5 15 10 10 10 10 5 15 10
0

Output for the Sample Input
2
0
2


C++ solution:
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    while(true){
        cin >> n;
        int a[n],b[n];
        int dis_a=0, dis_b=0
        , dis;

        int count=0, count_ans=0;
        if(n == 0) break;
        int flag=-1;
        for(int i=0; i<n; i++){
            cin >> a[i]; 
        }
        for(int i=0; i<n; i++){
            cin >> b[i];
        }

        for(int i=0; i<n; i++){
            count++;
            dis_a += a[i];
            dis_b += b[i];
            dis = dis_a - dis_b;
            if(dis == 0) continue;
            else if(dis > 0){
                flag = 1;
                break;
            }
            else if(dis < 0){
                flag = 0;
                break;
            }
        }

            for(int i=count; i<n; i++){
                dis_a += a[i];
                dis_b += b[i];
                dis = dis_a - dis_b;
                if(dis > 0){
                    if(flag == 1) continue;
                    else if(flag == 0){
                        count_ans += 1;
                        flag = 1;
                    }
                }
                else if(dis < 0){
                    if(flag == 1){
                        count_ans += 1;
                        flag = 0;
                    }
                    else if(flag == 0) continue;
                }
                else continue;
            }
            if(flag == -1) cout << "0" << endl;
            else cout << count_ans << endl;
    }
    return 0;
}

Go solution:
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
	"strings"
)

func main() {
	scanner := bufio.NewScanner(os.Stdin)
	output := []int{}

	for {
		scanner.Scan()
		line := scanner.Text()
		n, err := strconv.Atoi(line)
		if err != nil || n == 0 {
			break
		}

		scanner.Scan()
		aLine := scanner.Text()
		aStrs := strings.Fields(aLine)
		A := make([]int, n)
		for i := 0; i < n; i++ {
			A[i], _ = strconv.Atoi(aStrs[i])
		}

		scanner.Scan()
		bLine := scanner.Text()
		bStrs := strings.Fields(bLine)
		B := make([]int, n)
		for i := 0; i < n; i++ {
			B[i], _ = strconv.Atoi(bStrs[i])
		}

		aTotal, bTotal := 0, 0
		prevStatus := 0 // 0: tie, 1: A leads, 2: B leads
		overtakes := 0

		for i := 0; i < n; i++ {
			aTotal += A[i]
			bTotal += B[i]

			currentStatus := 0
			if aTotal > bTotal {
				currentStatus = 1
			} else if bTotal > aTotal {
				currentStatus = 2
			}

			// Count overtakes when status changes from non-tie to different non-tie
			if prevStatus != 0 && currentStatus != 0 && currentStatus != prevStatus {
				overtakes++
			}

			// Update previous status, but keep it when current status is tie
			if currentStatus != 0 {
				prevStatus = currentStatus
			}
		}

		output = append(output, overtakes)
	}

	for _, ans := range output {
		fmt.Println(ans)
	}
}

Java solution:
import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        List<Integer> results = new ArrayList<>();
        
        while (true) {
            String line = br.readLine();
            if (line == null) break;
            
            line = line.trim();
            if (line.isEmpty()) continue;
            
            int n = Integer.parseInt(line);
            if (n == 0) break;
            
            // Read runner A's distances
            String[] aStr = br.readLine().trim().split("\\s+");
            int[] a = new int[n];
            for (int i = 0; i < n; i++) {
                a[i] = Integer.parseInt(aStr[i]);
            }
            
            // Read runner B's distances
            String[] bStr = br.readLine().trim().split("\\s+");
            int[] b = new int[n];
            for (int i = 0; i < n; i++) {
                b[i] = Integer.parseInt(bStr[i]);
            }
            
            int totalA = 0, totalB = 0;
            int leader = 0; // 0 = tie, 1 = A leads, 2 = B leads
            int overtakes = 0;
            
            for (int i = 0; i < n; i++) {
                totalA += a[i];
                totalB += b[i];
                
                // Check for overtaking only if there was a previous leader
                if (leader != 0) {
                    if (leader == 1 && totalB > totalA) {
                        overtakes++;
                    } else if (leader == 2 && totalA > totalB) {
                        overtakes++;
                    }
                }
                
                // Update leader status
                if (totalA > totalB) {
                    leader = 1;
                } else if (totalB > totalA) {
                    leader = 2;
                }
                // Note: We don't reset leader to 0 on ties to maintain last known leader
            }
            
            results.add(overtakes);
        }
        
        // Output all results
        for (int result : results) {
            System.out.println(result);
        }
    }
}

JavaScript solution:
const readline = require('readline');

const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout,
    terminal: false
});

let inputLines = [];
let currentLine = 0;

rl.on('line', (line) => {
    if (line.trim() !== '') {
        inputLines.push(line.trim());
    }
});

rl.on('close', () => {
    processInput();
});

function processInput() {
    const output = [];
    currentLine = 0;
    
    while (currentLine < inputLines.length) {
        const N = parseInt(inputLines[currentLine++]);
        if (N === 0) break;
        
        const A = inputLines[currentLine++].split(/\s+/).map(Number);
        const B = inputLines[currentLine++].split(/\s+/).map(Number);
        
        let aTotal = 0, bTotal = 0;
        let prevLeader = null; // null: initial state, 1: A leads, 2: B leads
        let overtakes = 0;
        
        for (let i = 0; i < N; i++) {
            aTotal += A[i];
            bTotal += B[i];
            
            let currentLeader;
            if (aTotal > bTotal) {
                currentLeader = 1;
            } else if (bTotal > aTotal) {
                currentLeader = 2;
            } else {
                currentLeader = null;
            }
            
            // Only count overtakes when there's a change from a clear leader to another
            if (prevLeader !== null && currentLeader !== null && currentLeader !== prevLeader) {
                overtakes++;
            }
            
            // Update previous leader only when there's a clear leader (not tie)
            if (currentLeader !== null) {
                prevLeader = currentLeader;
            }
        }
        
        output.push(overtakes);
    }
    
    console.log(output.join('\n'));
}

Python solution:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 8)

output = []

while True:
    N = int(input())
    if N == 0: break
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))

    a, b = 0, 0
    # 0: 引き分け, 1: Aの勝ち, 2: Bの勝ち
    status = 0
    ans = 0

    for i in range(N):
        a += A[i]
        b += B[i]
        if status == 1:
            if b > a: ans += 1
        elif status == 2:
            if a > b: ans += 1
    
        if a > b: status = 1
        if a < b: status = 2
    
    output.append(ans)

for ans in output:
    print(ans)

Ruby solution:
while true
    n = gets.to_i
    break if n == 0
    a = [0] + gets.chomp.split.map(&:to_i)
    b = [0] + gets.chomp.split.map(&:to_i)
    leader, count = nil, 0
    1.upto(n){|i|
        a[i] += a[i-1]
        b[i] += b[i-1]
        if a[i] > b[i]
            count += 1 if leader == "B"
            leader = "A"
        elsif a[i] < b[i]
            count += 1 if leader == "A"
            leader = "B"
        end
    }
    puts count
end