Given availability of 3 types of leaves and availability of 3 different colors for each type of a leaf find out what is the maximum number of leaves that can be chosen in such a way that all chosen leaves are of the same type or of the same color and the number of chosen leaves is odd. If there is no way to choose the leaves according to these rules, then answer is 0. In one test file there are multiple test cases to handle.
QUICK EXPLANATION:
First, for each type of leaves calculate the result when only leaves of this type are chosen. Next, for each color of leaves also calculate the result when only leaves of this color are chosen. Since there are 3 types and 3 colors, then the final result is the maximum from these total 6 possibilities.
EXPLANATION:
Subtask 1
In the first subtask there are at most 5 leaves of any type and color in any test case. This allows some solutions taking advantage of this fact to pass test cases with such low constraints. On can for example try to iterate over all possible sizes of the resulting bouquet and for each such size decide if it is possible to create it.
Subtask 2
In the second subtask there are up to 10^9 leaves of any type and color, however, the task is still very easy. Since in the result all leaves has to have the same type or the same color (both type and color are also valid), we can iterate over all types first and for each type, sum up all the leaves of this type and subtract 1 from this sum if it is even (because we want the number of chosen leaves to be odd). After that, we can do the same with color, i.e. iterate over all colors and for each color sum up all the leaves of this color and subtract 1 from this sum if it is even. The final result is the maximum from these 6 values computed this way.
Let c[i][j] denotes the number of leaves from the i-th type and the j-th. The below pseudocode illustrates the approach:
res = 0
for i = 1 to 3:
subres = c[i][1] + c[i][2] + c[i][3]
if subres % 2 == 0
subres = subres - 1
res = max(res, subres)
for j = 1 to 3:
subres = c[1][j] + c[2][j] + c[3][j]
if subres % 2 == 0
subres = subres - 1
res = max(res, subres)
print res
Last but not least, be aware that the result can be bigger than 32-bit integer.
AUTHOR’S AND TESTER’S SOLUTIONS:
Setter’s solution will be posted soon.
Tester’s solution can be found here.
Editorialist’s solution can be found here.
#include<bits/stdc++.h>
using namespace std;
//#include<iostream.h>
int main()
{
int T,i;
long long int mg,my,mr,og,oy,ori,pg,py,pr;
cin>>T;
//while(T)
for(i=0;i<T;i++)
{
cin>>mg>>my>>mr;
cin>>og>>oy>>ori;
cin>>pg>>py>>pr;
if((mr+mg+my)>0||(ori+oy+og)>0||(py+pg+pr)>0){
without any loop
int main()
{
int t;long long y1,y2,y3,g1,g2,g3,r1,r2,r3;
scanf("%d",&t);
while(t–)
{
unsigned long long ans=0;
scanf("%lld%lld%lld",&g1,&y1,&r1);
scanf("%lld%lld%lld",&g2,&y2,&r2);
scanf("%lld%lld%lld",&g3,&y3,&r3);
long long a=g1+g2+g3,b=y1+y2+y3,c=r1+r2+r3;
long long d=g1+y1+r1;
long long e=g2+y2+r2;
long long f=g3+y3+r3;
if(a>=b && a>=c)
ans=a;
else if(b>=a && b>=c)
ans=b;
else if(c>=b && c>=a)
ans=c;
i think some more cases should also be considered
example consider this case
if c[i][1] + c[i][2] + c[i][3] is odd for all i=1 to 3 then it will not contribute to answer
now also res=0
also if c[1][j] + c[2][j] + c[3][j] is odd for all j=1 to 3 then it will not contribute to answer
now also res=0
but still possibilities are there to make res !=0
example
c[i][1] + c[i][2] for i=1 to 3 and it is even and greater than zero which is not considered and lead to res non zero(towards maximum)
also
consider this possibilities
c[i][2] + c[i][3] for i=1 to 3
also c[i][1] + c[i][3] for i=1 to 3
this were few other possibilities for same leaf different color(all leaves of same type)
similarly other possibilities for
c[1][j] + c[2][j] and j=1 to 3 and its is even and greater than res=0
but not considered
@pkacprzak
i think some more cases should also be considered
example consider this case if c[i][1] + c[i][2] + c[i][3] is odd for all i=1 to 3 then it will not contribute to answer
now also res=0
also if c[1][j] + c[2][j] + c[3][j] is odd for all j=1 to 3 then it will not contribute to answer
now also res=0
but still possibilities are there to make res !=0
example
c[i][1] + c[i][2] for i=1 to 3 and it is even and greater than zero which is not considered and lead to res non zero(towards maximum)
also
consider this possibilities
c[i][2] + c[i][3] for i=1 to 3
@vijayiota77 I don’t know exactly what you are talking about. If the sum of leaves of the same type or color is odd, we take all of them. If it’s even, then the best we can do is to take all minus one such leaf.
