CCC '17 S1 - Sum Game

View as PDF

Submit solution


Points: 3
Time limit: 1.0s
Memory limit: 256M

Problem type

Annie has two favourite baseball teams: the Swifts and the Semaphores. She has followed them throughout the season, which is now over. The season lasted for N days. Both teams played exactly one game on each day.

For each day, Annie recorded the number of runs scored by the Swifts on that day. She also recorded this information for the Semaphores.

She would like you to determine the largest integer K such that K \leq N and the Swifts and the Semaphores had scored the same total number of runs K days after the start of the season. The total number of runs scored by a team after K days is the sum of the number of runs scored by the team in all games before or on the K-th day.

For example, if the Swifts and the Semaphores have the same total number of runs at the end of the season, then you should output N. If the Swifts and the Semaphores never had the same number of runs after K games, for any value of K \leq N, then output 0.

Input Specification

The first line of input will contain an integer N\ (1 \leq N \leq 100\,000). The second line will contain N space-separated non-negative integers representing the number of runs scored by the Swifts on each day, in order. The third line will contain N space-separated non-negative integers representing the number of runs scored by the Semaphores on each day, in order. You may assume that each team scored at most 20 runs in any single game.

For 7 of the 15 points available, N \leq 1\,000.

Output Specification

Output the largest integer K such that K \leq N and the Swifts and the Semaphores have the same total number of runs after K days.

Sample Input 1

3
1 3 3
2 2 6

Sample Output 1

2

Explanation for Sample Output 1

After 2 days, each team had scored a total of 4 runs.

Sample Input 2

3
1 2 3
4 5 6

Sample Output 2

0

Explanation for Sample Output 2

The only time when the Swifts and the Semaphores had scored the same number of runs was the beginning of the season.

Sample Input 3

4
1 2 3 4
1 3 2 4

Sample Output 3

4

Explanation for Sample Output 3

The Swifts and Semaphores have the same number of total runs after the first game, and after the third game, and after the fourth game. We take the largest of these values (1, 3 and 4) and output 4.


Comments


  • 1
    Kevin03  commented on Jan. 6, 2019, 9:45 a.m. edited

    I can't get test case 3 in batch 1 in java. Someone help`pls


    • 1
      magicalsoup  commented on Jan. 6, 2019, 6:06 p.m.

      i checked your code with java 8, it works, in the language section, just choose java 8 and you should get full AC


    • 3
      AlanL  commented on Jan. 6, 2019, 4:48 p.m.

      I don't see anything wrong with your code, so I would suggest trying java 8 as well because java 8 should be a bit faster than java 9(I think). Submit a few times as well, because the judges do not always have consistent times so you may exceed the time limit with the code, but pass on another time. And, if all fails, consider learning how to used BufferedReader.


  • 3
    AidanB  commented on Oct. 6, 2018, 10:20 p.m.

    If you're getting a TLE in java, make sure you use a buffered reader.