Codeforces ラウンド #275 (ディビジョン 2)_html/css_WEB-ITnose

A. 反例

テストごとの制限時間 1 秒

テストごとのメモリ制限 256 メガバイト

あなたの友人は最近、共素数について学びました。 a と b の両方を割る最大数が 1 に等しい場合、数値のペア {a,?b} は互いに素と呼ばれます。

あなたの友達はよく違う発言をします。彼は最近、ペア (a,?b) が互いに素であり、ペア (b,?c) が互いに素である場合、ペア (a,?c) も互いに素であると仮定しました。

あなたは、友人の発言の反例を見つけたいと考えています。したがって、あなたのタスクは、ステートメントが false であり、数値が条件 l?≤?a?

より具体的には、l?≤?a?

入力

単一行には、スペースで区切られた 2 つの正の整数 l、r (1?≤?l?≤) が含まれています。 ?r?≤?1018; r?-?l?≤?50).

出力

スペースで区切られた 3 つの正の整数 a、b、c ?反例を形成する 3 つの異なる数値 (a、?b、?c)。解決策が複数ある場合は、どれを印刷しても構いません。数値は昇順で出力する必要があります。

反例が存在しない場合は、単一の数値 -1 を出力します。

サンプルテスト

入力

2 4

出力

2 3 4

入力

10 11

出力

-1

入力

900000000000000009 900000000000000029

出力

900000000000000009 900000000000000010 900000000000000021

注意

最初のサンプルでは、​​ペア (2,?4) は互いに素ではなく、ペア (2,?3) と (3,?4) は。

2 番目のサンプルでは、​​3 つの異なる整数のグループを形成できないため、答えは -1 です。

3 番目のサンプルでは、​​数値 900000000000000009 と 900000000000000021 が 3 で割り切れることが簡単にわかります。

题意很容易に見る懂、就不说了;

意解:简单点说就是一简单暴力,データ看起来挺吓人的,其实三个for宣搞,AC问题。

AC代コード:

<span style="font-size:12px;">#include <algorithm>#include <iostream>#include <cstring>#include <cstdio>using namespace std;typedef long long ll;const int M = 1e5 + 10;int e[M],t[M];ll gcd(ll a,ll b){    return b == 0 ? a : gcd(b,a % b);}int main(){    ll l,r;    while(cin>>l>>r)    {        int vis = 0;        for(ll a = l; a <= r - 2&&!vis; a++)        {            for(ll b = a + 1; b <= r - 1 && !vis; b++)            {                for(ll c = b + 1; c <= r; c++)                {                    if(gcd(a,b) == 1 && gcd(b,c) == 1 && gcd(a,c) != 1)                    {                        vis = 1;                        cout<<a<<" "<<b<<" "<<c<<endl;                        break;                    }                }            }        }        if(!vis) puts("-1");    }    return 0;}</span>

B. 友達とプレゼント

テストごとの制限時間 1 2 番目の

テストあたりのメモリ制限 256 メガバイト

あなたには友達が 2 人います。それぞれにいくつかの正の整数を提示したいとします。最初の友人に cnt1 番号を提示し、2 番目の友人に cnt2 番号を提示したいとします。さらに、提示されるすべての数字が区別できるようにしたいとします。これは、両方の友人に数字を提示すべきではないことも意味します。

さらに、最初の友人は、素数 x で余りなく割り切れる数字を好みません。 2 番目の人は、素数 y で余りなしに割り切れる数を嫌います。もちろん、友達が嫌いな数字を友達にプレゼントするつもりはありません。

あなたの仕事は、集合 1、?2、?... からの数字を使ってプレゼントを形成できる最小の数字 v を見つけることです。 、?v。もちろん、いくつかの数値をまったく表示しないことを選択することもできます。

1 より大きい正の整数は、1 とそれ自体以外に正の約数がない場合、素数と呼ばれます。

入力

The only line contains four positive integers cnt1, cnt2, x, y (1?≤?cnt1,?cnt2?

Output

Print a single integer ? the answer to the problem.

Sample test(s)

Input

3 1 2 3

Output

Input

1 3 2 3

Output

Note

In the first sample you give the set of numbers {1,?3,?5} to the first friend and the set of numbers {2} to the second friend. Note that if you give set {1,?3,?5} to the first friend, then we cannot give any of the numbers 1, 3, 5 to the second friend.

In the second sample you give the set of numbers {3} to the first friend, and the set of numbers {1,?2,?4} to the second friend. Thus, the answer to the problem is 4.

意解:二分答案加容斥原理,假设当前有n个坑,则放完c1或c2个坑,剩下的坑必须能够容纳n/x与n/y,否则不满足条件,此时要注意一个问题,但你把c1,c2填满后,要满足

至少剩余v / (x + y)多个坑.

AC代码:

<span style="font-size:12px;">#include <algorithm>#include <iostream>#include <cstring>#include <cstdio>using namespace std;typedef long long ll;const int M = 1e5 + 10;int e[M],t[M];ll c1,c2,x,y;bool check(ll v){    if(v / x > v - c1 || v / y > v - c2) return false;    if(v - c1 - c2 < v / (x * y)) return false;    return true;}int main(){    while(cin>>c1>>c2>>x>>y)    {        ll L = 1;        ll R = 1e9* 2;        while(L < R)        {            ll mid = (L + R) >> 1;            if(check(mid))                R = mid;            else L = mid + 1;        }        cout<<L<<endl;    }}</span>

C. Diverse Permutation

time limit per test  1 second

memory limit per test   256 megabytes

Permutation p is an ordered set of integers p1,???p2,???...,???pn, consisting of n distinct positive integers not larger than n. We'll denote as n the length of permutation p1,???p2,???...,???pn.

Your task is to find such permutation p of length n, that the group of numbers |p1?-?p2|,?|p2?-?p3|,?...,?|pn?-?1?-?pn| has exactly k distinct elements.

Input

The single line of the input contains two space-separated positive integers n, k (1?≤?k?

Output

Print n integers forming the permutation. If there are multiple answers, print any of them.

Sample test(s)

Input

3 2

Output

1 3 2

Input

3 1

Output

1 2 3

Input

5 2

Output

1 3 2 4 5

Note

By |x| we denote the absolute value of number x.

意解:简单构造题.

AC代码:

#include <algorithm>#include <iostream>#include <cstring>#include <cstdio>using namespace std;const int M = 1e5 + 10;int e[M],t[M];int main(){    int n,k,i = 1;    cin>>n>>k;    int a = 1,b = n;    while(a < b)    {        e[i] = a++;        e[i + 1] = b--;        i += 2;    }    if(n & 1) e[i] = (n + 1) / 2;    if(k == n - 1)    {        for(int i = 1; i <= n; i++)            printf(i == n? "%d\n" : "%d ",e[i]);    }    else    {        int cn=0;        for(int i = 1; i <= k; i++)            printf("%d ",e[i]);        for(int i = k + 1; i <= n; i++)            t[cn++] = e[i];        sort(t,t + cn);        if(t[cn - 1] < e[k])            for(int i = cn - 1; i >= 0; i--)                printf(i == 0? "%d\n" : "%d ",t[i]);        else            for(int i = 0; i < cn; i++)                printf(i == cn - 1? "%d\n" : "%d ",t[i]);    }    return 0;}