Solving CSES.fi problems one by one and explainations of them

Introductory Problems

Weird Algorithm

• Time limit: 1.00 s
• Memory limit: 512 MB

Consider an algorithm that takes as input a positive integer $n$. If $n$ is even, the algorithm divides it by two, and if $n$ is odd, the algorithm multiplies it by three and adds one. The algorithm repeats this, until $n$ is one. For example, the sequence for $n=3$ is as follows:

\[3 ightarrow 10 ightarrow 5 ightarrow 16 ightarrow 8 ightarrow 4 ightarrow 2 ightarrow 1\]

Your task is to simulate the execution of the algorithm for a given value of $n$.

Input

The only input line contains an integer $n$.

Output

Print a line that contains all values of nnn during the algorithm.

Constraints

\(1 \le n \le 10^6\)

Example

Input:

3

Output:

3 10 5 16 8 4 2 1

Code

#include<iostream>
using namespace std;
int main() {
    long long int n;
    cin >> n;
    while(n>1) {
        cout << n << " ";
        if(n%2==0)
            n=n/2;
        else
            n=n*3+1;
    }
    cout << n ;
    return 0;
}

Missing Number

• Time limit: 1.00s
• Memory limit: 512 MB

You are given all numbers between $1,2,\ldots,n$ except one. Your task is to find the missing number.

Input

The first input line contains an integer n.

The second line contains n-1 numbers. Each number is distinct and between 1 and n (inclusive).

Output

Print the missing number.

Constraints

\(2 \le n \le 2 \cdot 10^5\)

Example

Input:

5
2 3 1 5

Output:

4

Code

To solve this there are a few school of thoughts and ways to solve this. One is the sum of first n numbers is $ rac{n(n+1)}{2}$. So we can sum the given numbers and find the number missing with math.

\[missing = rac{n(n+1)}{2} - sum\]

#include<iostream>
 
using namespace std;
int main() {
    long long int n,sum = 0,check;
    cin >> n;
    for(int i = 0; i < n - 1; i++) {
        cin >> check;
        sum = sum + check;
    }
    check = n*(n + 1) / 2;
    cout << check - sum;
    return 0;
}

Repetitions

• Time limit: 1.00 s
• Memory limit: 512 MB

You are given a DNA sequence: a string consisting of characters A, C, G, and T. Find the longest repetition in the sequence — the maximum-length substring consisting of a single repeated character.

Input

The only input line contains a string of n characters.

Output

Print one integer: the length of the longest repetition.

Constraints

\(1 \le n \le 10^6\)

Example

Input:

ATTCGGGA

Output:

3

Code

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

int main() {
    string code;
    long long int n = 0, len, i = 0, flag = 0, ans = 0;
    cin >> code;
    len = code.length();
    while (i <= len) {
        if (code[flag] == code[i])
            n++;
        else {
            ans = max(n, ans);
            n = 1;
            flag = i;
        }
        i++;
    }
    cout << ans << endl;
    return 0;
}

Increasing Array

• Time limit: 1.00 s
• Memory limit: 512 MB

You are given an array of n integers. You want to modify the array so that it is non-decreasing: every element is at least as large as the previous element. On each move, you may increase the value of any element by one. What is the minimum number of moves required?

Input

The first input line contains an integer n: the size of the array.
The second line contains n integers x_1, x_2, …, x_n: the contents of the array.

Output

Print the minimum number of moves.

Constraints

\(1 \le n \le 2\cdot 10^5\) \(1 \le x_i \le 10^9\)

Example

Input:

5
3 2 5 1 7

Output:

5

Code

#include<iostream>
 
using namespace std;
int main() {
    long long int k, ans = 0, i;
    cin >> k;
    long long int n[k];
    for(i = 0; i < k; i++)
        cin >> n[i];
    for(i=1; i<k; i++)
    {
        if(n[i-1]>n[i])
        {
            ans += n[i-1]-n[i];
            n[i] = n[i -1];
        }
    }
    cout << ans << endl;
    return 0;
}

Sorting and Searching

Distinct Numbers

Apartments

Ferris Wheel

Concert Tickets

Restaurant Customers

Movie Festival

Sum of Two Values

Maximum Subarray Sum

Stick Lengths

Missing Coin Sum

Collecting Numbers

Collecting Numbers II

Playlist

Towers

Traffic Lights

Distinct Values Subarrays

Distinct Values Subsequences

Josephus Problem I

Josephus Problem II

Nested Ranges Check

Nested Ranges Count

Room Allocation

Factory Machines

Tasks and Deadlines

Reading Books

Sum of Three Values

Sum of Four Values

Nearest Smaller Values

Subarray Sums I

Subarray Sums II

Subarray Divisibility

Distinct Values Subarrays II

Array Division

Movie Festival II

Maximum Subarray Sum II

Dynamic Programming

Dice Combinations

Minimizing Coins

Coin Combinations I

Coin Combinations II

Removing Digits

Grid Paths I

Book Shop

Array Description

Counting Towers

Edit Distance

Longest Common Subsequence

Rectangle Cutting

Minimal Grid Path

Money Sums

Removal Game

Two Sets II

Mountain Range

Increasing Subsequence

Projects

Elevator Rides

Counting Tilings

Counting Numbers

Increasing Subsequence II

Graph Algorithms

Counting Rooms

Labyrinth

Building Roads

Message Route

Building Teams

Round Trip

Monsters

Shortest Routes I

Shortest Routes II

High Score

Flight Discount

Cycle Finding

Flight Routes

Round Trip II

Course Schedule

Longest Flight Route

Game Routes

Investigation

Planets Queries I

Planets Queries II

Planets Cycles

Road Reparation

Road Construction

Flight Routes Check

Planets and Kingdoms

Giant Pizza

Coin Collector

Mail Delivery

De Bruijn Sequence

Teleporters Path

Hamiltonian Flights

Knight’s Tour

Download Speed

Police Chase

School Dance

Distinct Routes

Range Queries

Static Range Sum Queries

Static Range Minimum Queries

Dynamic Range Sum Queries

Dynamic Range Minimum Queries

Range Xor Queries

Range Update Queries

Forest Queries

Hotel Queries

List Removals

Salary Queries

Prefix Sum Queries

Pizzeria Queries

Visible Buildings Queries

Range Interval Queries

Subarray Sum Queries

Subarray Sum Queries II

Distinct Values Queries

Distinct Values Queries II

Increasing Array Queries

Movie Festival Queries

Forest Queries II

Range Updates and Sums

Polynomial Queries

Range Queries and Copies

Missing Coin Sum Queries

Tree Algorithms

Subordinates

Tree Matching

Tree Diameter

Tree Distances I

Tree Distances II

Company Queries I

Company Queries II

Distance Queries

Counting Paths

Subtree Queries

Path Queries

Path Queries II

Distinct Colors

Finding a Centroid

Fixed-Length Paths I

Fixed-Length Paths II

Mathematics

Josephus Queries

Exponentiation

Exponentiation II

Counting Divisors

Common Divisors

Sum of Divisors

Divisor Analysis

Prime Multiples

Counting Coprime Pairs

Next Prime

Binomial Coefficients

Creating Strings II

Distributing Apples

Christmas Party

Permutation Order

Permutation Rounds

Bracket Sequences I

Bracket Sequences II

Counting Necklaces

Counting Grids

Fibonacci Numbers

Throwing Dice

Graph Paths I

Graph Paths II

System of Linear Equations

Sum of Four Squares

Triangle Number Sums

Dice Probability

Moving Robots

Candy Lottery

Inversion Probability

Stick Game

Nim Game I

Nim Game II

Stair Game

Grundy’s Game

Another Game

String Algorithms

Word Combinations

String Matching

Finding Borders

Finding Periods

Minimal Rotation

Longest Palindrome

All Palindromes

Required Substring

Palindrome Queries

Finding Patterns

Counting Patterns

Pattern Positions

Distinct Substrings

Distinct Subsequences

Repeating Substring

String Functions

Inverse Suffix Array

String Transform

Substring Order I

Substring Order II

Substring Distribution

Geometry

Point Location Test

Line Segment Intersection

Polygon Area

Point in Polygon

Polygon Lattice Points

Minimum Euclidean Distance

Convex Hull

Maximum Manhattan Distances

All Manhattan Distances

Intersection Points

Line Segments Trace I

Line Segments Trace II

Lines and Queries I

Lines and Queries II

Area of Rectangles

Robot Path

Advanced Techniques

Meet in the Middle

Hamming Distance

Corner Subgrid Check

Corner Subgrid Count

Reachable Nodes

Reachability Queries

Cut and Paste

Substring Reversals

Reversals and Sums

Necessary Roads

Necessary Cities

Eulerian Subgraphs

Monster Game I

Monster Game II

Subarray Squares

Houses and Schools

Knuth Division

Apples and Bananas

One Bit Positions

Signal Processing

New Roads Queries

Dynamic Connectivity

Parcel Delivery

Task Assignment

Distinct Routes II

Sliding Window Problems

Sliding Window Sum

Sliding Window Minimum

Sliding Window Xor

Sliding Window Or

Sliding Window Distinct Values

Sliding Window Mode

Sliding Window Mex

Sliding Window Median

Sliding Window Cost

Sliding Window Inversions

Sliding Window Advertisement

Interactive Problems

Hidden Integer

Hidden Permutation

K-th Highest Score

Permuted Binary Strings

Colored Chairs

Inversion Sorting

Bitwise Operations

Counting Bits

Maximum Xor Subarray

Maximum Xor Subset

Number of Subset Xors

K Subset Xors

All Subarray Xors

Xor Pyramid Peak

Xor Pyramid Diagonal

Xor Pyramid Row

SOS Bit Problem

And Subset Count

Construction Problems

Inverse Inversions

Monotone Subsequences

Third Permutation

Permutation Prime Sums

Chess Tournament

Distinct Sums Grid

Filling Trominos

Grid Path Construction

Advanced Graph Problems

Nearest Shops

Prüfer Code

Tree Traversals

Course Schedule II

Acyclic Graph Edges

Strongly Connected Edges

Even Outdegree Edges

Graph Girth

Fixed Length Walk Queries

Transfer Speeds Sum

MST Edge Check

MST Edge Set Check

MST Edge Cost

Network Breakdown

Tree Coin Collecting I

Tree Coin Collecting II

Tree Isomorphism I

Tree Isomorphism II

Flight Route Requests

Critical Cities

Visiting Cities

Graph Coloring

Bus Companies

Split into Two Paths

Network Renovation

Forbidden Cities

Creating Offices

New Flight Routes

Counting Problems

Filled Subgrid Count I

Filled Subgrid Count II

All Letter Subgrid Count I

All Letter Subgrid Count II

Border Subgrid Count I

Border Subgrid Count II

Raab Game II

Empty String

Permutation Inversions

Counting Bishops

Counting Sequences

Grid Paths II

Counting Permutations

Grid Completion

Counting Reorders

Tournament Graph Distribution

Collecting Numbers Distribution

Functional Graph Distribution

Additional Problems I

Shortest Subsequence

Distinct Values Sum

Distinct Values Splits

Swap Game

Beautiful Permutation II

Multiplication Table

Bubble Sort Rounds I

Bubble Sort Rounds II

Nearest Campsites I

Nearest Campsites II

Advertisement

Special Substrings

Counting LCM Arrays

Square Subsets

Subarray Sum Constraints

Water Containers Moves

Water Containers Queries

Stack Weights

Maximum Average Subarrays

Subsets with Fixed Average

Two Array Average

Pyramid Array

Permutation Subsequence

Bit Inversions

Writing Numbers

Letter Pair Move Game

Maximum Building I

Sorting Methods

Cyclic Array

List of Sums

Additional Problems II

Bouncing Ball Steps

Bouncing Ball Cycle

Knight Moves Queries

K Subset Sums I

K Subset Sums II

Increasing Array II

Food Division

Swap Round Sorting

Binary Subsequences

School Excursion

Coin Grid

Grid Coloring II

Programmers and Artists

Removing Digits II

Coin Arrangement

Replace with Difference

Grid Puzzle I

Grid Puzzle II

Bit Substrings

Reversal Sorting

Book Shop II

GCD Subsets

Minimum Cost Pairs

Same Sum Subsets

Mex Grid Queries

Maximum Building II

Stick Divisions

Stick Difference

Coding Company

Two Stacks Sorting