Time Limit:1000MS Memory Limit:262144KB 64bit IO Format:%I64d & %I64u
Description
After making bad dives into swimming pools, Wilbur wants to build a swimming pool in the shape of a rectangle in his backyard. He has set up coordinate axes, and he wants the sides of the rectangle to be parallel to them. Of course, the area of the rectangle must be positive. Wilbur had all four vertices of the planned pool written on a paper, until his friend came along and erased some of the vertices.
Now Wilbur is wondering, if the remaining n vertices of the initial rectangle give enough information to restore the area of the planned swimming pool.
Input
The first line of the input contains a single integer n (1 ≤ n ≤ 4) — the number of vertices that were not erased by Wilbur's friend.
Each of the following n lines contains two integers xi and yi ( - 1000 ≤ xi, yi ≤ 1000) —the coordinates of the i-th vertex that remains. Vertices are given in an arbitrary order.
It's guaranteed that these points are distinct vertices of some rectangle, that has positive area and which sides are parallel to the coordinate axes.
Output
Print the area of the initial rectangle if it could be uniquely determined by the points remaining. Otherwise, print - 1.
Sample Input
2 0 0 1 1
1
1 1 1
-1
Hint
In the first sample, two opposite corners of the initial rectangle are given, and that gives enough information to say that the rectangle is actually a unit square.
In the second sample there is only one vertex left and this is definitely not enough to uniquely define the area.
题解：水题，给一系列点，问是否能构成唯一矩形；
代码：
A
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
#define PI(x) printf("%d",x)
#define SI(x) scanf("%d",&x)
#define P_(x) printf(" ")
const int INF=0x3f3f3f3f;
typedef long long LL;
struct Dot{
int x,y;
};
Dot a[];
int main(){
int N;
while(~scanf("%d",&N)){
int lx,rx,ly,ry;
for(int i=;i<N;i++){
scanf("%d%d",&a[i].x,&a[i].y);
if(!i)lx=rx=a[i].x,ly=ry=a[i].y;
else lx=min(lx,a[i].x),rx=max(rx,a[i].x),ly=min(ly,a[i].y),ry=max(ry,a[i].y);
}
int x=rx-lx,y=ry-ly;
if(x*y==){
puts("-1");
}
else printf("%d\n",x*y);
}
return ;
}
Time Limit:1000MS Memory Limit:262144KB 64bit IO Format:%I64d & %I64u
Description
In this problem you are to calculate the sum of all integers from 1 to n, but you should take all powers of two with minus in the sum.
For example, for n = 4 the sum is equal to - 1 - 2 + 3 - 4 = - 4, because 1, 2 and 4 are 20, 21 and 22 respectively.
Calculate the answer for t values of n.
Input
The first line of the input contains a single integer t (1 ≤ t ≤ 100) — the number of values of n to be processed.
Each of next t lines contains a single integer n (1 ≤ n ≤ 109).
Output
Print the requested sum for each of t integers n given in the input.
Sample Input
2 4 1000000000
-4 499999998352516354
Hint
The answer for the first sample is explained in the statement.
题解：求- 1 - 2 + 3 - 4.....的等式结果，其中 20, 21 and 22....前是负号；
代码：
B
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
#define PI(x) printf("%d",x)
#define SI(x) scanf("%d",&x)
#define P_(x) printf(" ")
const int INF=0x3f3f3f3f;
typedef long long LL;
int main(){
LL n;
int T;
SI(T);
while(T--){
LL temp=,i=;
scanf("%lld",&n);
while(pow(,i)<=n){
temp+=pow(,i);
i++;
}
printf("%lld\n",n*(n+)/-*temp);
}
return ;
}
Time Limit:1000MS Memory Limit:262144KB 64bit IO Format:%I64d & %I64u
Description
Blake is a CEO of a large company called "Blake Technologies". He loves his company very much and he thinks that his company should be the best. That is why every candidate needs to pass through the interview that consists of the following problem.
We define function f(x, l, r) as a bitwise OR of integers xl, xl + 1, ..., xr, where xi is the i-th element of the array x. You are given two arrays a and b of length n. You need to determine the maximum value of sum f(a, l, r) + f(b, l, r) among all possible 1 ≤ l ≤ r ≤ n.
Input
The first line of the input contains a single integer n (1 ≤ n ≤ 1000) — the length of the arrays.
The second line contains n integers ai (0 ≤ ai ≤ 109).
The third line contains n integers bi (0 ≤ bi ≤ 109).
Output
Print a single integer — the maximum value of sum f(a, l, r) + f(b, l, r) among all possible 1 ≤ l ≤ r ≤ n.
Sample Input
5 1 2 4 3 2 2 3 3 12 1
22
10 13 2 7 11 8 4 9 8 5 1 5 7 18 9 2 3 0 11 8 6
46
Hint
Bitwise OR of two non-negative integers a and b is the number c = aORb, such that each of its digits in binary notation is 1 if and only if at least one of a or b have 1 in the corresponding position in binary notation.
In the first sample, one of the optimal answers is l = 2 and r = 4, because f(a, 2, 4) + f(b, 2, 4) = (2 OR 4 OR 3) + (3 OR 3 OR12) = 7 + 15 = 22. Other ways to get maximum value is to choose l = 1 and r = 4, l = 1 and r = 5, l = 2 and r = 4, l = 2 and r = 5,l = 3 and r = 4, or l = 3 and r = 5.
In the second sample, the maximum value is obtained for l = 1 and r = 9.
题解：水，求两个数组的或值和最大；由于是或，必然是所有的或最大；
代码：
D
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
#define PI(x) printf("%d",x)
#define SI(x) scanf("%d",&x)
#define P_(x) printf(" ")
const int INF=0x3f3f3f3f;
const int MAXN=;
typedef long long LL;
LL a[MAXN],b[MAXN],c[MAXN];
int main(){
int n;
while(~scanf("%d",&n)){
LL x1=,x2=;
for(int i=;i<n;i++)scanf("%lld",&a[i]),x1|=a[i];
for(int i=;i<n;i++)scanf("%lld",&b[i]),x2|=b[i];
printf("%lld\n",x1+x2);
}
return ;
}
Time Limit:1000MS Memory Limit:262144KB 64bit IO Format:%I64d & %I64u
Description
Consider the infinite sequence of integers: 1, 1, 2, 1, 2, 3, 1, 2, 3, 4, 1, 2, 3, 4, 5.... The sequence is built in the following way: at first the number 1 is written out, then the numbers from 1 to 2, then the numbers from 1 to 3, then the numbers from 1 to 4 and so on. Note that the sequence contains numbers, not digits. For example number 10 first appears in the sequence in position 55 (the elements are numerated from one).
Find the number on the n-th position of the sequence.
Input
The only line contains integer n (1 ≤ n ≤ 1014) — the position of the number to find.
Note that the given number is too large, so you should use 64-bit integer type to store it. In C++ you can use the long long integer type and in Java you can use long integer type.
Output
Print the element in the n-th position of the sequence (the elements are numerated from one).
Sample Input
3
2
5
2
10
4
55
10
56
1
题解：给位置，问对应值；看着数那么大，果断二分了，然而错了。。。不知道为啥。。。然后暴力下过了；
代码：
F
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
#define PI(x) printf("%d",x)
#define SI(x) scanf("%d",&x)
#define P_(x) printf(" ")
const int INF=0x3f3f3f3f;
typedef long long LL;
LL n;
/*
LL erfen(LL l,LL r){
LL mid;
while(l<=r){
mid=(l+r)/2;
if(mid*(mid+1)/2>=n)r=mid-1;
else l=mid+1;
}
return r;
}
*/
int main(){
while(~scanf("%lld",&n)){
LL ans;
/*ans=erfen(1,n);
// printf("%lld\n",ans);
while(ans*(ans+1)/2>=n)ans--;
*/
LL i;
for(i=;;i++){
if(n-i<=)break;
n-=i;
}
printf("%lld\n",n);
}
return ;
}
Time Limit:2000MS Memory Limit:262144KB 64bit IO Format:%I64d & %I64u
Description
Your friend recently gave you some slimes for your birthday. You have n slimes all initially with value 1.
You are going to play a game with these slimes. Initially, you put a single slime by itself in a row. Then, you will add the other n - 1slimes one by one. When you add a slime, you place it at the right of all already placed slimes. Then, while the last two slimes in the row have the same value v, you combine them together to create a slime with value v + 1.
You would like to see what the final state of the row is after you've added all n slimes. Please print the values of the slimes in the row from left to right.
Input
The first line of the input will contain a single integer, n (1 ≤ n ≤ 100 000).
Output
Output a single line with k integers, where k is the number of slimes in the row after you've finished the procedure described in the problem statement. The i-th of these numbers should be the value of the i-th slime from the left.
Sample Input
1
1
2
2
3
2 1
8
4
Hint
In the first sample, we only have a single slime with value 1. The final state of the board is just a single slime with value 1.
In the second sample, we perform the following steps:
Initially we place a single slime in a row by itself. Thus, row is initially 1.
Then, we will add another slime. The row is now 1 1. Since two rightmost slimes have the same values, we should replace these slimes with one with value 2. Thus, the final state of the board is 2.
In the third sample, after adding the first two slimes, our row is 2. After adding one more slime, the row becomes 2 1.
In the last sample, the steps look as follows:
- 1
- 2
- 2 1
- 3
- 3 1
- 3 2
- 3 2 1
- 4
题解：
就跟2048那个游戏一样，不过这个更简单，是一维的。。。
代码：
G
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
#define PI(x) printf("%d",x)
#define SI(x) scanf("%d",&x)
#define P_(x) printf(" ")
const int INF=0x3f3f3f3f;
typedef long long LL;
const int MAXN=;
LL ans[MAXN];
int main(){
int n;
while(~scanf("%d",&n)){
int tp=;
while(n--){
ans[tp]=;
tp++;
while(tp>&&ans[tp-]==ans[tp-]){
ans[tp-]=ans[tp-]+;
tp--;
}
}
for(int i=;i<tp;i++){
if(i)printf(" ");
printf("%lld",ans[i]);
}
puts("");
}
return ;
}
Time Limit:1500MS Memory Limit:65536KB 64bit IO Format:%I64d & %I64u
Description
He thinks normal number can be sold for $b$ yuan, while number with following features can be sold for $a$ yuan.
1.The last five numbers are the same. (such as 123-4567-7777)
2.The last five numbers are successive increasing or decreasing, and the diffidence between two adjacent digits is $1$. (such as 188-0002-3456)
3.The last eight numbers are a date number, the date of which is between Jar 1st, 1980 and Dec 31th, 2016. (such as 188-1888-0809,means August ninth,1888)
Baby Ming wants to know how much he can earn if he sells all the numbers.
Input
In the second line there is a positive integer $n$, which means how many numbers Baby Ming has.(no two same phone number)
In the third line there are $2$ positive integers $a, b$, which means two kinds of phone number can sell $a$ yuan and $b$ yuan.
In the next $n$ lines there are $n$ cell phone numbers.（|phone number|==11, the first number can’t be 0)
$1 \leq T \leq 30, b < 1000, 0 < a, n \leq 100,000$
Output
Sample Input
5
100000 1000
12319990212
11111111111
22222223456
10022221111
32165491212
Sample Output
H
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
#define PI(x) printf("%d",x)
#define SI(x) scanf("%d",&x)
#define P_(x) printf(" ")
const int INF=0x3f3f3f3f;
typedef long long LL;
int num[];
int mon[]={,,,,,,,,,,,,};
bool rn(int y){
if(y%==||(y%!=&&y%==))return true;
return false;
}
bool js(){
// for(int i=1;i<=11;i++)printf("%d ",num[i]);puts("");
int temp=;
for(int i=;i<;i++){
if(num[i]!=num[i+])temp=;
}
if(temp)return true;
// puts("1"); temp=;
for(int i=;i<;i++){
if(num[i]+!=num[i+])temp=;
// printf("%d\n",temp);
}
if(temp)return true;
// puts("2"); temp=;
for(int i=;i<;i++){
if(num[i]-!=num[i+])temp=;
}
if(temp)return true; int year=,mm=,rr=;
for(int i=;i<+;i++)year=year*+num[i];
for(int i=;i<+;i++)mm=mm*+num[i];
for(int i=;i<+;i++)rr=rr*+num[i];
if(!(year>=&&year<=))return false;
if(rr==||rr>||mm==||mm>)return false;
if(!rn(year)&&mm==&&rr>=)return false;
if(mm==&&rr>)return false;
if(rn(year)&&mm==&&rr==)return true;
if(rr>mon[mm])return false;
// puts("3");
return true;
}
int main(){
int T,n,a,b;
SI(T);
char s[];
while(T--){
SI(n);
scanf("%d%d",&a,&b);
LL ans=;
for(int i=;i<n;i++){
scanf("%s",s);
for(int i=;i<=;i++)num[i]=s[i-]-'';
if(js())ans+=a;
else ans+=b;
}
printf("%lld\n",ans);
}
return ;
}
Time Limit:1000MS Memory Limit:262144KB 64bit IO Format:%I64d & %I64u
Description
Find the number of k-divisible numbers on the segment [a, b]. In other words you need to find the number of such integer values x thata ≤ x ≤ b and x is divisible by k.
Input
The only line contains three space-separated integers k, a and b (1 ≤ k ≤ 1018; - 1018 ≤ a ≤ b ≤ 1018).
Output
Print the required number.
Sample Input
1 1 10
10
2 -4 4
5
题解：问a,b之间有多少个数能被k整除，如果都大于0处理a；如果都小于0，处理b，这点让我wa了两次；一个大0一个小0，则加上0；
代码：
I
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
#define PI(x) printf("%d",x)
#define SI(x) scanf("%d",&x)
#define P_(x) printf(" ")
const int INF=0x3f3f3f3f;
typedef __int64 LL;
int main(){
LL k,a,b;
while(~scanf("%I64d%I64d%I64d",&k,&a,&b)){
LL x1=a/k;
LL x2=b/k;
LL ans=x2-x1;
if(a==&&b==){
puts("");continue;
}
if(a>=&&b>=&&a%k==)ans++;
else if(a<=&&b<=&&b%k==)ans++;
else if(a<=&&b>=)ans++;
printf("%I64d\n",ans);
}
return ;
}