Trust Coding : Programming

Lab 1 to 6 (18 Hours)

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

Time Complexity

O(1)

C++ Solution (OOP Style)

Even though this problem does not require OOP, we can structure it using a class for practice.

#include <iostream>

using namespace std;

class HelloWorld {

public:

void printMessage() {

cout << "Hello World!" << endl;

}

};

int main() {

HelloWorld hw;

hw.printMessage();

return 0;

}

Explanation

Step 1: Create class

class HelloWorld

This class represents a simple message printer.

Step 2: Define method

void printMessage()

This function prints the required output.

Step 3: Create object and call method

HelloWorld hw;

hw.printMessage();

Output

Hello World!

OOP Concepts Used

Class: HelloWorld
Public method: printMessage()
Object creation
Encapsulation (basic structure)

Why this problem exists

This problem from Kattis is used to:

Verify submission setup
Test compiler configuration
Introduce beginners to online judging systems

Conclusion

Although trivial, this problem is the starting point of all competitive programming journeys and ensures that the coding environment is correctly configured before solving more complex problems.

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.

Time Complexity

O(1)

Only one condition is checked.

OOP Solution in C++

#include <iostream>

using namespace std;

class Watermelon {

private:

int weight;

public:

// Constructor

Watermelon(int w) {

weight = w;

}

// Member function

bool canDivide() {

return (weight > 2 && weight % 2 == 0);

}

};

int main() {

int w;

cin >> w;

Watermelon wm(w);

if (wm.canDivide())

cout << "YES" << endl;

else

cout << "NO" << endl;

return 0;

}

Explanation of the Program

Step 1

Read the watermelon weight.

int w;

cin >> w;

Step 2

Create a Watermelon object.

Watermelon wm(w);

The constructor stores the value of w inside the object.

Step 3

Call the member function.

wm.canDivide();

The function checks:

weight > 2 && weight % 2 == 0

If both conditions are true, it returns true; otherwise, it returns false.

Step 4

Display the answer.

if (wm.canDivide())

cout << "YES";

else

cout << "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

OOP Concepts Used

Class – Watermelon
Private Data Member – weight
Constructor – Initializes the object's weight.
Member Function – canDivide() checks the required condition.
Object Creation – Watermelon wm(w);
Encapsulation – The weight is kept private and accessed through a public member function.

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

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.

Time Complexity

For each word, only its length is checked.

Overall complexity:

O(n)

where n is the number of words.

OOP Solution in C++

#include <iostream>

#include <string>

using namespace std;

class WordAbbreviator {

private:

string word;

public:

// Constructor

WordAbbreviator(string w) {

word = w;

}

// Member function

string abbreviate() {

if (word.length() <= 10)

return word;

return word[0] + to_string(word.length() - 2) + word[word.length() - 1];

}

};

int main() {

int n;

cin >> n;

while (n--) {

string s;

cin >> s;

WordAbbreviator obj(s);

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

}

return 0;

}

Explanation of the Program

Step 1

Read the number of words.

int n;

cin >> n;

Step 2

Read each word.

string s;

cin >> s;

Step 3

Create an object.

WordAbbreviator obj(s);

The constructor stores the word inside the object.

Step 4

Call the member function.

obj.abbreviate();

If the word length is more than 10, the function returns

First Character + Length − 2 + Last Character

Otherwise, it returns 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

OOP Concepts Used

Class – WordAbbreviator
Private Data Member – word
Constructor – Initializes the object with a word.
Public Member Function – abbreviate()
Object Creation
Encapsulation

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

Conclusion

This problem introduces beginners to:

String manipulation
Conditional statements
Loops
Object-Oriented Programming (OOP)
Constructors
Member functions
Encapsulation

Although the problem can be solved with a few lines of code, implementing it using OOP helps students practice designing classes and member functions while solving competitive programming problems.

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.

Time Complexity

Each problem is processed once.

Time Complexity: O(n)

Space Complexity: O(1)

OOP Solution in C++

#include <iostream>

using namespace std;

class TeamDecision {

private:

int petya, vasya, tonya;

public:

// Constructor

TeamDecision(int p, int v, int t) {

petya = p;

vasya = v;

tonya = t;

}

// Member function

bool canSolve() {

return (petya + vasya + tonya >= 2);

}

};

int main() {

int n;

cin >> n;

int solved = 0;

while (n--) {

int p, v, t;

cin >> p >> v >> t;

TeamDecision problem(p, v, t);

if (problem.canSolve())

solved++;

}

cout << solved << endl;

return 0;

}

Explanation of the Program

Step 1

Read the number of problems.

int n;

cin >> n;

Step 2

For each problem, read the three values.

int p, v, t;

cin >> p >> v >> t;

Step 3

Create an object.

TeamDecision problem(p, v, t);

The constructor stores the three values inside the object.

Step 4

Call the member function.

problem.canSolve();

The function checks

petya + vasya + tonya >= 2

If true, the function returns true.

Step 5

Increase the answer.

if(problem.canSolve())

solved++;

Finally,

cout << solved;

prints the total number of solved problems.

Dry Run

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 =

OOP Concepts Used

Class – TeamDecision
Private Data Members – petya, vasya, tonya
Constructor – Initializes the object's data.
Public Member Function – canSolve()
Object Creation
Encapsulation

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

Conclusion

This problem helps beginners practice:

Input and output
Loops
Conditional statements
Counting techniques
Object-Oriented Programming (OOP)
Constructors
Member functions
Encapsulation

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

Time Complexity

O(n)

Each statement is processed once.

OOP Solution in C++

#include <iostream>

#include <string>

using namespace std;

class BitCounter {

private:

int x;

public:

// Constructor

BitCounter() {

x = 0;

}

// Process one statement

void apply(string s) {

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

x++;

else

x--;

}

int getValue() {

return x;

}

};

int main() {

int n;

cin >> n;

BitCounter counter;

while (n--) {

string s;

cin >> s;

counter.apply(s);

}

cout << counter.getValue() << endl;

return 0;

}

Explanation of the Program

Step 1: Initialize

BitCounter counter;

Sets:

x = 0

Step 2: Read each operation

string s;

cin >> s;

Step 3: Apply operation

counter.apply(s);

Inside function:

If "++" exists → increment
Else → decrement

Step 4: Output result

cout << counter.getValue();

Dry Run

Input

X++

++X

X--

Execution

x = 0

X++ → 1

++X → 2

X-- → 1

Output

OOP Concepts Used

Class → BitCounter
Private Member Variable → x
Constructor → initializes x
Member Functions → apply(), getValue()
Encapsulation → x is protected inside class

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--

Conclusion

This problem is a simple introduction to:

String handling
Conditional logic
Looping
Counting operations
Object-Oriented Programming (OOP)

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.

Time Complexity

O(25) = O(1)

OOP Solution in C++

#include <iostream>

using namespace std;

class BeautifulMatrix {

private:

int matrix[5][5];

int row, col;

public:

// Constructor

BeautifulMatrix() {

row = col = 0;

}

// Input matrix and locate 1

void readMatrix() {

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

for (int j = 0; j < 5; j++) {

cin >> matrix[i][j];

if (matrix[i][j] == 1) {

row = i;

col = j;

}

// Compute minimum moves

int getMoves() {

return abs(row - 2) + abs(col - 2);

}

};

int main() {

BeautifulMatrix bm;

bm.readMatrix();

cout << bm.getMoves() << endl;

return 0;

}

Explanation

Step 1: Read matrix

The program scans all 25 elements and finds where 1 is located.

Step 2: Store position

row = i;

col = j;

This records the location of the target element.

Step 3: Compute distance

Center of matrix (0-based indexing):

(2, 2)

So we compute:

|row - 2| + |col - 2|

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

OOP Concepts Used

Class: BeautifulMatrix
Private data members: matrix, row, col
Constructor: initializes variables
Member functions:

readMatrix()
getMoves()

Encapsulation: matrix handling inside class

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++

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

Time Complexity

O(n)

Only one pass through the array.

OOP Solution in C++

#include <iostream>

#include <vector>

using namespace std;

class NextRound {

private:

vector<int> scores;

int k;

int threshold;

public:

// Constructor

NextRound(vector<int> s, int kk) {

scores = s;

k = kk;

threshold = scores[k - 1];

}

// Compute number of qualifiers

int countQualifiers() {

int count = 0;

for (int x : scores) {

if (x >= threshold && x > 0)

count++;

}

return count;

}

};

int main() {

int n, k;

cin >> n >> k;

vector<int> arr(n);

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

cin >> arr[i];

NextRound contest(arr, k);

cout << contest.countQualifiers() << endl;

return 0;

}

Explanation

Step 1: Read input

int n, k;

cin >> n >> k;

Step 2: Store scores

vector<int> arr(n);

Step 3: Find threshold score

threshold = scores[k - 1];

This is the score of the k-th ranked participant.

Step 4: Count eligible participants

A participant qualifies if:

score >= threshold && score > 0

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

OOP Concepts Used

Class: NextRound
Private data members: scores, k, threshold
Constructor: initializes threshold
Member function: countQualifiers()
Encapsulation of logic inside class

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

Conclusion

This problem is an important introduction to:

Array processing
Sorting assumptions
Threshold-based filtering
Basic OOP design in C++

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

Time Complexity

O(n) where n is length of the strings.

OOP Solution in C++

#include <iostream>

#include <string>

using namespace std;

class StringCompare {

private:

string a, b;

string toLowerCase(string s) {

for (char &c : s) {

if (c >= 'A' && c <= 'Z')

c = c + 32;

}

return s;

}

public:

// Constructor

StringCompare(string s1, string s2) {

a = toLowerCase(s1);

b = toLowerCase(s2);

}

int compare() {

if (a < b) return -1;

if (a > b) return 1;

return 0;

}

};

int main() {

string s1, s2;

cin >> s1 >> s2;

StringCompare obj(s1, s2);

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

return 0;

}

Explanation

Step 1: Read input

string s1, s2;

cin >> s1 >> s2;

Step 2: Convert to lowercase

if (c >= 'A' && c <= 'Z')

c = c + 32;

This ensures case-insensitive comparison.

Step 3: Compare strings

if (a < b) return -1;

if (a > b) return 1;

Lexicographical comparison works directly in C++ strings.

Example

Input

aaaa

aaaA

After conversion

aaaa

Output

OOP Concepts Used

Class: StringCompare
Private data members: a, b
Constructor: initializes processed strings
Private helper function: toLowerCase()
Member function: compare()
Encapsulation of logic

Common Mistakes

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

Final Rule

Convert both strings to lowercase → compare lexicographically

Conclusion

This problem is a simple but important introduction to:

String manipulation
ASCII operations
Lexicographical comparison
Object-oriented programming design in C++

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"

Time Complexity

O(n)

Each number is processed once.

C++ Solution (OOP Style)

#include <iostream>

using namespace std;

class OdditiesChecker {

private:

int value;

public:

// Constructor

OdditiesChecker(int v) {

value = v;

}

string check() {

if (value % 2 == 0)

return "even";

else

return "odd";

}

};

int main() {

int n;

cin >> n;

while (n--) {

int x;

cin >> x;

OdditiesChecker obj(x);

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

}

return 0;

}

Explanation

Step 1: Read input count

int n;

cin >> n;

Step 2: Process each number

int x;

cin >> x;

Step 3: Create object

OdditiesChecker obj(x);

Encapsulates the value inside a class.

Step 4: Check parity

obj.check();

Logic:

if value % 2 == 0 → even

else → 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

Conclusion

This problem is a basic introduction to:

Conditional logic
Modulo arithmetic
Simple input/output handling
Object-oriented programming structure in C++

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

Time Complexity

O(n) where n is the length of the string.

C++ Solution (OOP Style)

#include <iostream>

using namespace std;

class Autori {

private:

string s;

public:

// Constructor

Autori(string str) {

s = str;

}

string getAbbreviation() {

string result = "";

for (int i = 0; i < s.length(); i++) {

if (i == 0 || s[i - 1] == '-') {

result += s[i];

}

return result;

}

};

int main() {

string input;

cin >> input;

Autori obj(input);

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

return 0;

}

Explanation

Step 1: Read input

string input;

cin >> input;

Step 2: Create object

Autori obj(input);

Stores the full string inside the class.

Step 3: Extract abbreviation

if (i == 0 || s[i - 1] == '-')

result += s[i];

We take:

First character of the string
Characters after every -

Step 4: Output result

cout << obj.getAbbreviation();

Example Walkthrough

Input

Portable-Network-Graphics

Processing

Word	First letter
Portable	P
Network	N
Graphics	G

Output

PNG

OOP Concepts Used

Class: Autori
Private data member: s
Constructor: initializes string
Member function: getAbbreviation()
Encapsulation of string processing logic

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 '-'

Conclusion

This problem is a simple string manipulation task that helps beginners learn:

String traversal
Character-based parsing
Basic pattern extraction
Object-oriented programming structure in C++

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

Time Complexity

O(1) (since only 3 numbers are involved)

C++ Solution (OOP Style)

#include <iostream>

#include <algorithm>

using namespace std;

class ABCSorter {

private:

int arr[3];

string pattern;

public:

// Constructor

ABCSorter(int a, int b, int c, string p) {

arr[0] = a;

arr[1] = b;

arr[2] = c;

pattern = p;

sort(arr, arr + 3);

}

void printOrdered() {

for (char ch : pattern) {

if (ch == 'A')

cout << arr[0] << " ";

else if (ch == 'B')

cout << arr[1] << " ";

else if (ch == 'C')

cout << arr[2] << " ";

}

};

int main() {

int a, b, c;

cin >> a >> b >> c;

string p;

cin >> p;

ABCSorter obj(a, b, c, p);

obj.printOrdered();

return 0;

}

Explanation

Step 1: Read input

int a, b, c;

cin >> a >> b >> c;

Step 2: Sort values

sort(arr, arr + 3);

Now:

arr[0] = smallest
arr[1] = middle
arr[2] = largest

Step 3: Read pattern

string p;

cin >> p;

Step 4: Print based on pattern

if (ch == 'A') → smallest

if (ch == 'B') → middle

if (ch == 'C') → largest

Example

Input

6 4 2

ABC

Sorted

2 4 6

Output

2 4 6

Input

6 4 2

CBA

Output

6 4 2

OOP Concepts Used

Class: ABCSorter
Private data members: arr, pattern
Constructor: initializes and sorts data
Member function: printOrdered()
Encapsulation of sorting logic

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

Conclusion

This problem teaches:

Sorting basics
Index mapping
Simple permutation logic
Object-oriented programming structure in C++

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

Time Complexity

O(n)

C++ Solution (OOP Style)

#include <iostream>

using namespace std;

class BatterUp {

private:

int n;

int arr[100];

public:

// Constructor

BatterUp(int size) {

n = size;

}

void readInput() {

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

cin >> arr[i];

}

double calculateSlugging() {

int sum = 0;

int count = 0;

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

if (arr[i] != -1) {

sum += arr[i];

count++;

}

return (double)sum / count;

}

};

int main() {

int n;

cin >> n;

BatterUp player(n);

player.readInput();

cout << player.calculateSlugging() << endl;

return 0;

}

Explanation

Step 1: Read input

int n;

cin >> n;

Step 2: Store values

cin >> arr[i];

We store all at-bats in an array.

Step 3: Ignore invalid values

if (arr[i] != -1)

We skip all -1 entries.

Step 4: Compute average

(double)sum / count

We cast to double to ensure floating-point division.

Example

Input

3 2 -1 4 1

Valid values

3 + 2 + 4 + 1 = 10

count = 4

Output

2.5

OOP Concepts Used

Class: BatterUp
Private data members: n, arr
Constructor: initializes size
Member functions:

readInput()
calculateSlugging()

Encapsulation of logic

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

Conclusion

This problem is a simple introduction to:

Filtering invalid data
Basic statistics (average)
Array processing
Object-oriented programming in C++

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

Time Complexity

Naive approach: O(n² log n) (due to repeated sorting)
Optimal approach (heaps): O(log n) per insertion

C++ Solution (OOP + Simple Approach)

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

class Statistics {

private:

vector<int> data;

public:

void addNumber(int x) {

data.push_back(x);

}

double getMedian() {

vector<int> temp = data;

sort(temp.begin(), temp.end());

int n = temp.size();

if (n % 2 == 1) {

return temp[n / 2];

} else {

return (temp[n / 2 - 1] + temp[n / 2]) / 2.0;

}

};

int main() {

Statistics stats;

int x;

while (cin >> x) {

stats.addNumber(x);

cout << stats.getMedian() << endl;

}

return 0;

}

Explanation

Step 1: Read input continuously

while (cin >> x)

Stops only at EOF.

Step 2: Store numbers

data.push_back(x);

We keep all numbers in a vector.

Step 3: Sort and compute median

sort(temp.begin(), temp.end());

Then:

Odd count → middle element
Even count → average of middle two

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

OOP Concepts Used

Class: Statistics
Private data member: data
Member functions:

addNumber()
getMedian()

Encapsulation of dataset and logic

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)

Conclusion

This problem introduces an important statistical concept in programming:

Median calculation
Stream processing
Sorting-based solutions
Object-oriented design in C++

These are excellent beginner problems:

100 The 3n + 1 Problem
272 TEX Quotes
10038 Jolly Jumpers
10107 What is the Median?

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

Time Complexity

Naive: O(n × cycle_length)
Optimized with memoization: significantly faster in practice

C++ Solution (OOP + Memoization)

#include <iostream>

#include <unordered_map>

using namespace std;

class Collatz {

private:

unordered_map<long long, int> memo;

public:

int cycleLength(long long n) {

if (n == 1) return 1;

if (memo.count(n))

return memo[n];

long long next;

if (n % 2 == 0)

next = n / 2;

else

next = 3 * n + 1;

memo[n] = 1 + cycleLength(next);

return memo[n];

}

int maxCycle(int i, int j) {

if (i > j) swap(i, j);

int maxLen = 0;

for (int k = i; k <= j; k++) {

int len = cycleLength(k);

if (len > maxLen)

maxLen = len;

}

return maxLen;

}

};

int main() {

Collatz solver;

long long i, j;

while (cin >> i >> j) {

cout << i << " " << j << " " << solver.maxCycle(i, j) << endl;

}

return 0;

}

Explanation

Step 1: Read input

while (cin >> i >> j)

Handles multiple test cases until EOF.

Step 2: Ensure correct order

if (i > j) swap(i, j);

Step 3: Compute cycle length

Rules:

n → n/2 (if even)

n → 3n+1 (if odd)

Step 4: Memoization

memo[n] = 1 + cycleLength(next);

Stores results to avoid recomputation.

Step 5: Find maximum

for (int k = i; k <= j; k++)

Track maximum cycle length.

Example

Input

1 10

Cycle lengths (sample)

n	Cycle Length
1	1
2	2
3	8
7	17

Output

1 10 20

OOP Concepts Used

Class: Collatz
Private data member: memo
Member functions:

cycleLength()
maxCycle()

Encapsulation of algorithm logic
Memoization inside object

Common Mistakes

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

Final Rule

Compute Collatz cycle length for all numbers in range and take maximum

Conclusion

This problem is a classic ICPC-style problem that teaches:

Recursion
Memoization (dynamic programming idea)
Range processing
Optimization techniques
Object-oriented design in C++

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

Time Complexity

O(n) where n is number of characters.

C++ Solution (OOP Style)

#include <iostream>

using namespace std;

class TEXQuotes {

private:

bool openQuote;

public:

// Constructor

TEXQuotes() {

openQuote = true;

}

void process() {

char c;

while (cin.get(c)) {

if (c == '"') {

if (openQuote) {

cout << "``";

} else {

cout << "''";

}

openQuote = !openQuote;

} else {

cout << c;

}

};

int main() {

TEXQuotes converter;

converter.process();

return 0;

}

Explanation

Step 1: Read character-by-character input

cin.get(c);

This ensures we preserve spaces and newlines.

Step 2: Track quote state

bool openQuote;

true → next quote is opening
false → next quote is closing

Step 3: Replace quotes

Input	Output
"	`` (opening)
"	'' (closing)

Example

Input

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

Output

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

OOP Concepts Used

Class: TEXQuotes
Private data member: openQuote
Constructor: initializes state
Member function: process()
Encapsulation of streaming logic

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

Conclusion

This problem is an important string-streaming problem that teaches:

Character-by-character input handling
State management (finite state machine idea)
Stream processing
Object-oriented design in C++

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

Time Complexity

O(n) per test case

C++ Solution (OOP Style)

#include <iostream>

#include <cmath>

using namespace std;

class JollyChecker {

private:

int arr[3000];

bool seen[3000];

int n;

public:

JollyChecker(int size) {

n = size;

}

void readInput() {

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

cin >> arr[i];

}

string check() {

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

seen[i] = false;

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

int diff = abs(arr[i] - arr[i + 1]);

if (diff >= 1 && diff <= n - 1)

seen[diff] = true;

}

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

if (!seen[i])

return "Not jolly";

}

return "Jolly";

}

};

int main() {

int n;

while (cin >> n) {

JollyChecker obj(n);

obj.readInput();

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

}

return 0;

}

Explanation

Step 1: Read sequence

cin >> n;

Step 2: Compute differences

diff = abs(arr[i] - arr[i+1]);

Step 3: Track differences

seen[diff] = true;

We mark which differences appear.

Step 4: Validate condition

We must have:

all values from 1 to n-1 must exist

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

OOP Concepts Used

Class: JollyChecker
Private data: arr, seen, n
Constructor: initializes size
Member functions:

readInput()
check()

Encapsulation of validation logic

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

Conclusion

This problem is a classic beginner-to-intermediate problem that teaches:

Array processing
Absolute differences
Boolean marking techniques
Input until EOF
Object-oriented programming in C++

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

Time Complexity

Each insertion: O(log n)
Each median query: O(1)

C++ Solution (OOP + Heap Based)

#include <iostream>

#include <queue>

using namespace std;

class MedianStream {

private:

priority_queue<int> maxHeap;

priority_queue<int, vector<int>, greater<int>> minHeap;

public:

void addNumber(int x) {

if (maxHeap.empty() || x <= maxHeap.top())

maxHeap.push(x);

else

minHeap.push(x);

// Balance heaps

if (maxHeap.size() > minHeap.size() + 1) {

minHeap.push(maxHeap.top());

maxHeap.pop();

}

else if (minHeap.size() > maxHeap.size()) {

maxHeap.push(minHeap.top());

minHeap.pop();

}

double getMedian() {

if (maxHeap.size() > minHeap.size())

return maxHeap.top();

return (maxHeap.top() + minHeap.top()) / 2.0;

}

};

int main() {

MedianStream ms;

int x;

while (cin >> x) {

ms.addNumber(x);

cout << ms.getMedian() << endl;

}

return 0;

}

Explanation

Step 1: Maintain two heaps

priority_queue<int> maxHeap;

priority_queue<int, vector<int>, greater<int>> minHeap;

maxHeap → smaller half
minHeap → larger half

Step 2: Insert number

if (x <= maxHeap.top())

Decides which side the number belongs to.

Step 3: Balance heaps

Ensure:

|size(maxHeap) - size(minHeap)| ≤ 1

Step 4: Compute median

Odd count → top of maxHeap
Even count → average of two heap tops

Example

Input

Processing

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

Output

2.5

OOP Concepts Used

Class: MedianStream
Private data:

maxHeap
minHeap

Member functions:

addNumber()
getMedian()

Encapsulation of streaming logic

Common Mistakes

Using only sorting (too slow)
Forgetting heap balancing
Integer division instead of floating-point
Not handling EOF input correctly

Final Rule

Maintain two heaps and balance them to compute median dynamically

Conclusion

This problem is a classic streaming statistics problem that teaches:

Heaps (priority queues)
Dynamic data structures
Median maintenance
Efficient algorithm design
Object-oriented programming in C++

It is a key ICPC-level concept often used in real contest problems.

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

Time Complexity

Not strictly bounded mathematically, but works efficiently for constraints in CSES Problem Set
Typical complexity: proportional to sequence length

C++ Solution (OOP Style)

#include <iostream>

using namespace std;

class WeirdAlgorithm {

private:

long long n;

public:

WeirdAlgorithm(long long value) {

n = value;

}

void generate() {

while (n != 1) {

cout << n << " ";

if (n % 2 == 0)

n = n / 2;

else

n = 3 * n + 1;

}

cout << 1 << endl;

}

};

int main() {

long long n;

cin >> n;

WeirdAlgorithm obj(n);

obj.generate();

return 0;

}

Explanation

Step 1: Start from n

n = starting value

Step 2: Apply rules

Even → divide by 2
Odd → multiply by 3 and add 1

Step 3: Stop condition

Stop when n == 1

Example

Input

Process

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

Output

3 10 5 16 8 4 2 1

OOP Concepts Used

Class: WeirdAlgorithm
Private data member: n
Constructor: initializes starting value
Member function: generate()
Encapsulation of sequence logic

Common Mistakes

Forgetting to print the last value 1
Using int instead of long long (overflow risk)
Incorrect loop termination condition
Printing extra spaces incorrectly

Final Rule

If n is even → n = n / 2

If n is odd → n = 3n + 1

Repeat until n = 1

Conclusion

This problem is a foundational exercise in:

Basic simulation
Conditional logic
Looping
Sequence generation
Object-oriented programming in C++

It is often one of the first problems recommended for beginners entering competitive programming.

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

Time Complexity

O(n)

Space Complexity

O(1) (if streaming input)

C++ Solution (OOP Style)

#include <iostream>

using namespace std;

class MissingNumber {

private:

long long n;

long long sumGiven;

public:

MissingNumber(long long size) {

n = size;

sumGiven = 0;

}

void readAndCompute() {

long long x;

for (long long i = 0; i < n - 1; i++) {

cin >> x;

sumGiven += x;

}

long long findMissing() {

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

return total - sumGiven;

}

};

int main() {

long long n;

cin >> n;

MissingNumber solver(n);

solver.readAndCompute();

cout << solver.findMissing() << endl;

return 0;

}

Explanation

Step 1: Compute expected total

1 + 2 + ... + n

Step 2: Compute given sum

We add all input numbers.

Step 3: Subtract

missing = total - given_sum

Example

Input

2 3 1 5

Calculation

Total = 15
Given = 11

Output

OOP Concepts Used

Class: MissingNumber
Private data members: n, sumGiven
Constructor: initializes state
Member functions:

readAndCompute()
findMissing()

Encapsulation of logic

Common Mistakes

Using int instead of long long
Forgetting one number in sum
Overflow in n(n+1)/2
Misreading input size (n-1 numbers)

Final Rule

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

Conclusion

This problem is a classic introduction to:

Mathematical reasoning
Summation formulas
Efficient input handling
Basic problem decomposition
Object-oriented programming in C++

It is one of the most important starter problems in competitive programming.

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

Time Complexity

O(n) where n is length of string

C++ Solution (OOP Style)

#include <iostream>

#include <string>

using namespace std;

class Repetitions {

private:

string s;

public:

Repetitions(string str) {

s = str;

}

int longestRun() {

int best = 1;

int current = 1;

for (int i = 1; i < s.length(); i++) {

if (s[i] == s[i - 1])

current++;

else

current = 1;

if (current > best)

best = current;

}

return best;

}

};

int main() {

string s;

cin >> s;

Repetitions obj(s);

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

return 0;

}

Explanation

Step 1: Read string

AGAAAACCC

Step 2: Track consecutive characters

Example:

A G A A A A C C C

Runs:

A → 1
G → 1
A → 4
C → 3

Step 3: Keep maximum

Final answer:

Example

Input

ATTCGGGA

Output

Explanation:

TT → 2
GGG → 3 (maximum)

OOP Concepts Used

Class: Repetitions
Private data member: s
Constructor: initializes string
Member function: longestRun()
Encapsulation of scanning logic

Common Mistakes

Forgetting to initialize best = 1
Not resetting current when character changes
Starting loop from index 0 instead of 1

Final Rule

Track consecutive equal characters and maintain maximum length

Conclusion

This problem is a fundamental string processing problem that teaches:

String traversal
Two-pointer-like scanning logic
State tracking
Simple dynamic counting
Object-oriented programming in C++

It is one of the easiest but most important introductory string problems in competitive programming.

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.

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

Problem Statement

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

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