codeforces Educational Codeforces Round 54 (Rated for Div. 2) 题解

56 阅读 0 评论 37 点赞

我是靠谱客的博主无奈万宝路，最近开发中收集的这篇文章主要介绍codeforces Educational Codeforces Round 54 (Rated for Div. 2) 题解，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

。。。。此次Div2就做了两个题目，第一个题目wa了4次，22分钟出的，第二道题目一遍过，18分钟，然后看到c题感觉样例好玄学，就捣鼓浮点数去了，没想到是二元一次方程求解。。。还是太蠢了。

A：

You are given a string s consisting of n lowercase Latin letters.

You have to remove at most one (i.e. zero or one) character of this string in such a way that the string you obtain will be lexicographically smallest among all strings that can be obtained using this operation.

String s=s1s2…sn

is lexicographically smaller than string t=t1t2…tm if n<m and s1=t1,s2=t2,…,sn=tn or there exists a number p such that p≤min(n,m) and s1=t1,s2=t2,…,sp−1=tp−1 and sp<tp

For example, "aaa" is smaller than "aaaa", "abb" is smaller than "abc", "pqr" is smaller than "z".

Input

The first line of the input contains one integer n

(2≤n≤2⋅105) — the length of s

The second line of the input contains exactly n

lowercase Latin letters — the string s

Output

Print one string — the smallest possible lexicographically string that can be obtained by removing at most one character from the string s

Examples

Input

Copy

3
aaa

Output

Copy

aa

Input

Copy

5
abcda

Output

Copy

abca

Note

In the first example you can remove any character of s

to obtain the string "aa".

In the second example "abca" < "abcd" < "abcda" < "abda" < "acda" < "bcda".

找第i项比第i+1项大的。删除的就是那个字符，如果没有，则删除最后一位。

代码如下：

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
const int maxn=2*1e5+5;
int n;
char a[maxn];
int main()
{
    scanf("%d",&n);
    int loc;
    char Max;
    scanf("%s",a);
    int flag=0;
    for (int i=0;i<n-1;i++)
    {
        if(a[i]>a[i+1])
        {
            flag=1;
            loc=i;
            break;
        }
    }
    if(!flag)
        loc=n-1;
    for (int i=0;i<n;i++)
        if(i!=loc)
        printf("%c",a[i]);
    printf("n");
    return 0;
}

B. Divisor Subtraction

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

You are given an integer number n

. The following algorithm is applied to it:

if n=0， then end algorithm;
find the smallest prime divisor d of n;
subtract d from n and go to step 1

Determine the number of subtrations the algorithm will make.

Input

The only line contains a single integer n
(2≤n≤1010
).

Output

Print a single integer — the number of subtractions the algorithm will make.

Examples
Input
Copy
```
5
```
Output
Copy
```
1
```
Input
Copy
```
4
```
Output
Copy
```
2
```
Note

In the first example 5
is the smallest prime divisor, thus it gets subtracted right away to make a 0
.

In the second example 2

is the smallest prime divisor at both steps.

当为偶数时，直接/2即可，当为奇数，求出枚举求出最小素因子，然后减去这个素因子，必定为偶数，然后转化为偶数求解的方式。

代码如下：

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <math.h>
using namespace std;
typedef long long ll;
ll n;
int is_su (ll x,ll& yin)
{
    ll m=(ll)sqrt(x);
    for (ll i=2;i<=m;i++)
    {
        if(x%i==0)
        {
            yin=i;
            return 0;
        }
    }
    return 1;
}
int main()
{
    scanf("%lld",&n);
    if(n%2==0)
    {
        printf("%lldn",n/2);
    }
    else
    {
        ll t;
        if(is_su(n,t))
        {
            printf("1n");
        }
        else
        {
            printf("%lldn",(n-t)/2+1);
        }
    }
    return 0;
}

C. Meme Problem

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Try guessing the statement from this picture:

You are given a non-negative integer d

. You have to find two non-negative real numbers a and b such that a+b=d and a⋅b=d

Input

The first line contains t

(1≤t≤103

) — the number of test cases.

Each test case contains one integer d

(0≤d≤103)

Output

For each test print one line.

If there is an answer for the i

-th test, print "Y", and then the numbers a and b

If there is no answer for the i

-th test, print "N".

Your answer will be considered correct if |(a+b)−a⋅b|≤10−6

and |(a+b)−d|≤10−6

Example

Input

Copy

Output

Copy

Y 67.985071301 1.014928699
Y 0.000000000 0.000000000
N
Y 2.000000000 2.000000000
Y 3.618033989 1.381966011
Y 997.998996990 1.001003010
Y 998.998997995 1.001002005

这题目想了50分钟结果想歪了。。。

就是个解二元一次方程组的问题。

a+b=d; a*b=d;

则a*(d-a)=d;

则a*a-ad+d=0,

用求根公式求出一个解，然后d减去那个解就是b的答案。

代码如下：

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <math.h>
using namespace std;
int t;
double d;
int main()
{
    scanf("%d",&t);
    while (t--)
    {
        scanf("%lf",&d);
        double m;
        m=d*d-4*d;
        if(m<0)
        {
            printf("Nn");
        }
        else
        {
            double x1,x2;
            m=sqrt(m);
            x1=(d+m)/2;
            x2=d-x1;
            printf("Y %.9lf %.9lfn",x1,x2);
        }
    }
    return 0;
}