I've used Ford-Fulkerson algo and got TL on test 22.(in java)

What is the O(N^2) solution of this problem?

I wrote simply Kraskal & DFS with assimptoty O(E * Log(E) + V * E) and got Accepted in 1.156... I want to know O(N^2) solution of this problem...

Подскажите, добрые люди, как же сделать так, чтобы не отправлять по сто раз решения на сервер, чтобы узнать работают они или нет.. для этого нужно отлаживать программу с помощью текстовых файлов, как же с ними работать?
для паскаля в руководстве написано вот это:
var
   a, b: longint;
begin
{$IFNDEF ONLINE_JUDGE}
   assign(input, 'input.txt');
   reset(input);
   assign(output, 'output.txt');
   rewrite(output);
{$ENDIF}
   readln(a, b);
   writeln(a + b);
{$IFNDEF ONLINE_JUDGE}
   close(input);
   close(output);
{$ENDIF}
end.
может кто-нибудь написать такую же для python3???

#include<iostream>
#include<string>
using namespace std;
int main()
{
    int n,k=0;
    char t,s;
    cin>>n;
    string a[1001];
    for(int i=0;i<n;i++)
        cin>>a[i];
    for(int i=0;i<n-1;i++)
    {
        t=a[i][0];
        s=a[i+1][0];

        if((t=='A' || t=='P' || t=='O' || t=='R') &&
           (s=='A' || s=='P' || s=='O' || s=='R'))
           k+=0;
        if((t=='A' || t=='P' || t=='O' || t=='R') &&
           (s=='B' || s=='M' || s=='S'))
           k+=1;
        if((t=='A' || t=='P' || t=='O' || t=='R') &&
           (s=='D' || s=='G' || s=='J' || s=='K' || s=='T' || s=='W'))
           k+=2;

        if((t=='B' || t=='M' || t=='S') &&
           (s=='B' || s=='M' || s=='S'))
           k+=0;
        if((t=='B' || t=='M' || t=='S') &&
           (s=='A' || s=='P' || s=='O' || s=='R'||
            s=='D' || s=='G' || s=='J' || s=='K' || s=='T' || s=='W'))
           k+=1;

        if((t=='D' || t=='G' || t=='J' || t=='K' || t=='T' || t=='W') &&
           (s=='D' || s=='G' || s=='J' || s=='K' || s=='T' || s=='W'))
           k+=0;
        if((t=='D' || t=='G' || t=='J' || t=='K' || t=='T' || t=='W') &&
           (s=='B' || s=='M' || s=='S'))
           k+=1;
        if((t=='D' || t=='G' || t=='J' || t=='K' || t=='T' || t=='W') &&
           (s=='A' || s=='P' || s=='O' || s=='R'))
           k+=2;
    }

    cout<<k;
    return 0;
}

Edited by author 27.07.2018 02:09

w = N/t
h = g*t*t/2
this is also if l/2 >= h you must print "BUTTER" and you stop your program else continue

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