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

链接:ht​​tp://codeforces.com/contest/485

A. Factory

テストごとの制限時間

1 秒

テストごとのメモリ制限

256 メガバイト

ある工業工場は、作業計画を改革しています。監督は、神話的なディテールの制作基準を設定することを提案しました。一日の初めに工場の保管場所に x の詳細があった場合、その日の終わりまでに、工場はより多くの詳細 (x を m で割った後の残り) を生成する必要があります。残念ながら、神話的なディテールを購入した顧客は一人もいないため、生産されたすべてのディテールは工場に保管されたままです。

取締役会は、指定された計画による生産が最終的に停止するのではないかと心配しています (つまり、工場の現在の詳細の数は m) で割り切れます。

初日の詳細の数 a と数値 m が与えられた場合、ある時点で生産が停止するかどうかを確認します。

入力

最初の行には 2 つの整数 a が含まれていますand m (1?≤?a,?m?≤?105)。

出力

生産が最終的に停止する場合は "Yes" (引用符なし) を出力し、それ以外の場合は "No" を出力します。

サンプルテスト

入力

1 5

出力

No

入力

3 6

出力

Yes

x每次加上对m取模の值、如果取模が0出出YES、如果值の前出出、退出なし

#include <cstdio>#include <cstring>int vis[100002];int main(){	int a, m;	scanf("%d %d", &a, &m);	memset(vis, 0, sizeof(vis));	while(true)	{		if(a == 0)		{			printf("Yes\n");			return 0;		}		if(vis[a])		{			printf("No\n");			return 0;		}		vis[a] = 1;		a = (a + a % m) % m;	}}

B.貴重なリソース

テストごとの制限時間

1 秒

テストごとのメモリ制限

256 メガバイト

多くのコンピューター ストラテジー ゲームでは、都市の建設、軍隊の募集、部族の征服、リソースの収集が必要です。時にはそれが興味深い問題につながることもあります。

あなたの仕事が正方形の都市を建設することであると仮定しましょう。世界地図はデカルト座標を使用します。都市の側面は座標軸に平行である必要があります。マップには貴重な資源を含む鉱山が含まれており、整数の座標を持ついくつかの点に配置されています。地雷のサイズは比較的小さいため、ポイントとして扱うことができます。都市は、すべての鉱山が都市の広場の内側または境界上に位置するように構築する必要があります。

都市の建設には、都市の規模に応じて多額の資金がかかるため、次の条件で都市を構築する必要があります。最低限の面積。鉱山の位置を考慮して、都市の可能な最小面積を見つけます。

入力

入力の最初の行には数値 n が含まれていますか?マップ上の地雷の数 (2?≤?n?≤?1000)。次の各行には、整数のペア xi andyi ? が含まれています。対応する鉱山の座標 (?-?109?≤?xi,?yi?≤?109)。すべての点はペアごとに区別されます。

出力

貴重な資源ですべての鉱山をカバーできる都市の最小エリアを出力します。

サンプル テスト

入力

20 02 2

出力

入力

20 00 3

出力

给几个点、让几个点都在一正方形上またはその内部、要求正方形の面积の最小値、最上减最下および最右减最左の最大值役边长

#include <cstdio>#include <algorithm>#define ll long longusing namespace std;int main(){	int n;	ll x, y;	ll mu, md, ml, mr;	ll ans = 0;	mu = mr = -2147483646;	ml = md = 2147483647;	scanf("%d", &n);	for(int i = 0; i < n; i++)	{		scanf("%I64d %I64d", &x, &y);		mu = max(mu , y);		md = min(md , y);		ml = min(ml , x);		mr = max(mr , x);	}	ans = max((mu - md), (mr - ml)) * max((mu - md), (mr - ml));	printf("%I64d\n", ans);}

C.ビット

テストごとの制限時間

1 秒

memory limit per test

256 megabytes

Let's denote as the number of bits set ('1' bits) in the binary representation of the non-negative integer x.

You are given multiple queries consisting of pairs of integersl andr. For each query, find thex, such thatl?≤?x?≤?r, and is maximum possible. If there are multiple such numbers find the smallest of them.

Input

The first line contains integer n ? the number of queries (1?≤?n?≤?10000).

Each of the following n lines contain two integersli,?ri ? the arguments for the corresponding query (0?≤?li?≤?ri?≤?1018).

Output

For each query print the answer in a separate line.

Sample test(s)

Input

31 22 41 10

Output

137

Note

The binary representations of numbers from 1 to 10 are listed below:

110?=?12

210?=?102

310?=?112

410?=?1002

510?=?1012

610?=?1102

710?=?1112

810?=?10002

910?=?10012

1010?=?10102

给一个区间，求区间里的数转化为二进制后拥有'1'个数最多的那个数，要是拥有'1'的数量相同，取最小的那个数输出。

直接从左端点对1进行或运算，构造出'1'最多且最小的数，直到值大于右端点

#include <cstdio>#define ll long longint main(){	int t;    scanf("%d", &t);      while(t--)    {          ll l, r, tmp, p = 1;           scanf("%I64d %I64d", &l, &r);        for(ll i = 0; i < 63; i++)          {              ll tmp = l | p;             if(tmp > r)            	break;              l = tmp;            p <<= 1;          }          printf("%I64d\n", l);    }  }

D. Maximum Value

time limit per test

1 second

memory limit per test

256 megabytes

You are given a sequence a consisting ofn integers. Find the maximum possible value of (integer remainder ofai divided byaj), where1?≤?i,?j?≤?n and ai?≥?aj.

Input

The first line contains integer n ? the length of the sequence (1?≤?n?≤?2·105).

The second line contains n space-separated integersai (1?≤?ai?≤?106).

Output

Print the answer to the problem.

Sample test(s)

Input

33 4 5

Output

找a[i] < a[j]中a[j] % a[i]的最大值  ,  ai的范围不大，用hash做

#include <cstdio>  int const MAX = 2000000 + 10;  int a[MAX];  int main()  {      int n, x, ans = 0;      scanf("%d",&n);        for(int i = 0; i < n; i++)      {          scanf("%d",&x);          a[x] = x;      }      for(int i = 0; i < MAX; i++)          if(a[i] != i)              a[i] = a[i - 1];      for(int i = 2; i < MAX; i++)            if(a[i] == i)              for(int j = i + i - 1; j < MAX; j = j + i)                  if(a[j] % i > ans && a[j] > i)                      ans = a[j] % i;            printf("%d\n",ans);   } 

Div.1 : D. Kindergarten

time limit per test

2 seconds

memory limit per test

256 megabytes

In a kindergarten, the children are being divided into groups. The teacher put the children in a line and associated each child with his or her integer charisma value. Each child should go to exactly one group. Each group should be a nonempty segment of consecutive children of a line. A group's sociability is the maximum difference of charisma of two children in the group (in particular, if the group consists of one child, its sociability equals a zero).

The teacher wants to divide the children into some number of groups in such way that the totalsociability of the groups is maximum. Help him find this value.

Input

The first line contains integer n ? the number of children in the line (1?≤?n?≤?106).

The second line contains n integersai ? the charisma of thei-th child (?-?109?≤?ai?≤?109).

Output

Print the maximum possible total sociability of all groups.

Sample test(s)

Input

51 2 3 1 2

Output

Input

33 3 3

Output

Note

In the first test sample one of the possible variants of an division is following: the first three children form a group with sociability 2, and the two remaining children form a group with sociability 1.

In the second test sample any division leads to the same result, the sociability will be equal to 0 in each group.

把一串数列分成若干组，每组的权值为该组中最大值与最小值的差，求所有组的权值和的最大值

#include <cstdio>#define ll long longint main(){    int n, t;     scanf ("%d", &n);    ll ans = 0, t1 = 0, t2 = 0;    for(int i = 0; i < n; i++)    {        scanf("%d", &t);        if (!i || ans + t > t1) t1 = ans + t;        if (!i || ans - t > t2) t2 = ans - t;        ans = t1 - t > t2 + t ? t1 - t : t2 + t;    }    printf("%I64d\n", ans);}