Memory Limit: 32768KB
Case Time Limit: 10000MS
Time Limit: 10000MS
Judger: Normal
Who can be the king in the kingdom of frogs?The one who can solve this problem in the shortest time. So, what’s theproblem? The problem named as Triple-Free- Or-Not. You are given a list ofinteger, you are asked to tell if the list is triple free or not. Triple freemeans, no 3 integers in the list can form an increasing arithmetic sequence(asequence of numbers such that the difference of any two successive members is apositive constant). The old king wants to keep the position, he is asking yourhelp.
You are given a list of integer numbers,write a program which can tell if it is triple free or not.
The first line of input contains T(1 \leq T\leq 100), the number of test cases. The first line of each test case will havean integer number N(1 \leq N \leq 1, 000), the number of integers in the list.The second line will contain N integers separate by spaces, all of them are inthe range of [-2^{31},2^{31}-1]\,.
For each test case, print Triple-Free orTriple-NotFree in one line.
2
3
1 2 3
3
3 4 6
Triple-NotFree
Triple-Free
程序:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int mod=10000;
const int MAXN=10000+5;
vector<int> point[MAXN];
int main()
{
int t,i,j,k,n,a[1005],line,pos,len;
long long temp;
memset(a,0,sizeof(a));
scanf("%d",&t);
while (t--)
{
for (i=0;i<MAXN;i++)
point[i].clear();
scanf("%d",&n);
for (i=0;i<n;i++)
{
scanf("%d",&a[i]);
point[abs(a[i])%mod].push_back(a[i]);
}
sort(a,a+n);
for (i=0;i<n;i++)
for (j=i+1;j<n;j++)
{
temp=2*a[j]-a[i];
line=abs(temp)%mod;
len=point[line].size();
if (!len) continue;
for (k=0;k<len;k++)
if (temp==point[line][k]) break;
if (k<len)
{
b2:
printf("Triple-NotFree\n");
goto b1;
}
}
printf("Triple-Free\n");
b1:;
}
return 0;
}
Memory Limit: 32768KB
Case Time Limit: 31000MS
Time Limit: 60000MS
Judger: Normal
Let’s play a game about numbers. The rule ofthis game is quite simple. Only two kinds of commands in this game, one is’Add\, k\,’ command the other one is ’Ask\,
k\,’ command. You will have a list ofnumbers. At beginning the list is empty. When you got the command ’Add\, k’,firstly, you must check if the number k\, is in the list or not; secondly, ifthe number k\, is not in the list, add it to the list or do nothing. When yougot the command ’Ask\, k’ you should tell if the number in the list or not.
Please code a program for me, which can helpme to play this game.
The first line of input contains T(1 \leq T\leq 20), the number of test cases. The first line of each test case will havean integer number N(1 \leq N \leq 1, 000, 000), the number of commands. N\,lines followed, each contains one command 'Add\, k' or 'Ask\, k'(-\,2,000,000,000 \leq k \leq 2,000,000,000).
Hint for C++ users: Huge input, do not usecin.
For each ’Ask\, k’ command, print ’YES\,’when the number k\, in the list or print ’NO\,’ in one line.
2
5
Add 2
Ask 3
Ask 2
Add 3
Ask 3
2
Add 1
Ask 2
NO
YES
YES
NO
程序:
#include <iostream>
#include <string>
#include <vector>
using namespace std;
const int mod=10000;
const int MAXN=10000+5;
vector<int> point[MAXN];
int main()
{
int n,temp,t1,line,i,len;
bool pos;
char s[5];
scanf("%d",&t1);
while (t1--)
{
for (i=0;i<MAXN;i++)
point[i].clear();
scanf("%d",&n);
while (n--)
{
scanf("%s",&s);
scanf("%d",&temp);
line=abs(temp%mod);
len=point[line].size();
pos=false;
for (i=0;i<len;i++)
if (temp==point[line][i])
{
pos=true;
break;
}
if (!strcmp(s,"Add"))
{
if (!pos)
point[line].push_back(temp);
}
else
{
if (pos)
printf("YES\n");
else
printf("NO\n");
}
}
}
return 0;
}
Memory Limit: 32768KB
Case Time Limit: 10000MS
Time Limit: 30000MS
Judger: Normal
Fengshui is an ancient subject in Chinesetradition. Someone considers it as science and someone criticizes it as blindfaith. Who knows! However, in modern days, everyone should respect culture fromour ancestor!
Fengshui focus on geography,environment andstaffs' position, all the theory come from a very old book named"YI". YI means change. Everything is always changing in the world.Fengshui wishes to guide changing, make life change to a better situation. Nowlet's look at Fengshui's changing.
At first we must know about the traditionalfive elements system which composed by GOLD,WOOD,GROUND,WATER and FIRE.Everything in the world can be represented by one and only one element. Forexample, river is represented by WATER, hill is represented by GROUND. Here, weonly consider the elements. In this system, once element can kill anotherelement, and one element can born anther element. Five elements compose as acircuit, as in Figure 1.
Every place has eight direction - east, west,north, south, northeast, northwest, southeast and southwest. Every directionhas a represented element. Now, our problem is about the elements at theseeight directions which form a Fengshui situation. Figure 2 is an example of oneFengshui situation.
But Fengshui situation can change! There'retwo change ways:
TURN: The whole situation turn clockwise onestep. Figure 3 shows the situation that situation in Figure 2 makes one TURNchange.
REBORN: Based on kill and born relation, onedirection's element can be killed by another direction's (at any other place)element in the situation, and then the killed element will born out as the newelement at its direction. Of course, kill and born are all according as therelation of the system as in Figure 1. In situation of Figure 3, WATER in eastcan kill FIRE in southeast, then southeast place change to be GROUND, as inFigure 4.
Each change, no matter TURN or REBORN, constone step.
Now, there're two Fengshui situation, wewant to know is it possible that first one can change to the second one? And ifpossible, how many steps it need at least?
There're several cases, the first line ofinput is the number of cases. Every case includes 6 lines, the first 3 linesindeicate the first Fengshui situation, the last 3 lines incicate the secondFengshui situation.
The format of one situation is as follow,there may be arbitrary blanks between adjacent directions.
northwest north northeast
west east
southwest south southeast
For every case, output the number of theleast changing steps on a single line, if it is possible, or output -1.
2
GOLD WOOD WATER
WATER FIRE
WOOD GOLD GROUND
WATER GOLD WOOD
WOOD WATER
GOLD GROUND GROUND
WATER GROUND WOOD
GOLD FIRE
GOLD FIRE GROUND
GOLD FIRE FIRE
GOLD FIRE
WATER GROUND WOOD
2
14
Memory Limit: 32768KB
Case Time Limit: 10000MS
Time Limit: 10000MS
Judger: Normal
Let's play a game like Problem A41 again.The rule of this game is quite simple. Only three kinds of commands in thisgame, 'Add \, k\,' , 'Ask \, k\,' and'Del \, k\,'. You will have a list of numbers. At beginning the list is empty.When you got the command 'Add \, k', firstly, you must check if the number 'k',is in the list or not; secondly, if the number 'k', is not in the list, add itto the list or do nothing. When you got the command 'Ask \, k' you should tellif the number in the list or not. When you got the command 'Del\, k', firstly,you must check if the number 'k', is in the list or not; secondly, if thenumber 'k', is in the list, delete it from the list or do nothing.
The first line of input contains T \,, thenumber of test cases. The first line of each test case will have an integernumber N(1 \leq N \leq 1, 000, 000), the number of commands. N \, linesfollowed, each contains one command 'Add \, k' , 'Ask \, k' and 'Del \, k'. Forevery k \, fited in 32 \,-bit.
For each 'Ask \, k' command, print 'YES \,'when the number k \, in the list or print 'NO \,' in one line.
2
5
Add 2
Ask 3
Ask 2
Del 2
Add 3
2
Del 2
Ask 1
NO
YES
NO
程序:
#include <iostream>
#include <string>
#include <vector>
using namespace std;
const int mod=10000;
const int MAXN=10000+5;
vector<long long> point[MAXN];
int main()
{
int n,temp,t1,line,i,len;
bool pos;
char s[5];
scanf("%d",&t1);
while (t1--)
{
for (i=0;i<MAXN;i++)
point[i].clear();
scanf("%d",&n);
while (n--)
{
scanf("%s",&s);
scanf("%d",&temp);
line=abs(temp%mod);
len=point[line].size();
pos=false;
for (i=0;i<len;i++)
if (temp==point[line][i])
{
pos=true;
break;
}
if (!strcmp(s,"Add"))
{
if (!pos)
point[line].push_back(temp);
}
else
if (!strcmp(s,"Ask"))
{
if (pos)
printf("YES\n");
else
printf("NO\n");
}
else
{
if (pos)
point[line][i]=3000000000;
}
}
}
return 0;
}