Trust Coding : Programming

Lab 1 to 6 (18 Hours)

1 Problem Statement

This is one of the simplest problems in competitive programming.

You are required to print:

Hello World!

No input is given, and no processing is required.

Input Format

There is no input.

Output Format

Print exactly:

Hello World!

including correct capitalization and punctuation.

Key Idea

This problem is purely for:

Checking environment setup
Understanding input/output handling
Getting familiar with an online judge

There is no algorithm involved.

Algorithm

1. Print the string "Hello World!"

2. End program

2 Problem Statement

A boy wants to divide a watermelon of weight w kilograms into two parts such that:

Both parts have positive integer weights.
Both parts have even weights.

Determine whether this is possible.

Example 1

Input

Output

YES

Explanation

8 = 4 + 4

Both parts have even weights.

Example 2

Input

Output

YES

Explanation

6 = 2 + 4

Example 3

Input

Output

Explanation

The only possible division is:

2 = 1 + 1

Both parts are odd, so the answer is NO.

Example 4

Input

Output

Since 5 is an odd number, it cannot be divided into two even integers.

Key Observation

Two even numbers always add up to an even number.

Therefore:

If w is odd → Impossible.
If w = 2 → Impossible.
Otherwise → Possible.

Hence, the required condition is:

w > 2 && w % 2 == 0

Algorithm

1. Read the value of w.

2. Create an object of the Watermelon class.

3. Call the member function canDivide().

4. If it returns true, print YES.

5. Otherwise, print NO.

Dry Run

Example 1

Input

Execution

weight = 8

8 > 2 → True

8 % 2 == 0 → True

Output → YES

Example 2

Input

Execution

weight = 2

2 > 2 → False

Output → NO

Example 3

Input

Execution

weight = 7

7 % 2 == 1

Output → NO

Why w > 2?

Consider these examples:

4 = 2 + 2 ✔

6 = 2 + 4 ✔

8 = 4 + 4 ✔

10 = 2 + 8 ✔

But:

2 = 1 + 1 ✘

The two parts are odd, so the answer is NO.

Common Mistake

Incorrect solution:

if (weight % 2 == 0)

cout << "YES";

This prints YES for weight = 2, which is incorrect.

Correct solution:

if (weight > 2 && weight % 2 == 0)

Final Rule

A watermelon can be divided into two positive even-weight parts if and only if:

weight > 2 && weight % 2 == 0

3 Problem Statement

Sometimes words like "localization" or "internationalization" are too long to write repeatedly. To make writing easier, a long word is abbreviated as follows:

Keep the first character.
Replace the middle characters with the number of omitted characters.
Keep the last character.

For example:

localization → l10n
internationalization → i18n

Given n words, abbreviate each word if its length is greater than 10. Otherwise, print the word unchanged.

Input Format

The first line contains an integer n (the number of words).
Each of the next n lines contains one word.

Output Format

For each word:

If its length is 10 or less, print it unchanged.
Otherwise, print its abbreviation.

Sample Input

word

localization

internationalization

apple

Sample Output

word

l10n

i18n

apple

Explanation

Word 1

word

Length = 4

Since the length is less than or equal to 10, print it as it is.

Output:

word

Word 2

localization

Length = 12

First letter = l
Middle letters = 10
Last letter = n

Output:

l10n

Word 3

internationalization

Length = 20

First letter = i
Middle letters = 18
Last letter = n

Output:

i18n

Key Observation

For every word:

If length ≤ 10, print the original word.
Otherwise,

First Letter + (Length − 2) + Last Letter

Algorithm

1. Read integer n.

2. Repeat n times:

o Read a word.

o Find its length.

o If the length is greater than 10:

§ Print the first character.

§ Print length - 2.

§ Print the last character.

o Otherwise, print the original word.

Dry Run

Input

localization

Length = 12

First Character = l

Middle Characters = 10

Last Character = n

Output

l10n

Input

apple

Length = 5

Since length ≤ 10,

Output

apple

Common Mistakes

Incorrect

Using:

word.length() - 1

instead of

word.length() - 2

The abbreviation should count only the omitted middle characters.

Incorrect

Abbreviating every word regardless of length.

Words with 10 or fewer characters must remain unchanged.

Final Rule

Length ≤ 10

Print the original word.

Otherwise print

First Character + (Length − 2) + Last Character

4 Problem Statement

Three friends, Petya, Vasya, and Tonya, are preparing for a programming contest. They have n problems to solve.

For each problem:

Each friend either knows the solution (1) or does not know the solution (0).
The team will solve a problem only if at least two of the three friends are sure about the solution.

Your task is to determine how many problems the team will solve.

Input Format

The first line contains an integer n — the number of problems.
Each of the next n lines contains three integers (0 or 1), representing whether Petya, Vasya, and Tonya know the solution.

Output Format

Print a single integer — the number of problems the team will solve.

Sample Input

1 1 0

1 1 1

1 0 0

Sample Output

Explanation

Problem 1

1 1 0

Two students know the solution.

✔ The team solves it.

Problem 2

1 1 1

All three students know the solution.

✔ The team solves it.

Problem 3

1 0 0

Only one student knows the solution.

✘ The team does not solve it.

Therefore, the answer is

Key Observation

For every problem,

Calculate

Petya + Vasya + Tonya

If the sum is 2 or 3, the team will solve the problem.

Algorithm

1. Read integer n.

2. Initialize count = 0.

3. Repeat n times:

o Read three integers.

o Calculate their sum.

o If the sum is at least 2, increment count.

4. Print count.

Sample Input

1 1 0

1 1 1

1 0 0

Problem 1

1 + 1 + 0 = 2

Team solves it.

Current Answer = 1

Problem 2

1 + 1 + 1 = 3

Team solves it.

Current Answer = 2

Problem 3

1 + 0 + 0 = 1

Less than 2.

Team cannot solve it.

Final Answer =

Common Mistakes

Mistake 1

Using

petya + vasya + tonya > 2

This ignores cases where exactly 2 students know the solution.

Correct condition:

petya + vasya + tonya >= 2

Mistake 2

Printing the result for every problem instead of counting the total number of solvable problems.

The problem asks for one final count, not individual outputs.

Final Rule

For every problem,

If (Petya + Vasya + Tonya ≥ 2)

Solve the problem

Else

Skip the problem

5 Problem Statement

You are given a variable x, initially set to 0.

You are given n statements. Each statement is one of the following:

++X or X++ → increment x by 1
--X or X-- → decrement x by 1

Your task is to compute the final value of x after executing all statements.

Input Format

The first line contains an integer n — number of statements.
Each of the next n lines contains one statement.

Output Format

Print the final value of x.

Sample Input

X++

++X

X--

Sample Output

Explanation

Initial value:

x = 0

Step 1

X++ → x = 1

Step 2

++X → x = 2

Step 3

X-- → x = 1

Final answer:

Key Observation

If the string contains "++" → increment
If the string contains "--" → decrement

We do not need to care about the position of X.

Algorithm

1. Initialize x = 0

2. Read n

3. For each statement:

o If it contains "++" → x++

o Else → x--

4. Print x

Common Mistakes

Mistake 1

Checking full string equality:

if (s == "X++")

This misses cases like ++X.

Correct approach:

if (s.find("++") != string::npos)

Mistake 2

Forgetting initial value:

x must start from 0

Final Rule

For each statement:

if contains "++" → x++

else → x--

5.2 Problem Statement

You are given a 5 × 5 matrix containing only 0s and exactly one 1.

Your task is to move the 1 to the center of the matrix (position (3,3) in 1-based indexing) using the minimum number of moves.

In one move, you can swap adjacent rows or columns (equivalent to moving the 1 up, down, left, or right by 1 step).

Return the minimum number of moves required.

Input Format

5 lines, each containing 5 integers (0 or 1).
Exactly one cell contains 1.

Output Format

Print a single integer — the minimum number of moves.

Key Observation

The problem is simply the Manhattan distance between:

Current position of 1: (i, j)
Target position: (3, 3)

So:

moves = |i - 3| + |j - 3|

Algorithm

1. Read the 5×5 matrix.

2. Find the position (i, j) of 1.

3. Compute Manhattan distance to (3, 3).

4. Print the result.

Example

Input

0 0 0 0 0

0 0 1 0 0

0 0 0 0 0

Position of 1

(2, 2)

Moves

|2 - 2| + |2 - 2| = 0

Output

Common Mistakes

Forgetting that indexing is 0-based in C++
Using (3,3) instead of (2,2)
Not storing the position of 1 correctly

Final Rule

Answer = |row - 2| + |col - 2|

Conclusion

This problem is a classic introduction to grid problems and teaches:

Matrix traversal
Coordinate geometry in grids
Manhattan distance
Basic object-oriented design in C++

6 Problem Statement

In a programming contest, participants are ranked by score in non-increasing order (sorted from highest to lowest).

A participant advances to the next round if:

Their score is greater than 0, and
Their score is greater than or equal to the score of the participant in k-th place

Given the number of participants and their scores, determine how many advance to the next round.

Input Format

First line: two integers n and k

n = number of participants
k = position threshold

Second line: n integers representing scores in non-increasing order

Output Format

Print a single integer — number of participants who advance.

Key Idea

Let the score of the k-th participant be:

threshold = a[k - 1]

A participant advances if:

score > 0
score >= threshold

Algorithm

1. Read n and k

2. Read array of scores

3. Set threshold = score[k - 1]

4. Count all scores satisfying:

o score >= threshold

o score > 0

5. Print count

Example

Input

8 5

10 9 8 7 7 7 5 5

Threshold

k = 5 → threshold = 7

Valid scores

10 ✓

9 ✓

8 ✓

7 ✓

5 ✗ (less than 7)

Output

Common Mistakes

Forgetting to exclude scores equal to 0
Using k instead of k - 1 (indexing error)
Not handling boundary conditions properly

Final Rule

A participant qualifies if:

score >= score[k - 1] AND score > 0

7 Problem Statement

Petya loves comparing strings, but he is not sure about case sensitivity.

Given two strings, determine their lexicographical comparison ignoring case.

If the first string is less than the second → print -1
If the first string is greater than the second → print 1
If both are equal → print 0

The comparison is case-insensitive, meaning uppercase and lowercase letters are treated as the same.

Input Format

Two strings are given, each on a separate line.

Output Format

Print:

-1, 0, or 1 based on comparison.

Key Idea

Convert both strings to the same case (lowercase or uppercase), then compare them lexicographically.

Algorithm

1. Read two strings a and b

2. Convert both to lowercase

3. Compare:

o If a < b → print -1

o If a > b → print 1

o Else → print 0

Example

Input

aaaa

aaaA

After conversion

aaaa

Output

Common Mistakes

Forgetting case conversion
Using ASCII comparison without normalization
Comparing original strings directly

Final Rule

Convert both strings to lowercase → compare lexicographically

8 Problem Statement

You are given several integers. For each integer, determine whether it is even or odd.

For every number:

If it is even → print "even"
If it is odd → print "odd"

Input Format

First line contains an integer n, the number of test cases.
The next n lines each contain a single integer.

Output Format

For each integer, print either:

even
odd

on a separate line.

Key Idea

A number is:

Even if number % 2 == 0
Odd otherwise

Algorithm

Read integer n
Repeat n times:

Read number x
If x % 2 == 0, print "even"
Else print "odd"

Example

Input

Output

even

odd

even

OOP Concepts Used

Class: OdditiesChecker
Private data member: value
Constructor: initializes value
Member function: check()
Encapsulation of logic inside object

Common Mistakes

Forgetting modulo operation % 2
Printing integers instead of strings
Not handling zero correctly (0 is even)

Final Rule

If value % 2 == 0 → even

Else → odd

9 Problem Statement

In this problem, you are given a compound name written in the format:

Word1-Word2-Word3-...-WordN

Your task is to create an abbreviation by taking the first letter of each word and concatenating them together.

Input Format

A single line containing a string with words separated by hyphens (-).

Output Format

Print the abbreviation formed by the first letter of each word.

Example

Input

Knuth-Morris-Pratt

Output

KMP

Another Example

Input

Portable-Network-Graphics

Output

PNG

Key Idea

We only need to:

Split the string by -
Take the first character of each segment
Combine them

Algorithm

Read input string s
Initialize an empty result string
Traverse the string:

If current character is the first character OR previous character is -, take it

Print the result

Example Walkthrough

Input

Portable-Network-Graphics

Processing

Word	First letter
Portable	P
Network	N
Graphics	G

Output

PNG

Common Mistakes

Forgetting to check i == 0
Splitting incorrectly with spaces instead of -
Not handling single-word input properly

Final Rule

Take the first character of the string and every character that follows a '-'

10 Problem Statement

You are given three integers. However, their order is unknown.

You are also given a string containing the characters:

A B C

The task is:

Sort the three numbers in ascending order
Then rearrange them according to the given pattern string

For example, if the sorted numbers are:

x ≤ y ≤ z

and the string is "CBA", the output should be:

z y x

Input Format

First line: three integers
Second line: a string of length 3 containing only A, B, C

Output Format

Print the three numbers in the order specified by the string.

Key Idea

Sort the three numbers.
Map:

A → smallest
B → middle
C → largest

Output according to the given pattern.

Algorithm

Read three integers into an array
Sort the array
Read the pattern string
For each character in the string:

Print corresponding number

Print result

Example

Input

6 4 2

ABC

Sorted

2 4 6

Output

2 4 6

Input

6 4 2

CBA

Output

6 4 2

Common Mistakes

Forgetting to sort the array
Misinterpreting mapping of A, B, C
Printing without spaces or in wrong order

Final Rule

A → smallest

B → middle

C → largest

11 Problem Statement

In baseball statistics, a player’s performance is measured using an average.

You are given n at-bats, where each at-bat is either:

A number representing the number of bases gained (0–4), or
-1 which means the player did not bat (this should be ignored)

Your task is to compute the player's slugging percentage, defined as:

slugging percentage = (sum of valid bases) / (number of valid at-bats)

Ignore all -1 values.

Input Format

First line: integer n
Second line: n integers representing at-bats

Output Format

Print the slugging percentage as a floating-point number.

Key Idea

We only consider values not equal to -1.

So:

Sum all valid values
Count valid entries
Divide sum by count

Algorithm

Read integer n
Initialize:

sum = 0
count = 0

For each value:

If value != -1:

add to sum
increment count

Print sum / count

Example

Input

3 2 -1 4 1

Valid values

3 + 2 + 4 + 1 = 10

count = 4

Output

2.5

Common Mistakes

Including -1 in calculations
Forgetting type casting to double
Division by zero (if all values are -1 — though not in constraints)

Final Rule

Ignore -1 values, then compute average of remaining numbers

12 Problem Statement

You are given a stream of integers. After reading each new integer, you must output the median of all numbers seen so far.

If the count of numbers is odd → median is the middle element
If the count is even → median is the average of the two middle elements (integer division is not used; use float/double)

Input Format

A sequence of integers, one per line
Input ends at EOF

Output Format

For each input number, print the current median.

Key Idea

Maintain a sorted structure of all numbers seen so far and compute median dynamically.

Efficient approach (ICPC standard):

Use two heaps:

Max-heap for lower half
Min-heap for upper half

But for beginner level, we can use a sorted array (simple but slower).

Simple Algorithm (Beginner Version)

Read numbers one by one
Insert into a list/vector
Sort the list
Compute median:

If odd → middle element
If even → average of two middle elements

Print result

Example

Input

Step-by-step

Numbers	Sorted	Median
1	[1]	1
1,3	[1,3]	2
1,3,4	[1,3,4]	3
1,3,4,2	[1,2,3,4]	2.5

Output

2.5

Common Mistakes

Forgetting to sort before computing median
Using integer division instead of floating point
Not handling even-sized cases correctly
Assuming fixed input size (problem uses EOF)

Final Rule

Median = middle element (odd) OR average of two middle elements (even)

13 Problem Statement

For any positive integer n, define the following process:

If n is even, divide it by 2 → n = n / 2
If n is odd, multiply by 3 and add 1 → n = 3n + 1

Repeat this process until n becomes 1.

The cycle length of a number is the number of terms in the sequence starting from n and ending at 1.

Task

Given two integers i and j, compute:

The maximum cycle length for all numbers between i and j (inclusive)

Input Format

Each line contains two integers:

i j

Input ends at EOF.

Output Format

For each pair (i, j), print:

i j max_cycle_length

Important Note

If i > j, swap them before processing.

Key Idea

We compute the cycle length for every number in the range and take the maximum.

To optimize:

Use memoization (caching) to store previously computed cycle lengths.

Algorithm

Read i and j
Swap if needed
For each number from i to j:

Compute cycle length using Collatz rules
Track maximum

Print result

Example

Input

1 10

Cycle lengths (sample)

n	Cycle Length
1	1
2	2
3	8
7	17

Output

1 10 20

Common Mistakes

Not swapping i and j
Overflow for large n (use long long)
Not using memoization (TLE risk)
Incorrect cycle counting

14 Problem Statement

In plain text, quotation marks are written as:

But in TEX typesetting, quotes must be replaced with:

Opening quote → `` (two backticks)
Closing quote → '' (two single quotes)

Your task is to convert all straight double quotes in the input into TEX-style quotes, preserving all other characters.

Input Format

Input consists of multiple lines of text.
Each " character must be replaced accordingly.

Output Format

Print the modified text with TEX-style quotes.

Key Idea

We alternate between:

Opening quote → `` (two backticks)
Closing quote → '' (two apostrophes)

We track whether we are inside a quoted section or not.

Algorithm

Initialize a boolean flag open = true
Read input character by character
If character is ":

If open is true → print ```` (two backticks)
Else → print ''
Toggle open

Otherwise, print the character as it is

Example

Input

"To be or not to be," she said.

Output

``To be or not to be,'' she said.

Common Mistakes

Using string input instead of character stream
Not toggling quote state
Replacing quotes globally without order tracking
Forgetting spaces/newlines preservation

Final Rule

First " → ``

Second " → ''

Repeat alternately

15 Problem Statement

A sequence of n integers is called a Jolly Jumper if the set of absolute differences between successive elements contains all integers from:

1 to n-1

Each difference must appear exactly once, regardless of order.

Example

Input

4 1 4 2 3

Differences

|1-4| = 3

|4-2| = 2

|2-3| = 1

We get: {1, 2, 3} → valid → Jolly

Input Format

Each line contains:

An integer n
Followed by n integers

Input ends at EOF.

Output Format

For each sequence, print:

Jolly if it is a Jolly Jumper
Not jolly otherwise

Key Idea

We check:

Compute absolute differences between consecutive elements
Mark which differences appear
Ensure all values from 1 to n-1 exist

Algorithm

Read n
Read array of size n
Create boolean array seen[n]
For each i from 0 to n-2:

compute diff = abs(a[i] - a[i+1])
if diff in range [1, n-1], mark it

Check if all values from 1 to n-1 are marked

Example Walkthrough

Input

5 1 4 2 3 5

Differences

|1-4| = 3

|4-2| = 2

|2-3| = 1

|3-5| = 2

Set = {1,2,3} → valid → Jolly

Common Mistakes

Forgetting absolute value
Not checking full range 1 to n-1
Indexing errors in seen[]
Not resetting array for each test case

Final Rule

A sequence is Jolly if all differences 1..n-1 appear exactly once

16 Problem Statement

You are given a stream of integers. After each new integer is read, you must output the median of all numbers seen so far.

If the number of elements is odd → median is the middle value.
If the number of elements is even → median is the average of the two middle values.

You must print the median after every input number.

Input Format

A sequence of integers, one per line.

Input continues until EOF.

Output Format

After reading each number, print the current median.

Key Idea

We maintain a dynamic median as numbers arrive.

Efficient approach (ICPC standard):

Max-heap → lower half
Min-heap → upper half

This keeps middle elements accessible in O(log n).

Algorithm (Optimal)

Maintain two heaps:

maxHeap (lower half)
minHeap (upper half)

For each number:

Insert into appropriate heap
Balance heaps (size difference ≤ 1)

Compute median:

If equal size → average of roots
Else → root of larger heap

Example

Input

Processing

Numbers	Median
1	1
1,3	2
1,3,4	3
1,3,4,2	2.5

Output

2.5

Final Rule

Maintain two heaps and balance them to compute median dynamically

17 Problem Statement

You are given an integer n. You must repeatedly apply the following rules until n becomes 1:

If n is even, divide it by 2 → n = n / 2
If n is odd, multiply it by 3 and add 1 → n = 3n + 1

Print all values of n in the sequence, starting from the initial value.

Input Format

A single integer n

Output Format

Print the full sequence of numbers, starting from n and ending at 1, separated by spaces.

Key Idea

This is the classic Collatz sequence. We repeatedly apply a deterministic rule until reaching 1.

Algorithm

Read n
While n != 1:

Print n
If n is even → n /= 2
Else → n = 3n + 1

Print 1

Example

Input

Process

3 → 10 → 5 → 16 → 8 → 4 → 2 → 1

Output

3 10 5 16 8 4 2 1

Final Rule

If n is even → n = n / 2

If n is odd → n = 3n + 1

Repeat until n = 1

18 Problem Statement

You are given all integers from 1 to n, but one number is missing.

You are given n − 1 distinct numbers. Your task is to find the missing number.

Input Format

First line: integer n
Second line: n − 1 integers, all distinct, in range 1 to n

Output Format

Print the missing number.

Key Idea

Instead of checking each number, we use a mathematical observation:

Method 1: Sum Formula

Sum of first n natural numbers:

total = n(n + 1) / 2

Missing number:

missing = total - sum_of_given_numbers

Method 2: XOR Trick (Alternative)

a ^ a = 0
a ^ 0 = a

XOR all numbers from 1 to n and XOR all input numbers → result is missing number.

Algorithm (Sum Method)

Read n
Compute expected sum = n * (n + 1) / 2
Read all n - 1 numbers and compute actual sum
Return difference

Example

Input

2 3 1 5

Calculation

Total = 15
Given = 11

Output

Final Rule

Missing = (1 to n sum) − (given numbers sum)

19 Problem Statement

You are given a DNA string consisting of characters:

A, C, G, T

Your task is to find the length of the longest substring where the same character appears consecutively.

Input Format

A single string s

Output Format

Print one integer — the maximum length of a contiguous repeating substring.

Key Idea

We scan the string and count consecutive equal characters.

Whenever the character changes, we reset the counter.

We maintain a global maximum.

Algorithm

Read string s
Initialize:

current = 1
best = 1

Loop from index 1 to end:

If s[i] == s[i-1] → increment current
Else → reset current = 1
Update best = max(best, current)

Print best

Example

Input

ATTCGGGA

Output

Explanation:

TT → 2
GGG → 3 (maximum)

20 Problem Statement

You are given an array of n integers. Your task is to make the array non-decreasing:

a1 ≤ a2 ≤ a3 ≤ ... ≤ an

You can increase any element any number of times.

Find the minimum total number of increments needed.

Input Format

First line: integer n
Second line: n integers

Output Format

Print one integer — the minimum number of increments required.

Key Idea

We traverse the array from left to right.

Whenever we find:

a[i] < a[i - 1]

We increase a[i] to match a[i - 1].

We accumulate the total increments.

Algorithm

Read n
Read array a
Initialize moves = 0
For each i from 1 to n-1:

If a[i] < a[i-1]:

moves += (a[i-1] - a[i])
set a[i] = a[i-1]

Print moves

Time Complexity

O(n)

C++ Solution (OOP Style)

#include <iostream>

using namespace std;

class IncreasingArray {

private:

long long arr[200000];

int n;

public:

IncreasingArray(int size) {

n = size;

}

void readInput() {

for (int i = 0; i < n; i++) {

cin >> arr[i];

}

long long makeIncreasing() {

long long moves = 0;

for (int i = 1; i < n; i++) {

if (arr[i] < arr[i - 1]) {

moves += (arr[i - 1] - arr[i]);

arr[i] = arr[i - 1];

}

return moves;

}

};

int main() {

int n;

cin >> n;

IncreasingArray obj(n);

obj.readInput();

cout << obj.makeIncreasing() << endl;

return 0;

}

Explanation

Step 1: Read array

Example:

3 2 5 1 7

Step 2: Fix violations

We ensure each element is at least as large as the previous one.

Step 3: Count increments

Step	Array	Moves
start	3 2 5 1 7	0
fix 2	3 3 5 1 7	1
fix 1	3 3 5 5 7	4

Example

Input

3 2 5 1 7

Output

OOP Concepts Used

Class: IncreasingArray
Private data member: arr, n
Constructor: initializes size
Member functions:

readInput()
makeIncreasing()

Encapsulation of logic

Common Mistakes

Not updating array after increment
Using wrong condition (> instead of <)
Using int instead of long long for moves
Missing left-to-right traversal requirement

Final Rule

If a[i] < a[i-1], increase a[i] to a[i-1] and count the difference

Conclusion

This problem is a key greedy problem that teaches:

Array traversal
Greedy adjustment
Prefix dependency handling
Accumulation techniques
Object-oriented programming in C++

It is an essential stepping stone for ICPC-level greedy problems.

21 Problem Statement

You are given an integer n. You must construct a permutation of numbers from 1 to n such that:

No two adjacent numbers differ by 1.

If such a permutation exists, print it. Otherwise, print:

NO SOLUTION

Input Format

A single integer n

Output Format

A valid permutation of 1..n, or
NO SOLUTION if impossible

Key Idea

We must avoid placing consecutive integers next to each other.

Observation:

For n = 1, valid: [1]
For n = 2, 3, impossible
For n ≥ 4, we can construct a solution by:

Strategy:

Print all even numbers first, then all odd numbers.

This avoids adjacent differences of 1.

Algorithm

If n == 1, print 1
If n == 2 or n == 3, print NO SOLUTION
Otherwise:

Print all even numbers from 1..n
Then print all odd numbers from 1..n

Time Complexity

O(n)

C++ Solution (OOP Style)

#include <iostream>

using namespace std;

class Permutations {

private:

int n;

public:

Permutations(int size) {

n = size;

}

void generate() {

if (n == 1) {

cout << 1 << endl;

return;

}

if (n == 2 || n == 3) {

cout << "NO SOLUTION" << endl;

return;

}

// Print even numbers

for (int i = 2; i <= n; i += 2)

cout << i << " ";

// Print odd numbers

for (int i = 1; i <= n; i += 2)

cout << i << " ";

cout << endl;

}

};

int main() {

int n;

cin >> n;

Permutations obj(n);

obj.generate();

return 0;

}

Explanation

Step 1: Handle small cases

n = 2 → impossible

n = 3 → impossible

Because any arrangement will have adjacent numbers differing by 1.

Step 2: Construct valid pattern

Example for n = 6:

Even numbers:

2 4 6

Odd numbers:

1 3 5

Final output:

2 4 6 1 3 5

Example

Input

Output

2 4 1 3 5

OOP Concepts Used

Class: Permutations
Private data member: n
Constructor: initializes value
Member function: generate()
Encapsulation of construction logic

Common Mistakes

Forgetting special cases (n = 2, 3)
Mixing order incorrectly
Not spacing output properly
Trying random permutations instead of constructive approach

Final Rule

Place all even numbers first, then all odd numbers

Conclusion

This problem is a classic constructive algorithm problem that teaches:

Pattern construction
Edge case handling
Modular thinking
Greedy construction
Object-oriented design in C++

It is an important step toward learning constructive problems in ICPC preparation.

Problem Statement

You are given a grid where numbers are arranged in a spiral pattern starting from (1,1):

1 2 9 10

4 3 8 11

5 6 7 12

16 15 14 13

For each query (y, x), you must find the number located at that position.

Input Format

First line: integer t (number of queries)
Next t lines: two integers y x

Output Format

For each query, print the number at position (y, x).

Key Idea

Instead of building the grid, we use a mathematical pattern.

The value depends on the maximum of (x, y):

Let:

n = max(x, y)

We determine the spiral layer and compute based on whether the layer is even or odd.

Pattern Observation

If n is odd:

Numbers increase downward and leftward in that layer

If n is even:

Numbers increase upward and rightward

We compute the base value:

n² - (something)

Formula

If n = max(x, y):

Case 1: n is even

If x == n:

value = n² - y + 1

Else:

value = (n-1)² + x

Case 2: n is odd

If y == n:

value = n² - x + 1

Else:

value = (n-1)² + y

Algorithm

Read number of queries t
For each (y, x):

Compute n = max(x, y)
Apply correct formula based on parity of n

Print result

Time Complexity

O(t)

Each query is solved in constant time.

C++ Solution (OOP Style)

#include <iostream>

using namespace std;

class NumberSpiral {

public:

long long getValue(long long y, long long x) {

long long n = max(x, y);

long long ans;

if (n % 2 == 0) {

if (x == n)

ans = n * n - y + 1;

else

ans = (n - 1) * (n - 1) + x;

} else {

if (y == n)

ans = n * n - x + 1;

else

ans = (n - 1) * (n - 1) + y;

}

return ans;

}

};

int main() {

ios::sync_with_stdio(false);

cin.tie(nullptr);

int t;

cin >> t;

NumberSpiral solver;

while (t--) {

long long y, x;

cin >> y >> x;

cout << solver.getValue(y, x) << "\n";

}

return 0;

}

Explanation

Step 1: Identify layer

n = max(x, y)

Each square layer ends at n².

Step 2: Determine direction

Even layer → pattern goes one way
Odd layer → pattern goes opposite way

Step 3: Compute value in O(1)

No grid construction needed.

Example

Input

1 1

2 3

4 2

Output

OOP Concepts Used

Class: NumberSpiral
Method: getValue()
Encapsulation of formula logic
Stateless design (efficient reuse)

Common Mistakes

Confusing (x, y) order
Using wrong square (n²) base
Not handling parity correctly
Overflow (use long long)

Final Rule

Answer depends on max(x,y) layer and whether it is even or odd

Conclusion

This problem is a classic mathematical pattern problem that teaches:

Grid observation
Mathematical derivation
Constant-time query solving
Pattern recognition
Object-oriented implementation in C++

It is a key problem for developing ICPC-level problem-solving intuition.

Problem Statement

You are given an n × n chessboard. You must determine, for each size k × k (from 1 to n), how many ways you can place two knights such that they do not attack each other.

Key Idea

Two knights attack each other only if they are placed in an L-shape (2 by 1 moves).

Total ways to place two knights:

C(k², 2) = k²(k² - 1) / 2

From this, subtract attacking pairs.

Attacking Positions

A knight attacks in 2 specific relative configurations:

2 × 1 blocks
Each 2×3 or 3×2 rectangle contributes attacking pairs

Number of attacking pairs:

4 × (k - 1) × (k - 2)

Final Formula

For board size k:

answer = k²(k² - 1) / 2 - 4(k - 1)(k - 2)

Algorithm

Read n
For each k from 1 to n:

Compute total placements
Subtract attacking positions

Print result

Time Complexity

O(n)

C++ Solution (OOP Style)

#include <iostream>

using namespace std;

class TwoKnights {

public:

long long countWays(long long k) {

long long total = (k * k) * (k * k - 1) / 2;

long long attack = 0;

if (k > 2)

attack = 4 * (k - 1) * (k - 2);

return total - attack;

}

};

int main() {

long long n;

cin >> n;

TwoKnights solver;

for (long long k = 1; k <= n; k++) {

cout << solver.countWays(k) << "\n";

}

return 0;

}

Explanation

Step 1: Total placements

Choose any 2 squares:

k² choose 2

Step 2: Remove attacking pairs

Each 2×3 or 3×2 region contains 2 attacking pairs per orientation → total:

4(k - 1)(k - 2)

Step 3: Edge cases

For k = 1 → 0
For k = 2 → 6 (no attacks possible)

Example

Input

Output

252

OOP Concepts Used

Class: TwoKnights
Method: countWays()
Encapsulation of combinatorics logic
Stateless reusable design

Common Mistakes

Forgetting k > 2 condition
Overflow (use long long)
Miscounting attacking configurations
Incorrect combinatorics formula

Final Rule

Answer = total ways to choose 2 squares − attacking knight pairs

Conclusion

This problem is an important combinatorics problem that teaches:

Counting techniques
Grid-based reasoning
Subtraction principle
Pattern recognition
Object-oriented implementation in C++

It is a classic ICPC preparation problem for combinatorics fundamentals.

Problem Statement

You are given an integer n. Your task is to split the set:

{1, 2, 3, ..., n}

into two subsets such that:

Both subsets have equal sum, or
If it is impossible, print NO

If possible, print:

YES
Then the elements of each subset

Key Idea

Let total sum be:

S = n(n + 1) / 2

For two equal subsets, we need:

S must be even

If S is odd → impossible.

Construction Strategy

We greedily assign numbers from n → 1 into two sets:

Put a number in set A if it does not exceed remaining sum
Otherwise put it in set B

We aim to make both sums equal to S/2.

Algorithm

Compute total sum S
If S % 2 != 0 → print NO
Target = S / 2
Start from n down to 1:

If i <= target, put in set A and reduce target
Else put in set B

Print both sets

Time Complexity

O(n)

C++ Solution (OOP Style)

#include <iostream>

#include <vector>

using namespace std;

class TwoSets {

private:

vector<int> set1, set2;

public:

void solve(int n) {

long long total = (long long)n * (n + 1) / 2;

if (total % 2 != 0) {

cout << "NO\n";

return;

}

cout << "YES\n";

long long target = total / 2;

for (int i = n; i >= 1; i--) {

if (i <= target) {

set1.push_back(i);

target -= i;

} else {

set2.push_back(i);

}

cout << set1.size() << "\n";

for (int x : set1) cout << x << " ";

cout << "\n";

cout << set2.size() << "\n";

for (int x : set2) cout << x << " ";

cout << "\n";

}

};

int main() {

int n;

cin >> n;

TwoSets solver;

solver.solve(n);

return 0;

}

Explanation

Step 1: Check feasibility

If total sum is odd:

NO solution exists

Step 2: Greedy assignment

We try to build one subset with sum = S/2.

Step 3: Fill second subset automatically

Remaining numbers go to second set.

Example

Input

Total sum

28 → each set must sum to 14

Output (one valid solution)

YES

7 6 1

5 4 3 2

OOP Concepts Used

Class: TwoSets
Private data members: set1, set2
Member function: solve()
Encapsulation of greedy construction logic

Common Mistakes

Forgetting to check sum parity
Not resetting target correctly
Printing incorrect format
Using inefficient subset generation

Final Rule

Split {1..n} into two equal-sum subsets if total sum is even

Conclusion

This problem is a classic greedy + construction problem that teaches:

Mathematical feasibility checking
Greedy subset construction
Partitioning techniques
Output formatting
Object-oriented design in C++

It is a fundamental ICPC-style constructive algorithm problem.

Skills covered

By solving these 25 problems, students will become comfortable with:

Time complexity analysis
Arrays and strings
Basic mathematics
Number theory
Sorting and searching
Prefix sums
Two pointers
Stack and queue
Graph traversal (BFS)
Recursion and backtracking
Dynamic programming basics

This foundation is sufficient for students to start solving ICPC regional-level Div. 2/A–C style problems before progressing to more advanced topics such as segment trees, union-find, shortest paths, and advanced dynamic programming.

Trust Coding : Programming

5.2 Problem Statement

কোন মন্তব্য নেই:

একটি মন্তব্য পোস্ট করুন