The 2025-2026 ICPC RSU Oklahoma - Intercontinental Invitational Programming Contest

Problem Statement

A horseshoe is thrown onto a board and you must determine if it is a winner. A horseshoe is a ringer if it is around a stake. A horseshoe is a leaner if it is leaning against the stake. A horseshoe is a ringer if it is within a certain distance from the stake center.

Given the positions of horseshoes and the stake, determine how many horseshoes are ringers and how many are leaners. Calculate the game score based on NHPA rules.

Input

The first line contains the position of the stake (x, y). The next N lines contain the positions of horseshoes. For each horseshoe, determine if it is a ringer, leaner, or neither.

Output

Output the score for each team following official horseshoe tournament rules.

Sample Input

Stake at (0, 0)
Horseshoe 1: (0.5, 0.5)
Horseshoe 2: (3.5, 0)
Horseshoe 3: (-0.1, 0.1)

Solution Approach

This problem requires geometric calculations and understanding of horseshoe scoring rules. Implement distance calculations and boundary checking to classify each horseshoe as a ringer, leaner, or invalid throw.

Problem Statement

A game is played with a list of numbers. Two players take turns removing elements from either end of the list. The score of a player is the sum of all numbers they collect. Find the maximum score the first player can achieve with optimal play from both players.

Input

The first line contains N, the length of the list. The second line contains N space-separated integers representing the list.

Output

The maximum score the first player can achieve.

Sample Input

5
10 20 30 40 50

Sample Output

80

Solution Approach

Use dynamic programming with game theory. Create a DP table where dp[i][j] represents the maximum score the current player can achieve from elements i to j. Consider both taking from the left and right ends.

Problem Statement

Even numbers can be expressed as sums of distinct primes. Find the number of ways to express a given even number as a sum of 2, 4, or 6 distinct primes. Two representations are different if they use different sets of primes.

Input

The first line contains T, the number of test cases. Each test case contains an even number N.

Output

For each test case, output the total number of ways to express N as the sum of 2, 4, or 6 distinct primes.

Sample Input

2
12
20

Sample Output

1
3

Solution Approach

Generate all primes up to N using Sieve of Eratosthenes. Then use combinations and subset generation to find all valid representations. This is a combinatorial problem requiring efficient subset enumeration.

Problem Statement

Find the length of the repeating cycle in the decimal expansion of a fraction a/b. The decimal representation may have a non-repeating part followed by a repeating cycle.

Input

Two integers a and b representing the fraction a/b where 0 < a < b and b is not divisible by 2 or 5.

Output

The length of the shortest repeating cycle in the decimal expansion of a/b.

Sample Input

1 6

Sample Output

1

Solution Approach

Use long division and track remainders. When a remainder repeats, you've found the cycle. The position of the repeated remainder tells you the cycle length. This requires careful tracking of the division process and remainder history.

Problem Statement

A king on a chessboard starts at position (0, 0) and needs to reach position (N, N). The king can move one square in any direction (including diagonals). Some squares are blocked. Find the minimum number of moves required to reach the destination, or determine if it's impossible.

Input

The first line contains N. The next N×N grid contains '.' for passable and '#' for blocked squares.

Output

The minimum number of moves to reach (N, N), or -1 if impossible.

Sample Input

5
.....
.###.
.#.#.
.###.
.....

Sample Output

8

Solution Approach

Use BFS (Breadth-First Search) to find the shortest path. Since the king can move in 8 directions, add all valid neighbors to the queue. Track visited squares to avoid revisiting them.

Problem Statement

In a trivia game, you answer N questions sequentially. Each question has a correct answer and an incorrect answer. You gain points for correct answers and lose points for incorrect answers. Your goal is to determine the maximum score possible given a strategy.

Input

The first line contains N. For each question, you receive the points for a correct answer and the penalty for an incorrect answer. You know the probability of answering each question correctly based on your knowledge.

Output

The expected maximum score using an optimal strategy.

Sample Input

3
+10 -5
+20 -10
+15 -7

Sample Output

35

Solution Approach

This problem combines game theory with dynamic programming. For each question, decide whether to answer or skip based on expected value. Use memoization to track optimal decisions from each state forward through the remaining questions.