# A. Detective Book

## Description:

Ivan recently bought a detective book. The book is so interesting that each page of this book introduces some sort of a mystery, which will be explained later. The $i$-th page contains some mystery that will be explained on page $a_i$ ($a_i \ge i$).
Ivan wants to read the whole book. Each day, he reads the first page he didn't read earlier, and continues to read the following pages one by one, until all the mysteries he read about are explained and clear to him (Ivan stops if there does not exist any page $i$ such that Ivan already has read it, but hasn't read page $a_i$). After that, he closes the book and continues to read it on the following day from the next page.
How many days will it take to read the whole book?

## Input:

The first line contains single integer $n$ ($1 \le n \le 10^4$) — the number of pages in the book.
The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($i \le a_i \le n$), where $a_i$ is the number of page which contains the explanation of the mystery on page $i$.

## Output

Print one integer — the number of days it will take to read the whole book.

## Sample Input:

9
1 3 3 6 7 6 8 8 9

4

## AC代码:

#include <bits/stdc++.h>

int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(0); std::cout.tie(0);

int n; std::cin >> n;
std::vector<int> a(n);
for (auto &it : a) {
std::cin >> it;
--it;
}

int flag = 0, cnt = 0;
for (int i = 0; i < n; ++i) {
flag = std::max(flag, a[i]);
if (flag <= i) cnt++;
}

std::cout << cnt << '\n';
return 0;
}

# B. Good String

## Description:

You have a string $s$ of length $n$ consisting of only characters > and <. You may do some operations with this string, for each operation you have to choose some character that still remains in the string. If you choose a character >, the character that comes right after it is deleted (if the character you chose was the last one, nothing happens). If you choose a character <, the character that comes right before it is deleted (if the character you chose was the first one, nothing happens).
For example, if we choose character > in string > > < >, the string will become to > > >. And if we choose character < in string > <, the string will become to <.
The string is good if there is a sequence of operations such that after performing it only one character will remain in the string. For example, the strings >, > > are good.
Before applying the operations, you may remove any number of characters from the given string (possibly none, possibly up to $n - 1$, but not the whole string). You need to calculate the minimum number of characters to be deleted from string $s$ so that it becomes good.

## Input:

The first line contains one integer $t$ ($1 \le t \le 100$) – the number of test cases. Each test case is represented by two lines.
The first line of $i$-th test case contains one integer $n$ ($1 \le n \le 100$) – the length of string $s$.
The second line of $i$-th test case contains string $s$, consisting of only characters > and <.

## Output

For each test case print one line.
For $i$-th test case print the minimum number of characters to be deleted from string $s$ so that it becomes good.

3
2
<>
3
><<
1
>

## Sample Output:

1
0
0

### 题目链接

> 可自动消除右侧所有字符， < 可自动消除左侧所有字符，求最小删除几个字符之后字符串可自动消除到只剩下一个字符

## AC代码:

#include <bits/stdc++.h>

int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(0); std::cout.tie(0);

int t; std::cin >> t;
for (int cas = 0; cas < t; ++cas) {
int n; std::cin >> n;
std::string str; std::cin >> str;

int l = -1, r = -1;
for (int i = 0; i < n; ++i)
if (str[i] == '>') {
l = i;
break;
}
for (int i = n - 1; i > 0; --i)
if (str[i] == '<') {
r = i;
break;
}

std::cout << std::max(0, std::min(l, n - r - 1)) << '\n';
}
return 0;
}

# C. Playlist

## Description:

You have a playlist consisting of $n$ songs. The $i$-th song is characterized by two numbers $t_i$ and $b_i$ — its length and beauty respectively. The pleasure of listening to set of songs is equal to the total length of the songs in the set multiplied by the minimum beauty among them. For example, the pleasure of listening to a set of $3$ songs having lengths $[5, 7, 4]$ and beauty values $[11, 14, 6]$ is equal to $(5 + 7 + 4) \cdot 6 = 96$.
You need to choose at most $k$ songs from your playlist, so the pleasure of listening to the set of these songs them is maximum possible.

## Input:

The first line contains two integers $n$ and $k$ ($1 \le k \le n \le 3 \cdot 10^5$) – the number of songs in the playlist and the maximum number of songs you can choose, respectively.
Each of the next $n$ lines contains two integers $t_i$ and $b_i$ ($1 \le t_i, b_i \le 10^6$) — the length and beauty of $i$-th song.

## Output

Print one integer — the maximum pleasure you can get.

4 3
4 7
15 1
3 6
6 8

78

5 3
12 31
112 4
100 100
13 55
55 50

10000

## AC代码:

#include <bits/stdc++.h>

int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(0); std::cout.tie(0);

int n, k; std::cin >> n >> k;
std::vector<std::pair<long long, long long>> s(n);
for (auto &it : s) std::cin >> it.first >> it.second;
sort(s.begin(), s.end(), [&](std::pair<long long, long long> k1, std::pair<long long, long long> k2) {
return k1.second > k2.second;
});

long long sum = 0, ans = 0;
std::priority_queue<long long, std::vector<long long>, std::greater<long long> > que;
for (int i = 0; i < n; ++i) {
que.push(s[i].first);
sum += s[i].first;
if (i >= k) {
long long cur = que.top(); que.pop();
sum -= cur;
}
ans = std::max(ans, sum * s[i].second);
}

std::cout << ans << '\n';
return 0;
}

# D. Minimum Triangulation

## Description:

You are given a regular polygon with $n$ vertices labeled from $1$ to $n$ in counter-clockwise order. The triangulation of a given polygon is a set of triangles such that each vertex of each triangle is a vertex of the initial polygon, there is no pair of triangles such that their intersection has non-zero area, and the total area of all triangles is equal to the area of the given polygon. The weight of a triangulation is the sum of weigths of triangles it consists of, where the weight of a triagle is denoted as the product of labels of its vertices.
Calculate the minimum weight among all triangulations of the polygon.

## Input:

The first line contains single integer $n$ ($3 \le n \le 500$) — the number of vertices in the regular polygon.

## Output

Print one integer — the minimum weight among all triangulations of the given polygon.

3

6

4

18

## AC代码:

#include <bits/stdc++.h>

int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(0); std::cout.tie(0);

int n; std::cin >> n;

long long ans = 0;
for (int i = 2; i < n; ++i) ans += i * (i + 1);

std::cout << ans << '\n';
return 0;
}
Last modification：March 29th, 2019 at 08:53 pm