1 1 1
butter

1 1 100
butter

1 1 900
bread

1 1 1000
bread

100 10 1000
butter

Help me please with the test number 3

#include<stdio.h>
int main()
{
    int n,i,j,item[9999],a,sum=0,temp;
    scanf("%d",&n);
    for(i=0; i<n; i++)
        scanf("%d",&item[i]);

    for(j=1; j<n; j++)
        for(a=n-1; a>=j; a--)
        {
            if(item[a-1]>item[a])
            {
                temp=item[a-1];
                item[a-1]=item[a];
                item[a]=temp;

            }
        }
        for(i=0; i<((n+1)/2); i++)
        {
            sum=sum+(item[a]+1)/2;
        }
        printf("%d\n",sum);
        return 0;
}

BinSearch.

Edited by author 14.07.2018 05:22

Do not use signed char (C++) or signed byte (C#) to store convivality, or you get wrong results because of overflow.

The test 5 is:
7
1
1
100
100
1
1
1
1 3
2 3
6 4
7 4
4 5
3 5
0 0

After you sum 100 + 100, you get -56 in the signed char/signed byte variable, while the right sum should be 200.

Hope this helps.

getting WA 39, can anyone please provide some test cases?

I got WA at #11. I had tested all tests on discussion and It's print right answer! Can anyone tell me some tricks? i don't know the mistake!!! What's #11???

I'm WA15 always.
My program passes all tests given there discussion, but can't AC.

Someone can give some test case to help with WA18, please?

Code:

#include <bits/stdc++.h>

using namespace std;

#define MAXN 2010
#define INF -1

typedef long long int lli;
typedef pair<lli,lli> ii;
typedef pair<ii,ii> pp;

lli gcd(lli a,lli b){
if(a<0) a=-a;
if(b<0) b=-b;

if(b==0) return a;
else return(gcd(b,a%b));
}

int maxPoint = 1,curMax, overlapPoints, xLine, yLine, zLine;
map<pp,int> slopeMap;

int main(){
int n;
//int x[MAXN],y[MAXN],z[MAXN];
lli x[MAXN],y[MAXN],z[MAXN];
scanf("%d",&n);

//for(int i=1;i<=n;i++) scanf("%d%d%d",&x[i],&y[i],&z[i]);
for(int i=1;i<=n;i++) scanf("%lld%lld%lld",&x[i],&y[i],&z[i]);

if(n==1) printf("%d\n",maxPoint);
else{
maxPoint = 0;
 for(int i=1;i<n;i++){
    curMax = overlapPoints = xLine = yLine = zLine = 0;

    for(int j=i+1;j<=n;j++){
        //int xDif = x[j] - x[i];
        //int yDif = y[j] - y[i];
        //int zDif = z[j] - z[i];
        lli xDif = x[j] - x[i];
        lli yDif = y[j] - y[i];
        lli zDif = z[j] - z[i];

        if(xDif == 0 && yDif == 0 && zDif == 0) overlapPoints++;
        else if(xDif == 0 && yDif == 0) zLine++;
        else if(xDif == 0 && zDif == 0) yLine++;
        else if(yDif == 0 && zDif == 0) xLine++;
        else if(xDif == 0){
            //int num1 = abs(yDif);
            //int den1 = abs(zDif);
            //int yz = gcd(num1,den1);
            lli num1 = abs(yDif);
            lli den1 = abs(zDif);
            lli yz = gcd(num1,den1);
            num1 /= yz;
            den1 /= yz;

            if((yDif > 0 && zDif > 0) || (yDif < 0 && zDif < 0)){
                slopeMap[make_pair(make_pair(num1,den1),make_pair(0,0))]++;
                curMax = max(curMax,slopeMap[make_pair(make_pair(num1,den1),make_pair(0,0))]);
            }
            else{
                slopeMap[make_pair(make_pair(-num1,den1),make_pair(0,0))]++;
                curMax = max(curMax,slopeMap[make_pair(make_pair(-num1,den1),make_pair(0,0))]);
            }
        }
        else if(yDif == 0){
            //int num1 = abs(xDif);
            //int den1 = abs(zDif);
            //int xz = gcd(num1,den1);
            lli num1 = abs(xDif);
            lli den1 = abs(zDif);
            lli xz = gcd(num1,den1);

            num1 /= xz;
            den1 /= xz;

            if((xDif > 0 && zDif > 0) || (xDif < 0 && zDif < 0)){
                slopeMap[make_pair(make_pair(num1,den1),make_pair(INF,INF))]++;
                curMax = max(curMax,slopeMap[make_pair(make_pair(num1,den1),make_pair(INF,INF))]);
            }
            else{
                slopeMap[make_pair(make_pair(-num1,den1),make_pair(INF,INF))]++;
                curMax = max(curMax,slopeMap[make_pair(make_pair(-num1,den1),make_pair(INF,INF))]);
            }
        }
        else if(zDif == 0){
            //int num1 = abs(xDif);
            //int den1 = abs(yDif);
            //int xy = gcd(num1,den1);
            lli num1 = abs(xDif);
            lli den1 = abs(yDif);
            lli xy = gcd(num1,den1);
            num1 /= xy;
            den1 /= xy;

            if((xDif > 0 && yDif > 0) || (xDif < 0 && yDif < 0)){
                slopeMap[make_pair(make_pair(INF,INF),make_pair(num1,den1))]++;
                curMax = max(curMax,slopeMap[make_pair(make_pair(INF,INF),make_pair(num1,den1))]);
            }
            else{
                slopeMap[make_pair(make_pair(INF,INF),make_pair(-num1,den1))]++;
                curMax = max(curMax,slopeMap[make_pair(make_pair(INF,INF),make_pair(-num1,den1))]);
            }
        }
        else{
            lli num1 = xDif*xDif + yDif*yDif;
            lli den1 = zDif*zDif;
            //int num2 = abs(xDif);
            //int den2 = abs(yDif);
            lli num2 = abs(xDif);
            lli den2 = abs(yDif);

            lli gcd1 = gcd(num1,den1);
            lli gcd2 = gcd(num2,den2);
            //int gcd2 = gcd(num2,den2);

            num1 /= gcd1;
            den1 /= gcd1;
            num2 /= gcd2;
            den2 /= gcd2;

            if((xDif < 0 && yDif > 0 && zDif > 0) || (xDif > 0 && yDif < 0 && zDif > 0)){
                slopeMap[make_pair(make_pair(num1,den1),make_pair(num2,den2))]++;
                curMax = max(curMax,slopeMap[make_pair(make_pair(num1,den1),make_pair(num2,den2))]);
               }
            else if((xDif < 0 && yDif < 0 && zDif < 0) || (xDif > 0 && yDif > 0 && zDif < 0)){
                slopeMap[make_pair(make_pair(-num1,den1),make_pair(-num2,den2))]++;
                curMax = max(curMax,slopeMap[make_pair(make_pair(-num1,den1),make_pair(-num2,den2))]);
            }
            else if((xDif < 0 && yDif < 0 && zDif > 0) || (xDif > 0 && yDif > 0 && zDif > 0)){
                slopeMap[make_pair(make_pair(num1,den1),make_pair(-num2,den2))]++;
                curMax = max(curMax,slopeMap[make_pair(make_pair(num1,den1),make_pair(-num2,den2))]);
            }
            else if((xDif < 0 && yDif > 0 && zDif < 0) || (xDif > 0 && yDif < 0 && zDif < 0)){
                slopeMap[make_pair(make_pair(-num1,den1),make_pair(num2,den2))]++;
                curMax = max(curMax,slopeMap[make_pair(make_pair(-num1,den1),make_pair(num2,den2))]);
            }
        }

        curMax = max(curMax,xLine);
        curMax = max(curMax,yLine);
        curMax = max(curMax,zLine);
    }

    maxPoint = max(maxPoint,curMax + overlapPoints + 1);
    slopeMap.clear();
}

printf("%d\n",maxPoint);
}
return 0;
}

Edited by author 13.07.2018 15:13

I am getting WA at 6 using floating arithmatic. Can someone please provide any test for test # 6?

Search for "Ellipsoidal cap volume" on the internet if you got stuck with this problem. You can find derivation of a formula needed for this problem.

I submitted my solution, but it says Test Case 2 didn't pass.
Could anyone tell me what the test case is?

The problem asks you to find the diameter of a tree.

If you have wa3 the following test may help you:

3 4
1 2 10 Pirated
1 2 11 Licensed
2 3 10 Pirated
2 3 8 Licensed

answer

Online
19

[code deleted]

Edited by author 07.01.2010 14:37

Help please!

I tried everything and cannot pass the second test .. any help?

You guys have to sort the roads to be the same sequence as the input
means first input,first output

Edited by author 04.07.2018 23:18

Edited by author 04.07.2018 23:18

Edited by author 04.07.2018 19:52