You are at a water bowling training. There are l people who play with their left hand, r people, who play with their right hand, and aambidexters, who can play with left or right hand.
The coach decided to form a team of even number of players, exactly half of the players should play with their right hand, and exactly half of the players should play with their left hand. One player should use only on of his hands.
Ambidexters play as well with their right hand as with their left hand. In the team, an ambidexter can play with their left hand, or with their right hand.
Please find the maximum possible size of the team, where equal number of players use their left and right hands, respectively.
The only line contains three integers l, r and a (0 ≤ l, r, a ≤ 100) — the number of left-handers, the number of right-handers and the number of ambidexters at the training.
Print a single even integer — the maximum number of players in the team. It is possible that the team can only have zero number of players.
1 4 2
6
5 5 5
14
0 2 0
0
In the first example you can form a team of 6 players. You should take the only left-hander and two ambidexters to play with left hand, and three right-handers to play with right hand. The only person left can't be taken into the team.
In the second example you can form a team of 14 people. You have to take all five left-handers, all five right-handers, two ambidexters to play with left hand and two ambidexters to play with right hand.
1 #include <iostream> 2 #include <string> 3 #include <algorithm> 4 #include <string.h> 5 #include <cstring> 6 #include <math.h> 7 #include <stdio.h> 8 9 #define mem(a) memset(a,0,sizeof(a)) 10 #define maxn 150 11 #define ll long long 12 using namespace std; 13 int a[maxn],b[maxn]; 14 15 int main(){ 16 ios::sync_with_stdio(0); 17 int l,r,a; 18 cin>>l>>r>>a; 19 if(l+a>=r&&r+a>=l){ 20 printf("%d ",(l+r+a)/2*2); 21 }else{ 22 printf("%d ",min(l+a,r+a)*2); 23 } 24 return 0; 25 }
Hacker Zhorik wants to decipher two secret messages he intercepted yesterday. Yeah message is a sequence of encrypted blocks, each of them consists of several bytes of information.
Zhorik knows that each of the messages is an archive containing one or more files. Zhorik knows how each of these archives was transferred through the network: if an archive consists of k files of sizes l1, l2, ..., lk bytes, then the i-th file is split to one or more blocks bi, 1, bi, 2, ..., bi, mi (here the total length of the blocks bi, 1 + bi, 2 + ... + bi, mi is equal to the length of the file li), and after that all blocks are transferred through the network, maintaining the order of files in the archive.
Zhorik thinks that the two messages contain the same archive, because their total lengths are equal. However, each file can be split in blocks in different ways in the two messages.
You are given the lengths of blocks in each of the two messages. Help Zhorik to determine what is the maximum number of files could be in the archive, if the Zhorik's assumption is correct.
The first line contains two integers n, m (1 ≤ n, m ≤ 105) — the number of blocks in the first and in the second messages.
The second line contains n integers x1, x2, ..., xn (1 ≤ xi ≤ 106) — the length of the blocks that form the first message.
The third line contains m integers y1, y2, ..., ym (1 ≤ yi ≤ 106) — the length of the blocks that form the second message.
It is guaranteed that x1 + ... + xn = y1 + ... + ym. Also, it is guaranteed that x1 + ... + xn ≤ 106.
Print the maximum number of files the intercepted array could consist of.
7 6
2 5 3 1 11 4 4
7 8 2 4 1 8
3
3 3
1 10 100
1 100 10
2
1 4
4
1 1 1 1
1
In the first example the maximum number of files in the archive is 3. For example, it is possible that in the archive are three files of sizes 2 + 5 = 7, 15 = 3 + 1 + 11 = 8 + 2 + 4 + 1 and 4 + 4 = 8.
In the second example it is possible that the archive contains two files of sizes 1 and 110 = 10 + 100 = 100 + 10. Note that the order of files is kept while transferring archives through the network, so we can't say that there are three files of sizes 1, 10 and 100.
In the third example the only possibility is that the archive contains a single file of size 4.
1 #include <iostream> 2 #include <string> 3 #include <algorithm> 4 #include <string.h> 5 #include <cstring> 6 #include <math.h> 7 #include <stdio.h> 8 9 #define mem(a) memset(a,0,sizeof(a)) 10 #define ll long long 11 using namespace std; 12 const int maxn=1e5+10; 13 int a[maxn]; 14 int b[maxn]; 15 16 int main(){ 17 ios::sync_with_stdio(0); 18 int m,n; 19 mem(a); 20 mem(b); 21 cin>>m>>n; 22 for(int i=0;i<m;i++){ 23 cin>>a[i]; 24 } 25 for(int i=0;i<n;i++){ 26 cin>>b[i]; 27 } 28 int x=0,y=0,t=0,ans=0; 29 for(int i=0;i<m;i++){ 30 x+=a[i]; 31 while(y<x&&t<n) y+=b[t++]; 32 if(x==y) { 33 ++ans; 34 x=y=0; 35 } 36 } 37 printf("%d ",ans); 38 return 0; 39 }
Oleg writes down the history of the days he lived. For each day he decides if it was good or bad. Oleg calls a non-empty sequence of days a zebra, if it starts with a bad day, ends with a bad day, and good and bad days are alternating in it. Let us denote bad days as 0 and good days as 1. Then, for example, sequences of days 0, 010, 01010 are zebras, while sequences 1, 0110, 0101 are not.
Oleg tells you the story of days he lived in chronological order in form of string consisting of 0 and 1. Now you are interested if it is possible to divide Oleg's life history into several subsequences, each of which is a zebra, and the way it can be done. Each day must belong to exactly one of the subsequences. For each of the subsequences, days forming it must be ordered chronologically. Note that subsequence does not have to be a group of consecutive days.
In the only line of input data there is a non-empty string s consisting of characters 0 and 1, which describes the history of Oleg's life. Its length (denoted as |s|) does not exceed 200 000 characters.
If there is a way to divide history into zebra subsequences, in the first line of output you should print an integer k (1 ≤ k ≤ |s|), the resulting number of subsequences. In the i-th of following k lines first print the integer li (1 ≤ li ≤ |s|), which is the length of the i-th subsequence, and then li indices of days forming the subsequence. Indices must follow in ascending order. Days are numbered starting from 1. Each index from 1 to n must belong to exactly one subsequence. If there is no way to divide day history into zebra subsequences, print -1.
Subsequences may be printed in any order. If there are several solutions, you may print any of them. You do not have to minimize nor maximize the value of k.
0010100
3
3 1 3 4
3 2 5 6
1 7
111
-1
按照零分解
0
01010
0
1 #include <vector> 2 #include <algorithm> 3 #include <string> 4 #include <string.h> 5 #include <cstring> 6 #include <stdio.h> 7 8 using namespace std; 9 const int maxn=2e5+10; 10 vector<int> v[maxn]; 11 char s[maxn]; 12 13 int main(){ 14 scanf("%s",s+1); 15 int ans=0; 16 int maxx=0; 17 int len=strlen(s+1); 18 for(int i=1;i<=len;++i){ 19 if(s[i]=='0') v[++ans].push_back(i); 20 else{ 21 if(ans==0) return puts("-1"),0; 22 v[ans--].push_back(i); 23 } 24 maxx=max(maxx,ans); 25 } 26 if(maxx!=ans) return puts("-1"),0; 27 printf("%d ",maxx); 28 for(int i=1;i<=maxx;i++){ 29 printf("%d",v[i].size()); 30 for(int j=0;j<v[i].size();++j){ 31 printf(" %d",v[i][j]); 32 } 33 printf(" "); 34 } 35 return 0; 36 }
Dima is a beginner programmer. During his working process, he regularly has to repeat the following operation again and again: to remove every second element from the array. One day he has been bored with easy solutions of this problem, and he has come up with the following extravagant algorithm.
Let's consider that initially array contains n numbers from 1 to n and the number i is located in the cell with the index 2i - 1 (Indices are numbered starting from one) and other cells of the array are empty. Each step Dima selects a non-empty array cell with the maximum index and moves the number written in it to the nearest empty cell to the left of the selected one. The process continues until all n numbers will appear in the first n cells of the array. For example if n = 4, the array is changing as follows:
You have to write a program that allows you to determine what number will be in the cell with index x (1 ≤ x ≤ n) after Dima's algorithm finishes.
The first line contains two integers n and q (1 ≤ n ≤ 1018, 1 ≤ q ≤ 200 000), the number of elements in the array and the number of queries for which it is needed to find the answer.
Next q lines contain integers xi (1 ≤ xi ≤ n), the indices of cells for which it is necessary to output their content after Dima's algorithm finishes.
For each of q queries output one integer number, the value that will appear in the corresponding array cell after Dima's algorithm finishes.
4 3
2
3
4
3
2
4
13 4
10
5
4
8
13
3
8
9
The first example is shown in the picture.
In the second example the final array is [1, 12, 2, 8, 3, 11, 4, 9, 5, 13, 6, 10, 7].
找规律
实在想不出来看这个
http://blog.csdn.net/xiangAccepted/article/details/79506332
1 #include <vector> 2 #include <algorithm> 3 #include <string> 4 #include <string.h> 5 #include <cstring> 6 #include <stdio.h> 7 8 using namespace std; 9 const int maxn=2e5+10; 10 typedef long long ll; 11 12 vector<int> v[maxn]; 13 char s[maxn]; 14 int a[45]; 15 /* 16 memset(a,0,sizeof(a)); 17 for(int n=1;n<=20;++n){ 18 printf("%2d: ",n); 19 for(int i=1;i<=n;i++){ 20 a[2*i-1]=i; 21 } 22 int j=2*n-2,i=2*n-1; 23 while(j){ 24 while(!a[i]) i--; 25 a[j]=a[i--]; 26 j-=2; 27 } 28 for(int i=1;i<=n;i++){ 29 printf(" %d",a[i]); 30 } 31 printf(" "); 32 } 33 */ 34 int main(){ 35 ll n,q; 36 scanf("%I64d%I64d",&n,&q); 37 while(q--){ 38 ll x; 39 scanf("%I64d",&x); 40 if(x%2==1){ 41 printf("%I64d ",x/2+1); 42 continue; 43 } 44 ll m=n; 45 while(x%2==0){ 46 x=m-x/2; 47 m=x; 48 } 49 printf("%I64d ",n-x+(x+1)/2); 50 } 51 return 0; 52 }