Give that test, pls...

What an amusing problem! Now it seems to be easy - in contrast to prima facie :^) Special thanks to Vorokh Sergey and Mamonov Anton, who proved correctness of my solution.

And some test data

input #1:
0 0 90 5
5 4.9
output #1:
28.2176

input #2:
0 0 90 5
0 -0.000001
output #2:
31.4159

I can't understand why. Can anybody help me?

try this:
aaaba

is
2
aa aba

not
3
aaa b a

WA #7 can anyone help plz?

using simple dp

var
 AD,AC,BD,BC,X,Y:int64;
 CD:real;

BEGIN
 read(AD,AC,BD,BC);

 X:=AD*AC-BD*BC;
 Y:=AD*AC*(BD*BD+BC*BC)-BD*BC*(AD*AD+AC*AC);
 if(X=0)or(Y*X<0) then write('Impossible.')
 else begin
  write('Distance is ');
  CD:=1000*sqrt(Y/X);
  write(CD:0:0,' km.');
 end;
END.

Why Wa18? What is test?

Why Runtime Error?

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
    unsigned short n, m;
    scanf("%hu", &n);
    vector <unsigned long long> bytes(n);
    vector <vector<unsigned short> > red(n);
    for(unsigned short i=0;i<n;i++) scanf("%llu", &bytes[i]);
    for(unsigned short i=1;i<n;i++) {
        unsigned short x, y;
        scanf("%hu %hu", &x, &y);
        red[x-1].push_back(y);
        red[y-1].push_back(x); }
    if(n>1) {
        for(unsigned short i=0;i<red.size();i++) sort(red[i].begin(), red[i].end());
        for(unsigned short i=0;i<red.size();i++) {
            for(unsigned short j=0;j<red[i].size()-1;j++) {
                if(red[i][j]==red[i][j+1]) {
                    for(unsigned short pos=j+1;pos<red[i].size()-1;pos++) red[i][pos] = red[i][pos+1];
                    red[i].pop_back(); }
            }
        }
    }
    scanf("%hu", &m);
    for(int i=0;i<m;i++) {
        unsigned short v, t;
        scanf("%hu %hu", &t, &v);
        if(t==1) {
            for(unsigned j=0;j<red[v-1].size();j++) bytes[red[v-1][j]-1] += bytes[v-1]; }
        if(t==2) printf("%llu\n", bytes[v-1]%1000000007); }
}

I use a simple DP ,but WA#10.Give me some useful tests,pls.
And I'd like to know if there is a better algo.

Recursive solution works fine! If you are getting TLE, Rethink your DP state :)

When my sort compare function is:
bool cmp(pair<int, int> p1, pair<int, int> p2)
{
    if(p1.first != p2.first)
        return p1.first < p2.first;
    else
        return p1.second >= p2.second;
}

I get WA#14.
And then delete the "=" like :
bool cmp(pair<int, int> p1, pair<int, int> p2)
{
    if(p1.first != p2.first)
        return p1.first < p2.first;
    else
        return p1.second > p2.second;
}
I get AC;

Try this test:
5
0 3
3 5
5 7
0 0

AC answer is:
2
0 3
3 5

not:
3
0 3
3 5
5 7

Input: 1440 5723
Output: 7163

Input: -2972 -2411
Output: -5383

Input: 6307 4686
Output: 10993

Input: 5185 -2017
Output: 3168

Input:

7
1 1 1 1 1 1 1
1 2
1 3
1 4
1 5
2 6
2 7
9
1 1
1 1
1 1
1 1
1 1
1 6
2 2
1 2
2 7

output:
7
8

I used segment tree, but got wa on testcase 6

This is when there's only one pole.
1
1 2
The answer should be:
1
1

what's is the wrong with this solution ?: i find the shortest path from the first vertx in the chain to the last ( with bfs) an print that path.i read my code , and I think it's correct ,say if I misunderstood the problem

CODE:-

import java.util.*;
public class titans
{
    public static void main (String[] args) throws java.lang.Exception
    {
        int ind = 0; int w = 0;
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int a[] = new int[n];
        for (int i = 0; i < n; i++)
        {
            a[i] = sc.nextInt();
        }
        int largest = a[0] + a[1] + a[2];
        if (n%2 != 0 )
        {
            w = (n/2) + 1;
        }
        else
        {
            w = n/2;
        }
        for (int j = 0; j <= w; j++)
        {
            int new_long = a[j] + a[j+1] + a[j+2];
            if (new_long >= largest)
            {
                largest = new_long;
                ind = j + 2;
            }
        }
        System.out.println(largest + " " + ind);
    }
}
----------------------------------------------------------
Please tell where am I going wrong. The code is working fine on my system. Thanks in advance.
-----------------------------------------------------------
Thanks for your time but I have found the solution - thanks again!

Edited by author 28.11.2015 19:30

I solved this problem with a non-greedy solution.
Basically there are only one of the following 4 cases:
1. total number of '+' is <= 2N, problem solved;
2. There exists one column without any '+', and there also exists one column with more than 2 '+'(i.e. at least three), in this case you can "move" that two '+'s to the empty column (through two permutations);
3. Similar condition for case 2, move the row;
4. None of above is satisfied, using Hungarian Algorithm to find a best traversal.

Repeat above process until case 1 is reached.

This is not greedy and we can prove that it is correct:
Both case 2 and 3 guarantees that 1) the total number of '+'s does not change, and 2) cannot continue infinitely, i.e. it must reach case 4 at some point.
Then case 4 guarantees the total number of '+'s will be reduced at least by 1 (due to the fact that 2N + 1 is odd, and neither case 2 and case 3 is satisfied, can be easily proved)

Code:
 const Nmax=155000;
var
 Z,L1,R1:array[1..Nmax] of longint;
 A:array[1..Nmax] of char;
 N,M,Middle,L,R,i,j,k:longint;
 ch:char;

function Min(x,y:longint):longint;
begin
 if(x>y) then x:=y;
 Min:=x;
end;

BEGIN
 N:=0;
 read(ch);
 while(ord(ch)>=ord('a')) do begin
  inc(N);
  A[N]:=ch;
  read(ch);
 end;
 readln;

 inc(N);
 A[N]:='#';
 M:=N;
 read(ch);
 while(ord(ch)>=ord('a')) do begin
  inc(N);
  A[N]:=ch;
  read(ch);
 end;

 Z[1]:=N;
 R:=0;
 L:=0;

 for i:=2 to N do begin
  if(i<=r) then Z[i]:=min(R-i+1,Z[i-L+1])
  else Z[i]:=0;
  while(i+z[i]<=N)and(A[i+z[i]]=A[z[i]+1]) do inc(z[i]);
  if(i+z[i]-1>r) then begin
   L:=i;
   R:=i+z[i]-1;
  end;
 end;

 k:=0;
 L1[k]:=N+1;
 R1[k]:=N+1;

 i:=N;
 while(i>=M+1) do begin
  if(i+z[i]-1>=L1[k]-1) then begin
   inc(k);
   L1[k]:=i;
   R1[k]:=L1[k-1]-1;
  end;
  dec(i);
 end;

 if(L1[k]=M+1) then begin
  writeln('No');
  while(k>0) do begin
   for i:=L1[k] to R1[k] do write(A[i]);write(' ');
   dec(k);
  end;
 end
 else begin
  writeln('Yes');
 end;
END.