Problem C: The Same Color
Time Limit: 1 Sec Memory Limit: 128 MBSubmit: 993 Solved: 595
[ Submit][ Status][ Web Board]
Description
Diao Yang has many balls with different colors. Today he wants to divide his balls into two groups. But he does not know how to divide. Then Diao Ze gives him a suggestion: first you choose a ball and put it into the first group. Then from the second ball, if the color of the ball is same to the last ball you has chosen, then you put the ball into the other group. Otherwise you put the ball into the same group with the last ball. Diao Yang thinks it is OK.
Then the problem is, Diao Yang wants to know the product of the number of two groups’ balls. Can you help him?
Input
The first line contains an integer T, indicating the number of test cases.
In each test case, there are several lines, each line contains only one string with lowercas, indicating the color of the ball Diao Yang has chosen currently. Diao Yang will stop choosing when the string is equal to “END”. Note that the string “END” does not mean a color.
You can assume that there are at most 100 lines in each test case and each string has at most 10 letters.
Output
For each test case, output the answer in a line.
Sample Input
<span class="sampledata">3 yellow yellow pink red red green END blue black purple purple END rose orange brown white END</span>
Sample Output
<span class="sampledata">9 3 0</span>
HINT
In the first test case, the color of the first group’s balls are yellow, red, green, 3 balls in total. The color of the second group’s balls are yellow, pink, red, 3 balls in total too. So the product is 3×3=9.
In the second test case, the answer is 3×1=3 and in the third test case the answer is 4×0=0.
//题意：
给你很多个不同颜色的球，现在要将这些球放到两个箱子里，放的要求为：
先将一个球放到一个箱子里，然后放第二个球，如果第二个球与最后一个球颜色相同，那么就将这个球放到另一个箱子里，然后重复上面的操作，最后输出两个箱子球的个数的乘机。
//思路：
直接模拟，对于每个球，对每个球进行操作，模拟它放到那个箱子中就行了
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<iostream>
using namespace std;
char s[30],c[30];
int main()
{
int t,i,j;
scanf("%d",&t);
while(t--)
{
int a=0,b=0;
int tmp;
memset(c,'\0',sizeof(c));
while(scanf("%s",s)&&strcmp(s,"END")!=0)
{
if(strcmp(s,c)==0)
{
b++;
tmp=a;a=b;b=tmp;
}
else
a++;
strcpy(c,s);
}
printf("%d\n",a*b);
}
return 0;
}
Problem H: Eat Candy
Time Limit: 1 Sec Memory Limit: 128 MBSubmit: 1333 Solved: 644
[ Submit][ Status][ Web Board]
Description
There is a box with infinite volume. At first there are n candies in the box. Then every second you will eat some candies, left half of candies (round down) in the box. Then add k candies into the box. How many candies there are in the box after 109+7 seconds?
Input
There are multiple test cases. In each test case, there are only one line contains two integers n,k(1≤n,k≤109+7)
Output
For each test case, output the answer in one line.
Sample Input
<span class="sampledata">4 5 2 3</span>
Sample Output
<span class="sampledata">9 5</span>
HINT
In the first test case:
1st second, 4->2, 2+5 = 7
2nd second, 7->3, 3+5 = 8
3rd second, 8->4, 4+5 = 9
4th second, 9->4, 4+5 = 9
…
1000000007th 9
So there are 9 candies in the box after 1000000007 seconds.
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
long long n,k;
while(scanf("%lld%lld",&n,&k)!=EOF)
{
long long pre=n;
for(int i=0;i<1e9+7;i++)
{
n=n/2+k;
if(pre==n)
{
break;
}
pre=n;
}
cout<<n<<endl;
}
return 0;
}
Problem I: Catching Dogs
Time Limit: 1 Sec Memory Limit: 128 MBSubmit: 1140 Solved: 298
[ Submit][ Status][ Web Board]
Description
Diao Yang keeps many dogs. But today his dogs all run away. Diao Yang has to catch them. To simplify the problem, we assume Diao Yang and all the dogs are on a number axis. The dogs are numbered from 1 to n. At first Diao Yang is on the original point and his speed is v. The ith dog is on the point ai and its speed isvi . Diao Yang will catch the dog by the order of their numbers. Which means only if Diao Yang has caught the ith dog, he can start to catch the (i+1)th dog, and immediately. Note that When Diao Yang catching a dog, he will run toward the dog and he will never stop or change his direction until he has caught the dog. Now Diao Yang wants to know how long it takes for him to catch all the dogs.
Input
There are multiple test cases. In each test case, the first line contains two positive integers n(n≤10) and v(1≤v≤10). Then n lines followed, each line contains two integers ai(|ai|≤50) and vi(|vi|≤5). vi＜0 means the dog runs toward left and vi＞0 means the dog runs toward right. The input will end by EOF.
Output
For each test case, output the answer. The answer should be rounded to 2 digits after decimal point. If Diao Yang cannot catch all the dogs, output “Bad Dog”(without quotes).
Sample Input
<span class="sampledata">2 5 -2 -3 2 3 1 6 2 -2 1 1 0 -1 1 1 -1 -1</span>
Sample Output
<span class="sampledata">6.00 0.25 0.00 Bad Dog</span>
<span class="sampledata">//:题意：输入n，v，表示有n条狗，小明的速度是v，接下来输入n对数，xi,vi,表示相应的狗的初始位置和速度（vi小于0的话表示狗向左跑，大于0表示向右跑），</span>
小明有n条狗，现在他们都在数轴上以相应速度的相应的方向跑，现在小明想捉住他们，问需要时间是多少？
//思路：
一个一个模拟就行了，没啥说的
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<iostream>
#define INF 0x3f3f3f3f
#define E 1e-6
using namespace std;
int main()
{
int n;
double v;
while(scanf("%d%lf",&n,&v)!=EOF)
{
double t=0,tt;
double x[110],y[110],xx=0;
for(int i=0;i<n;i++)
{
scanf("%lf%lf",&x[i],&y[i]);
}
int flag=0;
for(int i=0;i<n;i++)
{
x[i]+=t*y[i];
if(x[i]==xx)
continue;
else
{
if(y[i]<0)
{
if(xx-x[i]>E)
{
if(fabs(y[i])>=v)
{
flag=1;
break;
}
else
{
tt=fabs(xx-x[i])/fabs(v+y[i]);
t+=tt;
xx-=tt*v;
}
}
else
{
tt=fabs(xx-x[i])/fabs(v-y[i]);
t+=tt;
xx+=tt*v;
}
}
else
{
if(xx-x[i]>E)
{
tt=fabs(xx-x[i])/fabs(v+y[i]);
t+=tt;
xx-=tt*v;
}
else
{
if(y[i]>=v)
{
flag=1;
break;
}
else
{
tt=fabs(xx-x[i])/fabs(v-y[i]);
t+=tt;
xx+=tt*v;
}
}
}
}
}
if(flag)
printf("Bad Dog\n");
else
printf("%.2lf\n",t);
}
return 0;
}
Problem J: Arithmetic Sequence
Time Limit: 1 Sec Memory Limit: 128 MBSubmit: 1806 Solved: 308
[ Submit][ Status][ Web Board]
Description
Giving a number sequence A with length n, you should choosing m numbers fromA(ignore the order) which can form an arithmetic sequence and make m as large as possible.
Input
There are multiple test cases. In each test case, the first line contains a positive integer n. The second line contains n integers separated by spaces, indicating the number sequence A. All the integers are positive and not more than 2000. The input will end by EOF.
Output
For each test case, output the maximum as the answer in one line.
Sample Input
<span class="sampledata">5 1 3 5 7 10 8 4 2 7 11 3 1 9 5</span>
Sample Output
<span class="sampledata">4 6</span>
HINT
In the first test case, you should choose 1,3,5,7 to form the arithmetic sequence and its length is 4.
In the second test case, you should choose 1,3,5,7,9,11 and the length is 6.
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define MAXN 2020
int dp[MAXN][MAXN];
int main()
{
int n,num[MAXN];
while(scanf("%d",&n)!=EOF)
{
for(int i=1;i<=n;i++)
scanf("%d",&num[i]);
sort(num+1,num+n+1);
for(int i=1;i<=n;i++)
for(int j=1;j<MAXN;j++)
{
dp[i][j]=1;
}
int ans=0;
for(int i=1;i<=n;i++)
{
for(int j=1;j<i;j++)
if(num[i]>num[j])
{
int d=num[i]-num[j];
dp[i][d]=max(dp[i][d],dp[j][d]+1);
if(dp[i][d]>ans)
ans=dp[i][d];
}
}
int ans2=1,pre=num[1];
for(int i=2;i<=n;i++)
{
if(pre==num[i])
{
ans2++;
ans=max(ans,ans2);
}
else
{
pre=num[i];
ans2=1;
}
}
if(n==1)
printf("1\n");
else
printf("%d\n",ans);
}
return 0;
}