很简单的一个插件，现在支持汉化Sublime Text2，Sublime Text3。全部系统Win64、Win32，Linux64，Linux32，OSX等，可以随意来回切换简体中文、繁体中文、日语、英语，无需重启SublimeText。
Codeforces 176 A
A. IQ Test
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
In the city of Ultima Thule job applicants are often offered an IQ test. The test is as follows: the person gets a piece of squared paper with a 4 × 4 square painted on it. Some of the square’s cells are painted black and others are painted white. Your task is to repaint at most one cell the other color so that the picture has a 2 × 2 square, completely consisting of cells of the same color. If the initial picture already has such a square, the person should just say so and the test will be completed. Your task is to write a program that determines whether it is possible to pass the test. You cannot pass the test if either repainting any cell or no action doesn’t result in a 2 × 2 square, consisting of cells of the same color.
Input
Four lines contain four characters each: the j-th character of the i-th line equals “.” if the cell in the i-th row and the j-th column of the square is painted white, and “#”, if the cell is black.
Output
Print “YES” (without the quotes), if the test can be passed and “NO” (without the quotes) otherwise.
Sample test(s)
input
#### .#.. #### ....
output
YES
input
#### .... #### ....
output
NO
Note
In the first test sample it is enough to repaint the first cell in the second row. After such repainting the required 2 × 2 square is on the intersection of the 1-st and 2-nd row with the 1-st and 2-nd column.
#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
char s[5][5];
bool Fit(int x,int y)
{
int w=0,b=0;
for(int i=0;i<2;i++)
for(int j=0;j<2;j++)
if('.'==s[x+i][y+j])w++;
else b++;
//cout<<x<<" "<<y<<" "<<w<<" "<<b<<endl;
return w!=b;
}
int main()
{
for(int i=0;i<4;i++)
cin>>s[i];
int flag=0;
for(int i=0;i<3;i++)
{
if(flag)break;
for(int j=0;j<3;j++)
if(Fit(i,j))
{
flag=1;
break;
}
}
if(flag)cout<<"YES"<<endl;
else cout<<"NO"<<endl;
return 0;
}
Codeforces 176 B
B. Pipeline
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
Vova, the Ultimate Thule new shaman, wants to build a pipeline. As there are exactly n houses in Ultimate Thule, Vova wants the city to have exactly n pipes, each such pipe should be connected to the water supply. A pipe can be connected to the water supply if there’s water flowing out of it. Initially Vova has only one pipe with flowing water. Besides, Vova has several splitters. A splitter is a construction that consists of one input (it can be connected to a water pipe) and x output pipes. When a splitter is connected to a water pipe, water flows from each output pipe. You can assume that the output pipes are ordinary pipes. For example, you can connect water supply to such pipe if there’s water flowing out from it. At most one splitter can be connected to any water pipe. 
The figure shows a 4-output splitter Vova has one splitter of each kind: with 2, 3, 4, …, k outputs. Help Vova use the minimum number of splitters to build the required pipeline or otherwise state that it’s impossible. Vova needs the pipeline to have exactly n pipes with flowing out water. Note that some of those pipes can be the output pipes of the splitters.
Input
The first line contains two space-separated integers n and k (1 ≤ n ≤ 1018, 2 ≤ k ≤ 109). Please, do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64dspecifier.
Output
Print a single integer — the minimum number of splitters needed to build the pipeline. If it is impossible to build a pipeline with the given splitters, print -1.
Sample test(s)
input
4 3
output
2
input
5 5
output
1
input
8 4
output
-1
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
using namespace std;
int main()
{
long long n,tmp,temp;
long long k;
long double dtmp;
//巨郁闷！被1000000000 999999999叉掉了，而只要换成long double就OK了
cin>>n>>k;
tmp=(k-1)*k/2+1;
//cout<<tmp<<endl;
if(n>tmp)cout<<-1<<endl;
else
{
dtmp=(2.0*k-1)*(2.0*k-1)-8.0*(n-1);
//cout<<dtmp<<endl;
dtmp=(2.0*k-1-sqrt(dtmp))/2.0;
temp=dtmp;
if(dtmp>temp)temp++;
//if(dtmp==temp)cout<<"!"<<endl;
if(dtmp<0)temp=1;
//cout<<dtmp<<endl;
cout<<temp<<endl;
}
return 0;
}
Topcoder好题推荐 (by 白衣少年)
推荐的好题不一定是难题，但往往带有那么一点代表性。凡是由别人推荐的题目，偶会加上推荐人ID和blog地址。偶自己推荐的题目，偶会尽量推荐一份简洁的代码。当天推荐的题会以红色标记。
Single Round Match
Codeforces 175 C
C. Building Permutation
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
Permutation p is an ordered set of integers p1, p2, …, p__n, consisting of n distinct positive integers, each of them doesn’t exceed n. We’ll denote the i-th element of permutation p as p__i. We’ll call number n the size or the length of permutation p1, p2, …, p__n. You have a sequence of integers a1, a2, …, a__n. In one move, you are allowed to decrease or increase any number by one. Count the minimum number of moves, needed to build a permutation from this sequence.
Input
The first line contains integer n (1 ≤ n ≤ 3·105) — the size of the sought permutation. The second line contains n integers_a1, _a2, …, a__n ( - 109 ≤ a__i ≤ 109).
Output
Print a single number — the minimum number of moves. Please, do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64dspecifier.
Sample test(s)
input
2 3 0
output
2
input
3 -1 -1 2
output
6
Note
In the first sample you should decrease the first number by one and then increase the second number by one. The resulting permutation is (2, 1). In the second sample you need 6 moves to build permutation (1, 3, 2).
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
long long a[300005];
int main()
{
int n;
long long ans,tmp;
cin>>n;
for(int i=0;i<n;i++)cin>>a[i];
sort(a,a+n);
ans=0;
for(int i=0;i<n;i++)
{
tmp=(long long)(i+1)-a[i];
if(tmp<0)ans-=tmp;
else ans+=tmp;
}
cout<<ans<<endl;
return 0;
}
Codeforces 175 B
B. Find Marble
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
Petya and Vasya are playing a game. Petya’s got n non-transparent glasses, standing in a row. The glasses’ positions are indexed with integers from 1 to n from left to right. Note that the positions are indexed but the glasses are not. First Petya puts a marble under the glass in position s. Then he performs some (possibly zero) shuffling operations. One shuffling operation means moving the glass from the first position to position p1, the glass from the second position to position p2 and so on. That is, a glass goes from position i to position p__i. Consider all glasses are moving simultaneously during one shuffling operation. When the glasses are shuffled, the marble doesn’t travel from one glass to another: it moves together with the glass it was initially been put in. After all shuffling operations Petya shows Vasya that the ball has moved to position t. Vasya’s task is to say what minimum number of shuffling operations Petya has performed or determine that Petya has made a mistake and the marble could not have got from position s_to position _t.
Input
The first line contains three integers: n, s, t (1 ≤ n ≤ 105; 1 ≤ s, t ≤ n) — the number of glasses, the ball’s initial and final position. The second line contains n space-separated integers: p1, p2, …, p__n (1 ≤ p__i ≤ n) — the shuffling operation parameters. It is guaranteed that all p__i’s are distinct. Note that s can equal t.
Output
If the marble can move from position s to position t, then print on a single line a non-negative integer — the minimum number of shuffling operations, needed to get the marble to position t. If it is impossible, print number -1.
Sample test(s)
input
4 2 1 2 3 4 1
output
3
input
4 3 3 4 1 3 2
output
0
input
4 3 4 1 2 3 4
output
-1
input
3 1 3 2 1 3
output
-1
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int a[100005];
int b[100005];
int main()
{
int n,s,t,tmp,ans=0,err=0;
cin>>n>>s>>t;
for(int i=1;i<=n;i++)
cin>>a[i];
tmp=s;
while(t!=tmp)
{
if(b[tmp])
{
err=1;
t++;
cout
break;
}
b[tmp]=1;
tmp=a[tmp];
ans++;
}
if(err)cout<<-1<<endl;
else cout<<ans<<endl;
return 0;
}
Codeforces 175 A
A. Slightly Decreasing Permutations
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
Permutation p is an ordered set of integers p1, p2, …, p__n, consisting of n distinct positive integers, each of them doesn’t exceed n. We’ll denote the i-th element of permutation p as p__i. We’ll call number n the size or the length of permutation p1, p2, …, p__n. The decreasing coefficient of permutation p1, p2, …, p__n is the number of such i (1 ≤ i < n), that p__i > p__i + 1. You have numbers n and k. Your task is to print the permutation of length n with decreasing coefficient k.
Input
The single line contains two space-separated integers: n, k (1 ≤ n ≤ 105, 0 ≤ k < n) — the permutation length and the decreasing coefficient.
Output
In a single line print n space-separated integers: p1, p2, …, p__n — the permutation of length n with decreasing coefficient k. If there are several permutations that meet this condition, print any of them. It is guaranteed that the permutation with the sought parameters exists.
Sample test(s)
input
5 2
output
1 5 2 4 3
input
3 0
output
1 2 3
input
3 2
output
3 2 1
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int main()
{
int n,k;
cin>>n>>k;
cout<<(k+1);
for(int i=k;i>0;i--)
cout<<" "<<i;
for(int i=k+2;i<=n;i++)
cout<<" "<<i;
cout<<endl;
return 0;
}
[转]C++中获取高精度时间差
解决一个问题通常有多种方法， 我们总想找到最高效的，所以需要对比不同算法执行所用的时间。可惜的是，C++中提供的方法一般只能精确到毫秒级。 提供一种更加精确的方法。编写一个函数，可以在C++中这样写：
__declspec (naked) unsigned __int64 GetCpuCycle( void )
{
_asm
{
rdtsc
ret
}
}
RDTSC的返回值存放在EDX EAX中， EDX为高32位，EAX为低32位。这里的 RDTSC 指令( Read Time Stamp Counter )， 获得CPU的高精度时间戳。 这样以来我们就可以在随处获得当前的CPU自上电以来的时间周期数了：
unsigned __int64 iCpuCycle = GetCpuCycle();
根据这个数字我们可以计算出上电以来所经历的时间( 秒s )：
second = iCpuCycle / CPU主频率( HZ ); 1GHZ = 1,000 MHZ = 1,000,000 KHZ = 1,000,000,000 HZ;
获取两次作差就可以得到运行的时间了。其实没必要换算成时间，关注差值就行了。
PS：
可以放心一个unsigned __int64 不会溢出 - - 可以计算一下你的CPU能保存多少年的时间。。
根据这一方法有几个好处： 一是精度高，二是函数调用开销最小，三是平台限制小，四是具有和CPU主频相对应的直接关系。。。 但是由于精度高，得到的数字浮动比较大。。
Codeforces Round #173 (Div. 2) Yet Another Number Game
D. Yet Another Number Game
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
Since most contestants do not read this part, I have to repeat that Bitlandians are quite weird. They have their own jobs, their own working method, their own lives, their own sausages and their own games! Since you are so curious about Bitland, I’ll give you the chance of peeking at one of these games. BitLGM and BitAryo are playing yet another of their crazy-looking genius-needed Bitlandish games. They’ve got a sequence of n non-negative integers a1, a2, …, a__n. The players make moves in turns. BitLGM moves first. Each player can and must do one of the two following actions in his turn:
- Take one of the integers (we’ll denote it as a__i). Choose integer x (1 ≤ x ≤ a__i). And then decrease a__i by x, that is, apply assignment:a__i = a__i - x.
- Choose integer x
. And then decrease all a__i by x, that is, apply assignment: a__i = a__i - x, for all i. The player who cannot make a move loses. You’re given the initial sequence a1, a2, …, a__n. Determine who wins, if both players plays optimally well and if BitLGM and BitAryo start playing the described game in this sequence.
Input
The first line contains an integer n (1 ≤ n ≤ 3). The next line contains n integers a1, a2, …, a__n (0 ≤ a__i < 300).
Output
Write the name of the winner (provided that both players play optimally well). Either “BitLGM” or “BitAryo” (without the quotes).
Sample test(s)
input
2 1 1
output
BitLGM
input
2 1 2
output
BitAryo
input
3 1 2 1
output
BitLGM
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;
int tab2[305][305];
int tab3[305][305][305];
int check2(int x,int y)
{
if(0==x && 0==y)return 1;
int Min=x<y?x:y;
for(int i=Min;i>=0;i--)
if(1==tab2[x-i][y-i])return 0;
for(int i=0;i<=y;i++)
if(1==tab2[x][i])return 0;
for(int i=0;i<=x;i++)
if(1==tab2[i][y])return 0;
return 1;
}
void mark2(int x,int y)
{
for(int i=0;;i++)
{
if(x+i>303 || y+i>303)break;
tab2[x+i][y+i]=0;
}
for(int i=0;i<303;i++)
{
tab2[x][i]=0;
tab2[i][y]=0;
}
tab2[x][y]=1;
}
void inital2()
{
memset(tab2,-1,sizeof(tab2));
//tab2[0][0]=1;
for(int i=0;i<303;i++)
for(int j=0;j<303;j++)
{
if(tab2[i][j]!=-1)continue;
if(check2(i,j))
{
mark2(i,j);
mark2(j,i);
}
}
/*
for(int i=0;i<10;i++)
{
for(int j=0;j<10;j++)
cout<<tab2[i][j]<<" ";
cout<<endl;
}
*/
}
int check3(int x,int y,int z)
{
if(0==x && 0==y && 0==z)return 1;
int Min=x<y?x:y;
Min=Min<z?Min:z;
for(int i=Min;i>=0;i--)
if(1==tab3[x-i][y-i][z-i])return 0;
for(int i=0;i<=z;i++)
if(1==tab3[x][y][i])return 0;
for(int i=0;i<=y;i++)
if(1==tab3[x][i][z])return 0;
for(int i=0;i<=x;i++)
if(1==tab3[i][y][z])return 0;
return 1;
}
void mark3(int x,int y,int z)
{
for(int i=0;;i++)
{
if(x+i>303 || y+i>303 || z+i>303)break;
tab3[x+i][y+i][z+i]=0;
}
for(int i=0;i<303;i++)
{
tab3[x][y][i]=0;
tab3[x][i][z]=0;
tab3[i][y][z]=0;
}
tab3[x][y][z]=1;
}
void inital3()
{
memset(tab3,-1,sizeof(tab3));
//tab2[0][0]=1;
for(int i=0;i<303;i++)
for(int j=0;j<303;j++)
for(int k=0;k<303;k++)
{
if(tab3[i][j][k]!=-1)continue;
if(check3(i,j,k))
{
mark3(i,j,k);
mark3(i,k,j);
mark3(k,i,j);
mark3(j,i,k);
mark3(j,k,i);
mark3(k,j,i);
}
}
/*
for(int i=0;i<10;i++)
{
cout<<i<<endl;
for(int k=0;k<10;k++)
{
for(int j=0;j<10;j++)
cout<<tab3[i][k][j]<<" ";
cout<<endl;
}
cout<<endl;
}
*/
}
int main()
{
int n;
int a[5];
cin>>n;
if(1==n)
{
cin>>a[0];
if(a[0])cout<<"BitLGM"<<endl;
else cout<<"BitAryo"<<endl;
}
else if(2==n)
{
inital2();
cin>>a[0]>>a[1];
//cout<<tab2[a[0]][a[1]]<<endl;
if(tab2[a[0]][a[1]])cout<<"BitAryo"<<endl;
else cout<<"BitLGM"<<endl;
}
else if(3==n)
{
inital3();
cin>>a[0]>>a[1]>>a[2];
if(tab3[a[0]][a[1]][a[2]])cout<<"BitAryo"<<endl;
else cout<<"BitLGM"<<endl;
}
return 0;
}
Codeforces Round #173 (Div. 2) XOR and Or
C. XOR and OR
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
The Bitlandians are quite weird people. They do everything differently. They have a different alphabet so they have a different definition for a string. A Bitlandish string is a string made only of characters “0” and “1”. BitHaval (the mayor of Bitland) loves to play with Bitlandish strings. He takes some Bitlandish string a, and applies several (possibly zero) operations to it. In one operation the mayor may take any two adjacent characters of a string, define one of them as x and the other one as y. Then he calculates two values p and q: p = x xor y, q = x or y. Then he replaces one of the two taken characters by p and the other one by q. The xor operation means the bitwise excluding OR operation. The or operation is the bitwise OR operation. So for example one operation can transform string 11 to string 10 or to string 01. String 1 cannot be transformed into any other string. You’ve got two Bitlandish strings a and b. Your task is to check if it is possible for BitHaval to transform string a to string b in several (possibly zero) described operations.
Input
The first line contains Bitlandish string a, the second line contains Bitlandish string b. The strings can have different lengths. It is guaranteed that the given strings only consist of characters “0” and “1”. The strings are not empty, their length doesn’t exceed 106.
Output
Print “YES” if a can be transformed into b, otherwise print “NO”. Please do not print the quotes.
Sample test(s)
input
11 10
output
YES
input
1 01
output
NO
input
000 101
output
NO
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;
int main()
{
char c;
int ones1=0,zero1=0,ones2=0,zero2=0;
int fs=1;
while(c=getchar())
{
if(1==fs)
{
if(c=='\n')fs=2;
else if(c=='1')ones1++;
else zero1++;
}
else
{
if(c=='\n')break;
else if(c=='1')ones2++;
else zero2++;
}
}
if(((ones2 && ones1) || ones2==ones1) && ones1+zero1==ones2+zero2)
cout<<"YES"<<endl;
else cout<<"NO"<<endl;
//system("pause");
return 0;
}
Codeforces Round #173 (Div. 2) Painting Eggs
B. Painting Eggs
time limit per test
5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
The Bitlandians are quite weird people. They have very peculiar customs. As is customary, Uncle J. wants to have n eggs painted for Bitruz (an ancient Bitland festival). He has asked G. and A. to do the work. The kids are excited because just as is customary, they’re going to be paid for the job! Overall uncle J. has got n eggs. G. named his price for painting each egg. Similarly, A. named his price for painting each egg. It turns out that for each egg the sum of the money both A. and G. want for the painting equals 1000. Uncle J. wants to distribute the eggs between the children so as to give each egg to exactly one child. Also, Uncle J. wants the total money paid to A. to be different from the total money paid to G. by no more than 500. Help Uncle J. Find the required distribution of eggs or otherwise say that distributing the eggs in the required manner is impossible.
Input
The first line contains integer n (1 ≤ n ≤ 106) — the number of eggs. Next n lines contain two integers a__i and g__i each (0 ≤ a__i, g__i ≤ 1000; a__i + g__i = 1000): a__i is the price said by A. for the i-th egg and g__i is the price said by G. for the i-th egg.
Output
| If it is impossible to assign the painting, print “-1” (without quotes). Otherwise print a string, consisting of n letters “G” and “A”. The i-th letter of this string should represent the child who will get the i-th egg in the required distribution. Letter “A” represents A. and letter “G” represents G. If we denote the money Uncle J. must pay A. for the painting as S__a, and the money Uncle J. must pay G. for the painting as S__g, then this inequality must hold: | S__a - S__g | ≤ 500. If there are several solutions, you are allowed to print any of them. |
Sample test(s)
input
2 1 999 999 1
output
AG
input
3 400 600 400 600 400 600
output
AGA
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
using namespace std;
const int MAXN=1000005;
struct egg
{
int a,g;
int id;
char ch;
}eggs[MAXN];
int n;
bool operator<(const egg a,const egg b)
{
return a.a<b.a;
}
int cmp(const void *a,const void *b)
{
return ((egg *)a)->id < ((egg *)b)->id;
}
int Abs(int a)
{
if(a<0)return -a;
return a;
}
int main()
{
int ans1,ans2,ans;
int st,ed;
int tmp1,tmp2;
while(cin>>n)
{
for(int i=0;i<n;i++)
{
cin>>eggs[i].a>>eggs[i].g;
eggs[i].id=i;
}
sort(eggs,eggs+n);
ans1=0;ans2=0;
st=0;ed=n-1;
while(st<=ed)
{
tmp1=Abs(ans1+eggs[st].a-ans2);
tmp2=Abs(ans2+eggs[ed].g-ans1);
if(tmp1<=Abs(ans2-ans1))
{
ans1+=eggs[st].a;
eggs[st].ch='A';
st++;
}
else if(tmp2<=Abs(ans2-ans1))
{
//if(ans2+eggs[ed].g)
ans2+=eggs[ed].g;
eggs[ed].ch='G';
ed--;
}
else if(tmp1<=tmp2)
{
ans1+=eggs[st].a;
eggs[st].ch='A';
st++;
}
else
{
ans2+=eggs[ed].g;
eggs[ed].ch='G';
ed--;
}
}
ans=ans1-ans2;
if(ans<0)ans=-ans;
if(ans>500)cout<<-1<<endl;
else
{
qsort(eggs,n,sizeof(egg),cmp);
for(int i=0;i<n;i++)
cout<<eggs[i].ch;
cout<<endl;
}
}
//system("pause");
return 0;
}