The 2025-2026 ICPC RSU Northeast Oklahoma Provincial Programming Contest

Problem Statement

You are climbing a staircase. It takes N steps to reach the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Input

A single integer N representing the number of steps (1 ≤ N ≤ 45).

Output

The number of distinct ways to climb to the top.

Sample Input

3

Sample Output

3

Explanation

There are 3 ways to climb to the top: 1. 1 step + 1 step + 1 step 2. 1 step + 2 steps 3. 2 steps + 1 step

Solution Approach

Use dynamic programming where dp[i] represents the number of ways to reach step i. The recurrence relation is: dp[i] = dp[i-1] + dp[i-2].

Problem Statement

Given an array of integers and a target sum, find two numbers that add up to the target. Return the indices of the two numbers (not the values themselves).

Input

The first line contains an integer N, the size of the array. The second line contains N space-separated integers. The third line contains an integer T, the target sum.

Output

Two space-separated integers representing the indices of the two numbers that sum to the target. Guarantee that exactly one solution exists and you cannot use the same element twice.

Sample Input

4
2 7 11 15
9

Sample Output

0 1

Explanation

The numbers at index 0 and 1 are 2 and 7, which add up to 9.

Solution Approach

Use a hash map to store each number and its index as you iterate through the array. For each number, check if (target - number) exists in the hash map.

Problem Statement

Given a string s, find the longest palindromic substring in s. A palindrome is a word that reads the same forwards and backwards.

Input

A single string s containing only lowercase English letters (1 ≤ length ≤ 1000).

Output

The longest palindromic substring. If there are multiple answers, return any of them.

Sample Input

babad

Sample Output

bab

Note

"aba" is also a valid answer.

Solution Approach

Use the expand-around-center approach: for each possible center (both odd and even length palindromes), expand outward while characters match. Track the longest palindrome found.

Problem Statement

Given a set of positive integers and a target sum, determine if there is a subset of the given set with sum equal to the target sum.

Input

The first line contains two integers N and T, where N is the size of the set and T is the target sum. The second line contains N space-separated positive integers.

Output

Print "Yes" if a subset with the target sum exists, otherwise print "No".

Sample Input

4 7
3 34 4 12

Sample Output

Yes

Explanation

The subset {3, 4} has sum equal to 7.

Solution Approach

Use dynamic programming with a boolean DP table where dp[i][j] represents whether sum j is possible using first i elements. Fill the table based on including or excluding each element.

Problem Statement

You are given different coins with different denominations and an infinite supply of each coin. Find the minimum number of coins needed to make a given amount.

Input

The first line contains two integers N and A, where N is the number of different coin denominations and A is the target amount. The second line contains N space-separated integers representing the coin denominations.

Output

The minimum number of coins needed to make the amount. If it's impossible, return -1.

Sample Input

3 5
1 2 5

Sample Output

1

Explanation

The amount can be made with a single coin of denomination 5.

Solution Approach

Use dynamic programming where dp[i] represents the minimum coins needed to make amount i. For each amount from 1 to A, try using each coin and take the minimum.

Problem Statement

Given an M×N grid of characters and a word, determine if the word exists in the grid. The word must be constructed from letters of sequentially adjacent cells (horizontally, vertically, or diagonally). The same letter cell may not be used more than once in a word.

Input

The first line contains two integers M and N, the dimensions of the grid. The next M lines each contain N characters. The last line contains a string representing the word to search for.

Output

Print "Yes" if the word exists in the grid, otherwise print "No".

Sample Input

3 4
CATS
CACS
RSAD
CAR

Sample Output

Yes

Solution Approach

Use backtracking/DFS. For each cell matching the first character of the word, recursively search for the remaining word in adjacent cells (8 directions). Mark visited cells to prevent reuse and backtrack when no valid path is found.