1 second
256 megabytes
standard input
standard output
One industrial factory is reforming working plan. The director suggested to set a mythical detail production norm. If at the beginning of the day there were
x details in the factory storage, then by the end of the day the factory has to produce
(remainder after dividing
x by m) more details. Unfortunately, no customer has ever bought any mythical detail, so all the details produced stay on the factory.
The board of directors are worried that the production by the given plan may eventually stop (that means that there will be а moment when the current number of details on the factory is divisible by
m).
Given the number of details a on the first day and number
m check if the production stops at some moment.
The first line contains two integers a and
m (1 ≤ a, m ≤ 105).
Print "Yes" (without quotes) if the production will eventually stop, otherwise print "No".
简单题
#include <map>
#include <set>
#include <list>
#include <stack>
#include <queue>
#include <vector>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
int a, m;
while (~scanf("%d%d", &a, &m))
{
map<int, bool> qu;
qu.clear();
bool flag = false;
while(1)
{
a = a + a % m;
a %= m;
if (a == 0)
{
flag = true;
break;
}
if (qu[a])
{
break;
}
else
{
qu[a] = 1;
}
}
if (flag)
{
printf("Yes\n");
}
else
{
printf("No\n");
}
}
return 0;
}
1 second
256 megabytes
standard input
standard output
Many computer strategy games require building cities, recruiting army, conquering tribes, collecting resources. Sometimes it leads to interesting problems.
Let's suppose that your task is to build a square city. The world map uses the Cartesian coordinates. The sides of the city should be parallel to coordinate axes. The map contains mines with valuable resources, located at some points with integer coordinates.
The sizes of mines are relatively small, i.e. they can be treated as points. The city should be built in such a way that all the mines are inside or on the border of the city square.
Building a city takes large amount of money depending on the size of the city, so you have to build the city with the minimum area. Given the positions of the mines find the minimum possible area of the city.
The first line of the input contains number n — the number of mines on the map (2 ≤ n ≤ 1000). Each of the next
n lines contains a pair of integers
xi and
yi — the coordinates of the corresponding mine ( - 109 ≤ xi, yi ≤ 109).
All points are pairwise distinct.
Print the minimum area of the city that can cover all the mines with valuable resources.
2 0 0 2 2
4
2 0 0 0 3
9
简单题
#include <map>
#include <set>
#include <list>
#include <stack>
#include <queue>
#include <vector>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
struct node
{
int x, y;
}pp[1010];
int cmp1(node a, node b)
{
return a.x < b.x;
}
int cmp2(node a, node b)
{
return a.y < b.y;
}
int main()
{
int n;
while (~scanf("%d", &n))
{
for (int i = 0; i < n; ++i)
{
scanf("%d%d", &pp[i].x, &pp[i].y);
}
int l, r, u, d;
sort(pp, pp + n, cmp1);
l = pp[0].x;
r = pp[n - 1].x;
sort(pp, pp + n, cmp2);
d = pp[0].y;
u = pp[n - 1].y;
__int64 a = (__int64)max(r - l, u - d);
printf("%I64d\n", a * a );
}
return 0;
}
1 second
256 megabytes
standard input
standard output
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 integers
l and r. For each query, find the
x, such that l ≤ x ≤ r, and
is maximum possible. If there are multiple such numbers find the smallest of them.
The first line contains integer n — the number of queries (1 ≤ n ≤ 10000).
Each of the following n lines contain two integers
li, ri — the arguments for the corresponding query (0 ≤ li ≤ ri ≤ 1018).
For each query print the answer in a separate line.
3 1 2 2 4 1 10
1 3 7
我想到的思路是，先判断区间[l，r]之间有没有2^n - 1这样的数，如果有，那么答案就是这个数；否则，找到两个这样的数A, B，包含这个区间，然后相加除以2得到C，然后判断与区间的关系，如果在区间左边，就用C + B / 2,否则就用A + C / 2，直到在区间内，可惜超时了，贴下代码
#include <map>
#include <set>
#include <list>
#include <stack>
#include <queue>
#include <vector>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
__int64 l, r;
__int64 a[70];
int main()
{
int n;
__int64 li, ri, mid, lii, rii;
a[0] = 1;
for (int i = 1; i <= 59; ++i)
{
a[i] = a[i - 1] << 1;
a[i]++;
}
scanf("%d", &n);
while(n--)
{
scanf("%I64d%I64d", &l, &r);
if (l == r)
{
printf("%I64d\n", r);
continue;
}
bool flag = false;
for (int i = 59; i >= 0; --i)
{
if (a[i] >= l && a[i] <= r)
{
printf("%I64d\n", a[i]);
flag = true;
break;
}
}
if (flag)
{
continue;
}
for (int i = 0; i <= 59; ++i)
{
if (a[i] > r)
{
ri = rii = a[i];
break;
}
}
for (int i = 59; i >= 0; --i)
{
if (a[i] < l)
{
li = lii = a[i];
break;
}
}
while (1)
{
mid = (li + ri) >> 1;
if (mid < l)
{
li = mid;
ri = rii;
}
else if(mid > r)
{
ri = mid;
li = lii;
}
else
{
printf("%I64d\n", mid);
break;
}
}
}
return 0;
}