Codeforces Round #186 (Div. 2) (ABCDE題解)

Codeforces Round #186 (Div. 2) (ABCDE題解)

 

 

A. Ilya and Bank Account time limit per test：2 seconds memory limit per test：256 megabytes

Ilya is a very clever lion, he lives in an unusual city ZooVille. In this city all the animals have their rights and obligations. Moreover, they even have their own bank accounts. The state of a bank account is an integer. The state of a bank account can be a negative number. This means that the owner of the account owes the bank money.

Ilya the Lion has recently had a birthday, so he got a lot of gifts. One of them (the gift of the main ZooVille bank) is the opportunity to delete the last digit or the digit before last from the state of his bank account no more than once. For example, if the state of Ilya's bank account is -123, then Ilya can delete the last digit and get his account balance equal to -12, also he can remove its digit before last and get the account balance equal to -13. Of course, Ilya is permitted not to use the opportunity to delete a digit from the balance.

Ilya is not very good at math, and that's why he asks you to help him maximize his bank account. Find the maximum state of the bank account that can be obtained using the bank's gift.

Input

The single line contains integer n (10 ≤ |n| ≤ 10⁹) — the state of Ilya's bank account.

Output

In a single line print an integer — the maximum state of the bank account that Ilya can get.

Sample test(s) Input

2230

Output

2230

Input

-10

Output

0

Input

-100003

Output

-10000

Note

In the first test sample Ilya doesn't profit from using the present.

In the second test sample you can delete digit 1 and get the state of the account equal to 0.

 

題目大意：一個數字，可以刪掉最後一個數字或者倒數第二個數字，也可以不刪，問操作完的最大值

 

題目分析：正數直接輸出，負數兩種刪法比個大小

 

#include 
#include 
#include 
#include 
using namespace std;

int main()
{
    int n;
    scanf(%d, &n);
    if(n >= 0)
        printf(%d
, n);
    else
    {
        n = -n;
        if(n < 10)
            printf(0
);
        else
        {
            int nn = n;
            int tmp = n / 100;
            int a = n % 10;
            int b = (nn / 10) % 10;
            printf(%d
, max(-(tmp * 10 + a), -(tmp * 10 + b)));
        }
    }
}

 

 

 

B. Ilya and Queries time limit per test：2 seconds memory limit per test：256 megabytes

Ilya the Lion wants to help all his friends with passing exams. They need to solve the following problem to pass the IT exam.

You've got string s = s₁s₂...s_n (n is the length of the string), consisting only of characters . and # andm queries. Each query is described by a pair of integersl_i, r_i(1 ≤ l_i < r_i ≤ n). The answer to the queryl_i, r_i is the number of such integersi(l_i ≤ i < r_i), thats_i = s_i + 1.

Ilya the Lion wants to help his friends but is there anyone to help him? Help Ilya, solve the problem.

Input

The first line contains string s of length n (2 ≤ n ≤ 10⁵). It is guaranteed that the given string only consists of characters . and #.

The next line contains integer m (1 ≤ m ≤ 10⁵) — the number of queries. Each of the nextm lines contains the description of the corresponding query. Thei-th line contains integers l_i, r_i(1 ≤ l_i < r_i ≤ n).

Output

Print m integers — the answers to the queries in the order in which they are given in the input.

Sample test(s) Input

......
4
3 4
2 3
1 6
2 6

Output

1
1
5
4

Input

#..###
5
1 3
5 6
1 5
3 6
3 4

Output

1
1
2
2
0

 

 

題目大意：求[l,r]中有多少個相鄰的位置字符相等

 

題目分析：記錄[1,i]中多有少個，直接減

 

#include 
#include 
#include 
using namespace std;
int const MAX = 1e5 + 5;
char s[MAX];
int cnt[MAX];

int main()
{
    scanf(%s, s + 1);
    int len = strlen(s + 1);
    for(int i = 1; i <= len; i++)
    {
        if(s[i] == s[i - 1])
            cnt[i] = cnt[i - 1] + 1;
        else
            cnt[i] = cnt[i - 1];
    }
    int m;
    scanf(%d, &m);
    while(m --)
    {
        int l, r;
        scanf(%d %d, &l, &r);
        printf(%d
, cnt[r] - cnt[l]);
    }
}

 

 

C. Ilya and Matrix time limit per test：1 second memory limit per test：256 megabytes
Ilya is a very good-natured lion. He likes maths. Of all mathematical objects, his favourite one is matrices. Now he's faced a complicated matrix problem he needs to solve.

He's got a square 2ⁿ × 2ⁿ-sized matrix and4ⁿ integers. You need to arrange all these numbers in the matrix (put each number in a single individual cell) so that thebeauty of the resulting matrix with numbers is maximum.

The beauty of a2ⁿ × 2ⁿ-sized matrix is an integer, obtained by the following algorithm:

Find the maximum element in the matrix. Let's denote it asm.If n = 0, then the beauty of the matrix equalsm. Otherwise, a matrix can be split into 4 non-intersecting2^n - 1 × 2^n - 1-sized submatrices, then the beauty of the matrix equals the sum of numberm and other four beauties of the described submatrices.

As you can see, the algorithm is recursive.

Help Ilya, solve the problem and print the resulting maximum beauty of the matrix.

Input

The first line contains integer 4ⁿ (1 ≤ 4ⁿ ≤ 2·10⁶). The next line contains4ⁿ integersa_i(1 ≤ a_i ≤ 10⁹) — the numbers you need to arrange in the2ⁿ × 2ⁿ-sized matrix.

Output

On a single line print the maximum value of the beauty of the described matrix.

Please, do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use thecin,cout streams or the%I64d specifier.

Sample test(s) Input

1
13

Output

13

Input

4
1 2 3 4

Output

14

Note

Consider the second sample. You need to arrange the numbers in the matrix as follows:

1 2
3 4

Then the beauty of the matrix will equal: 4 + 1 + 2 + 3 + 4 = 14.

 

 

題目大意：給4^n個數，填到一個2^n * 2^n的矩陣裡，要求美麗值最大，一個矩陣的美麗值等於每2^i * 2^i個子矩陣中的最大值

 

題目分析：從大到小排序，計算前綴和，每次除4，表示前4^n大的和，前4^n-1大的和。。。前4大的和，類加即可，這題好像卡cin，cout，惡心。。。

 

#include 
#include 
#include 
#include 
#define ll long long
using namespace std;
ll a[1 << 21]; 

bool cmp(ll p, ll q)
{
    return p > q;
}

int main()
{
    ll n, ans = 0;
    scanf(%I64d, &n);
    for(int i = 1; i <= n; i++)
        scanf(%I64d, &a[i]);
    sort(a + 1, a + n + 1, cmp);
    for(int i = 1; i <= n; i++)
        a[i] += a[i - 1];
    while(n)
    {
        ans += a[n],
        n /= 4;
    }
    printf(%I64d
, ans);
}

 

 

 

D. Ilya and Roads time limit per test：3 seconds memory limit per test：256 megabytes

Everything is great about Ilya's city, except the roads. The thing is, the only ZooVille road is represented asn holes in a row. We will consider the holes numbered from 1 ton, from left to right.

Ilya is really keep on helping his city. So, he wants to fix at leastk holes (perharps he can fix more) on a single ZooVille road.

The city has m building companies, thei-th company needsc_i money units to fix a road segment containing holes with numbers of at leastl_i and at mostr_i. The companies in ZooVille are very greedy, so, if they fix a segment containing some already fixed holes, they do not decrease the price for fixing the segment.

Determine the minimum money Ilya will need to fix at leastk holes.

Input

The first line contains three integers n, m, k (1 ≤ n ≤ 300, 1 ≤ m ≤ 10⁵, 1 ≤ k ≤ n). The nextm lines contain the companies' description. Thei-th line contains three integers l_i, r_i, c_i(1 ≤ l_i ≤ r_i ≤ n, 1 ≤ c_i ≤ 10⁹).

Output

Print a single integer — the minimum money Ilya needs to fix at leastk holes.

If it is impossible to fix at least k holes, print -1.

Please, do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use thecin,cout streams or the%I64d specifier.

Sample test(s) Input

10 4 6
7 9 11
6 9 13
7 7 7
3 5 6

Output

17

Input

10 7 1
3 4 15
8 9 8
5 6 8
9 10 6
1 4 2
1 4 10
8 10 13

Output

2

Input

10 1 9
5 10 14

Output

-1

 

題目大意：n個洞，m個區間，每個公司只能修補區間[li, ri]的洞並且需要花費ci，現在問至少修k個洞的最小花費，注意同一個洞多次被修的話，花費要累加

 

題目分析：n那麼小，赤果果的區間dp，dp[i][j]表示前i個洞修了j個的最小花費，p[i][j]表示從第i個洞修到第j個洞的最小花費，先預處理p[i][j]，直接在輸入的時候算一下就好，轉移方程：dp[i][j] = min(dp[i - 1][j]，dp[i - k][j - k] + p[i - k + 1][i] (1 <= k <= j))

 

#include 
#include 
#include 
#define ll long long
using namespace std;
ll const INF = 1ll << 40;
int const MAX = 305;
ll dp[MAX][MAX], p[MAX][MAX];

int main()
{
    int n, m, k;
    scanf(%d %d %d, &n, &m, &k);
    for(int i = 0; i <= n; i++)
        for(int j = i; j <= n; j++)
            dp[i][j] = p[i][j] = INF;
    while(m --)
    {
        int l, r, c;
        scanf(%d %d %d, &l, &r, &c);
        for(int i = l; i <= r; i++)
            p[l][i] = min(p[l][i], (ll)c);
    }
    dp[0][0] = 0;
    for(int i = 1; i <= n; i++)
    {
        for(int j = 0; j <= i; j++)
        {
            dp[i][j] = dp[i - 1][j];
            for(int k = 1; k <= j; k++)
                dp[i][j] = min(dp[i][j], dp[i - k][j - k] + p[i - k + 1][i]);
        }
    }
    if(dp[n][k] == INF)
        printf(-1
);
    else
        printf(%I64d
, dp[n][k]);
}

 

 

E. Ilya and Two Numbers time limit per test：2 seconds memory limit per test：256 megabytes

Ilya has recently taken up archaeology. He's recently found two numbers, written in them-based notation. Each of the found numbers consisted of exactlyn digits. Ilya immediately started looking for information about those numbers. He learned that the numbers are part of a cyphered code and the one who can decypher it can get the greatest treasure.

After considerable research Ilya understood that to decypher the code, he should do the following:

Rearrange digits in the first number in some manner. Similarly, rearrange digits in the second number in some manner. As a result of this operation, the numbers can get leading zeroes.Add numbers, digit by digit, modulo m. In other words, we need to get the third number of length n, each digit of the number is the sum of the respective numbers of the found numbers. For example, suppose there are two numbers recorded in the ternary notation, 001210 and 012111, then if you add them to each other digit by digit modulo 3, you will get number 010021. The key to the code is the maximum possible number that can be obtained in the previous step.

Help Ilya, find the key to the code.

Input

The first line contains two integers n, m (1 ≤ n, m ≤ 10⁵, m > 1). The second line contains the first found number, the third line contains the second found number.

The numbers are recorded as a sequence of digits in them-based notation. Each digit is an integer from 0 tom - 1. The digits in the line are written in the order from the most significant digits to the least significant ones.

The given numbers can contain leading zeroes.

Output

Print n m-base digits. The resulting third number written in the m-based notation. Print the digits in the order from the most significant digits to the least significant ones.

Sample test(s) Input

4 7
5 4 3 2
5 6 5 4

Output

6 4 2 1 

Input

5 5
2 4 4 1 3
1 0 1 2 4

Output

4 4 4 3 2 

 

題目大意：給兩排n個數，每排可以任意排序，現在求兩排數對m的無進位加法的最大值

 

題目分析：在輸入的時候計數，每一排的各個數字出現了多少次，然後i從0到m-1枚舉，顯然對於一個i，我要去找m - i - 1和它相加，如果沒有就找比m - i - 1小但盡可能大的相加，這裡可以用棧維護第一排，隊列維護第二排，其實相當於維護一個單調遞增棧和單調遞增隊列，若第一排的i在第二排找完可加的數後，第二排的對應數還有剩余，則將其減去m放入隊列，最後直接將隊列和棧中的元素相加，因為它們都是單調的，且和都小於m，所以可以直接加，最好是在紙上畫畫，很難描述清楚

 

#include 
#include 
#include 
#include 
#include 
using namespace std;
int const MAX = 100005;
int a[MAX], b[MAX], ans[MAX];
stack  s;
queue  q;

int main()
{
    int n, m, t, cnt = 0;
    scanf(%d %d, &n, &m);
    for(int i = 0; i < n; i++)
    {
        scanf(%d, &t);
        a[t] ++;
    }
    for(int i = 0; i < n; i++)
    {
        scanf(%d, &t);
        b[t] ++;
    }
    for(int i = 0; i < m; i++)
    {
        while(a[i])
        {
            s.push(i);
            a[i] --;
        }
        int j = m - i - 1;
        while(b[j])
        {
            if(!s.empty())
            {
                ans[cnt ++] = j + s.top();
                s.pop();
            }
            else 
                q.push(j - m);
            b[j] --;
        }
    }
    while(!s.empty())
    {
        ans[cnt ++] = s.top() + q.front();
        s.pop();
        q.pop();
    }
    sort(ans, ans + cnt);
    for(int i = n - 1; i > 0; i--)
        printf(%d , ans[i]);
    printf(%d
, ans[0]);
}