Vasya, like many others, likes to participate in a variety of sweepstakes and lotteries. Now he collects wrappings from a famous chocolate bar "Jupiter". According to the sweepstake rules, each wrapping has an integer written on it — the number of points that the participant adds to his score as he buys the bar. After a participant earns a certain number of points, he can come to the prize distribution center and exchange the points for prizes. When somebody takes a prize, the prize's cost is simply subtracted from the number of his points.
Vasya didn't only bought the bars, he also kept a record of how many points each wrapping cost. Also, he remembers that he always stucks to the greedy strategy — as soon as he could take at least one prize, he went to the prize distribution centre and exchanged the points for prizes. Moreover, if he could choose between multiple prizes, he chose the most expensive one. If after an exchange Vasya had enough points left to get at least one more prize, then he continued to exchange points.
The sweepstake has the following prizes (the prizes are sorted by increasing of their cost):
- a mug (costs a points),
- a towel (costs b points),
- a bag (costs c points),
- a bicycle (costs d points),
- a car (costs e points).
Now Vasya wants to recollect what prizes he has received. You know sequence p1, p2, ..., pn, where pi is the number of points Vasya got for the i-th bar. The sequence of points is given in the chronological order. You also know numbers a, b, c, d, e. Your task is to find, how many prizes Vasya received, what prizes they are and how many points he's got left after all operations are completed.
InputThe first line contains a single integer n (1 ≤ n ≤ 50) — the number of chocolate bar wrappings that brought points to Vasya. The second line contains space-separated integers p1, p2, ..., pn (1 ≤ pi ≤ 109). The third line contains 5 integers a, b, c, d, e (1 ≤ a < b < c < d < e ≤ 109) — the prizes' costs.
OutputPrint on the first line 5 integers, separated by a space — the number of mugs, towels, bags, bicycles and cars that Vasya has got, respectively. On the second line print a single integer — the number of points Vasya will have left after all operations of exchange are completed.
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)input3output
3 10 4
2 4 10 15 20
1 1 1 0 0input
1
4output
10 4 39 2
3 5 10 11 12
3 0 1 0 3Note
0
In the first sample Vasya gets 3 points after eating the first chocolate bar. Then he exchanges 2 points and gets a mug. Vasya wins abag after eating the second chocolate bar. Then he wins a towel after eating the third chocolate bar. After all chocolate bars 3 - 2 + 10 - 10 + 4 - 4 = 1 points remains.
这是一道联系代码功底的题，题意大致是：（读题要小心仔细点）
一开始给你一个数n，然后有n个数，分别代表每次那个人能够获得的值，如果他获得的值大于最低能够兑换的奖品的要求达到的值的话，那么他就马上去换奖品，注意他每次是进行谈心选取，即如果达到要求的话，那么他每次想拿的都是当前情况下能够取到的最大值，每次取奖品直到不能够再取到为止。
#include<stdio.h>map数组中保存的是每一种奖品最终获得的数量，然后sum中保存的是每次剩下来的值（即为最终剩余多少值）。 A. Multicolored Marblestime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output
#include<string.h>
__int64 p[55],sum,map1[55];
int main(){
int i,j,k,n;
scanf("%I64d",&n);
for(i=1;i<=n;i++) scanf("%I64d",&p[i]);
__int64 a[6]={0};
for(i=1;i<=5;i++) scanf("%I64d",&a[i]);
sum=0;
for(i=1;i<=n;i++){
sum+=p[i];
for(j=5;j>=1;j--){
if(sum>=a[j]){
map1[j]+=sum/a[j];
sum=sum-sum/a[j]*a[j];
}
}
}
for(i=1;i<=5;i++){
if(i!=5) printf("%I64d ",map1[i]);
else printf("%I64d\n",map1[i]);
}
printf("%I64d\n",sum);
}
Polycarpus plays with red and blue marbles. He put n marbles from the left to the right in a row. As it turned out, the marbles form azebroid.
A non-empty sequence of red and blue marbles is a zebroid, if the colors of the marbles in this sequence alternate. For example, sequences (red; blue; red) and (blue) are zebroids and sequence (red; red) is not a zebroid.
Now Polycarpus wonders, how many ways there are to pick a zebroid subsequence from this sequence. Help him solve the problem, find the number of ways modulo 1000000007 (109 + 7).
InputThe first line contains a single integer n (1 ≤ n ≤ 106) — the number of marbles in Polycarpus's sequence.
OutputPrint a single number — the answer to the problem modulo 1000000007 (109 + 7).
Sample test(s)input3output
6input
4output
11Note
Let's consider the first test sample. Let's assume that Polycarpus initially had sequence (red; blue; red), so there are six ways to pick a zebroid:
- pick the first marble;
- pick the second marble;
- pick the third marble;
- pick the first and second marbles;
- pick the second and third marbles;
- pick the first, second and third marbles.
It can be proven that if Polycarpus picks (blue; red; blue) as the initial sequence, the number of ways won't change.
题目的大致意思是：
就是给你n个大理石，然后叫你按照他的那种方法排列，即为每次都要满足红与蓝的石头相互间隔，问你最多有几种摆放的方式，输出mod上那个数字。
这也是一道找规律的题，我是把前几组数据列出来，然后发现了数字之间的联系，比如说“ABABA"与“BABAB”这种情况算出来的值是一样的，所以只要取一种来算就好。
#include<stdio.h>
#include<string.h>
#define mod 1000000007
__int64 f[1111111];
int main(){
__int64 n;
int i,j,k;
scanf("%I64d",&n);
f[1]=1; f[2]=3;
for(i=3;i<=1000000;i++) f[i]=(f[i-1]+f[i-2]+2)%mod;
printf("%I64d\n",f[n]);
}
B. Pixelstime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output
Flatland is inhabited by pixels of three colors: red, green and blue. We know that if two pixels of different colors meet in a violent fight, only one of them survives the fight (that is, the total number of pixels decreases by one). Besides, if pixels of colors x and y (x ≠ y) meet in a violent fight, then the pixel that survives the fight immediately changes its color to z (z ≠ x; z ≠ y). Pixels of the same color are friends, so they don't fight.
The King of Flatland knows that his land will be peaceful and prosperous when the pixels are of the same color. For each of the three colors you know the number of pixels of this color that inhabit Flatland. Help the king and determine whether fights can bring peace and prosperity to the country and if it is possible, find the minimum number of fights needed to make the land peaceful and prosperous.
InputThe first line contains three space-separated integers a, b and c (0 ≤ a, b, c ≤ 231; a + b + c > 0) — the number of red, green and blue pixels, correspondingly.
OutputPrint a single number — the minimum number of pixel fights before the country becomes peaceful and prosperous. If making the country peaceful and prosperous is impossible, print -1.
Sample test(s)input1 1 1output
1input
3 1 0output
3Note
In the first test sample the country needs only one fight to achieve peace and prosperity. Besides, it can be any fight whatsoever. For example, let's assume that the green and the blue pixels fight, then the surviving pixel will be red. As a result, after the fight there are two red pixels. There won't be other pixels.
In the second sample the following sequence of fights is possible: red and blue, green and red, red and blue. As a result, after all fights there is one green pixel left.
这道题的大致题意是：
很类似于以前我做过的一道变色龙的题目，就是给你三种颜色，然后叫你判断是否能把所有的颜色都变为一种颜色，但是这道题问法有变化，就是让你输出最少要几次才能使它们的颜色都变为一样，如果不可以就输出-1。
好吧，因为以前的那道题我没想清楚，所以这回我没有做出来，但是这回仔细的分析了一下，用公式推导了出来。
我们首先设有三个数：a[0],a[1],a[2],然后如果要使所有颜色都一样的话，那么肯定要有两种颜色相同才可以，这里选取哪两个来进行碰撞呢？用贪心法，每次都选两个最大的数字相碰，直到加到有两个数相等。
比如说“1，5，8” 因为1与5之间相差了偶数，所以肯定有一次能把他们变到相等的情况，
那么最少有几次呢？ t=(a[1]-a[0])/2+(a[1]-a[0])/2+a[0],其中前面的第一项代表的是a[0]与a[1]相互转化要几次，然后第二项与第三项相加代表的是转化后相等的数再转化到只有一种颜色要几次。
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
__int64 a[4];
int main(){
for(int i=0;i<3;i++) scanf("%I64d",&a[i]);
sort(a,a+3);
if((a[1]-a[0])%2==0) printf("%I64d\n",a[1]);
else printf("%I64d\n",a[2]);
return 0;
}
题意大致就是每次你都能选择一个区间l到r，然后使其中的数的值都增加1，然后问你最少几次能使这个序列变成不递减的序列。
好吧，我是模拟了几组数据，然后就发现最少的步数就是前后两个数字相减的绝对值，然后把它们加起来就好了。
其实也是算找规律题把。不过我竟然能看出来，不错啊，加油！
#include<stdio.h>
#include<string.h>
__int64 a[111111];
int main(){
int i,j,k,n;
scanf("%d",&n);
for(i=1;i<=n;i++) scanf("%I64d",&a[i]);
__int64 sum=0;
for(i=2;i<=n;i++){
if(a[i]<a[i-1]) sum+=a[i-1]-a[i];
}
printf("%I64d\n",sum);
}
A. Little Elephant and Intervaltime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output
The Little Elephant very much loves sums on intervals.
This time he has a pair of integers l and r (l ≤ r). The Little Elephant has to find the number of such integers x (l ≤ x ≤ r), that the first digit of integer x equals the last one (in decimal notation). For example, such numbers as 101, 477474 or 9 will be included in the answer and 47, 253 or 1020 will not.
Help him and count the number of described numbers x for a given pair l and r.
InputThe single line contains a pair of integers l and r (1 ≤ l ≤ r ≤ 1018) — the boundaries of the interval.
Please, do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use cin, cout streams or the %I64dspecifier.
OutputOn a single line print a single integer — the answer to the problem.
Sample test(s)input2 47output
12input
47 1024output
98Note
In the first sample the answer includes integers 2, 3, 4, 5, 6, 7, 8, 9, 11, 22, 33, 44.
好吧，这也是一道找规律的题，只不过我没想到那种规律罢了。
题意是：给你一个范围的区间，然后叫你判断在那个区间中有几个数满足首位和末位是相同的，并输出。
类似于数位dp的一道题，虽然说题目中没有包含0这个数，那么我们也可以把它算进去，然后两个端点相减就是答案，注意左端点。
规律就是前百位中有18个，然后按照位数来进行数的个数的增加，3位90个，4位900个。。。
然后分情况：1）若首位大于末位，那么就是取中间的那个数字然后再加上1，还有别忘了要加上在这个数之前的那些情况。至于为什么加1的原因是当首末两位相等的时候是肯定取的到的。
2）若首位小于末位，那么就直接取中间的那个数字就好。
然后还要注意一下只有个位数的情况。
#include<stdio.h>
#include<string.h>
#include<math.h>
__int64 l,r,sum1,sum2;
__int64 a[20];
int lnn[22];//保存每一位；
int getlen(__int64 n){
int len=0;
while(n){
lnn[len]=n%10;
n=n/10;
len++;
}
return len;
}
//注意一下这里求阶乘，不要用那个pow函数，因为会有误差；
__int64 fac(ints){
int i;
__int64 ans=1;
for(i=1;i<=s;i++) ans=ans*10;
return ans;
}
//这里是为了求出中间的那个数字；
__int64 getn(int ll,int rr){
int i;
__int64 j=1,ans=0;
for(i=ll;i<=rr;i++){
ans+=lnn[i]*j;
j=j*10;
}
//printf("%I64d\n",ans);
return ans;
}
int main(){
int i,j,k;
int len1=0,len2=0;
scanf("%I64d%I64d",&l,&r);
a[1]=10; a[2]=9;
a[3]=90;
for(i=4;i<=18;i++) a[i]=a[i-1]*10;
sum1=sum2=0;
len2=getlen(r);
//要单独讨论长度只有1的情况；
if(len2==1) sum2+=r+1;
for(i=1;i<len2;i++) sum2+=a[i];
__int64 s2=fac(len2-1);
__int64 ans=0;
if(r/s2>1&&len2!=1){
sum2+=a[len2]/9*(r/s2-1);
}
sum2+=getn(1,len2-2);
//这里是首位小于等于末尾的情况，那么要加1；
if(r/s2<=r%10&&len2!=1) sum2++;
memset(lnn,0,sizeof(lnn));
len1=getlen(l-1);
if(len1==1) sum1+=l;
for(i=1;i<len1;i++) sum1+=a[i];
__int64 s1=fac(len1-1);
if((l-1)/s1>1&&len1!=1){
sum1+=a[len1]/9*((l-1)/s1-1);
}
sum1+=getn(1,len1-2);
if((l-1)/s1<=(l-1)%10&&len1!=1) sum1++;
printf("%I64d\n",sum2-sum1);
}