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.

In what position brick can fall through the hole? Why program like follows doesn't work properly?

var
 a, b, c, d, e: real;
begin
 readln(a, b, c, d, e);
  if (a<=d)and(b<=e)or
     (a<=e)and(b<=d)or
     (a<=d)and(c<=e)or
     (a<=e)and(c<=d)or
     (b<=d)and(c<=e)or
     (b<=e)and(c<=d) then
    writeln('YES')
  else
    writeln('NO')
end.

Please, tell me some tests to check my program...
I have WA#2

Give me test#12, please. I tried all tests in the discussions, but still WA12

Edited by author 27.01.2014 14:42

Решая задачу обыватель мог столкнуться с проблемой того,как вводить данные. Данные водятся потоком, поэтому мы не знаем какое количество чисел войдут на проверку, для этого нам нужно использовать следующую конструкцию:

var
r:real;
..
Begin
while not seekeof do
Begin
read(r);
..
End;
..
End.

while not seekeof do - пока не конце файла, то делай то то. пропуская пробелы и переходы на новую строчку. Но так как отсутствует файлы, то он ждёт конец потока вводимых с экрана данных.
Для решения просто вставляем эту конструкцию, дополняя кодом и всё.
http://acm.timus.ru/help.aspx?topic=pascal

Edited by author 28.11.2015 11:30

here is my code if someone can help me, thanks you and greetings.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Scanner;

public class P1100 {

    public static void main(String[] args) {
       Scanner in = new Scanner(System.in);
        PrintWriter out = new PrintWriter(System.out);

        int n = in.nextInt();
        int [] vec=new int[n*2];
        for(int i=0;i<n*2;i++)vec[i]=in.nextInt();
        int [] aux=new int[n];
        int mayor=0,menor=100;
        for(int i=1;i<n*2;i=i+2){
            if(menor>vec[i]){
                menor=vec[i];
            }
            if(mayor<vec[i]){
                mayor=vec[i];
            }
        }
        int sig=-1;
        for(int i=0;i<n;i++){
            for(int j=1;j<n*2;j=j+2){
               if(mayor==vec[j] && vec[j]!=-1 ){
                   System.out.printf(" %d %d",vec[j-1],vec[j]);
                   vec[j]=-1;

               }
               if(sig<mayor && sig < vec[j] && vec[j]!=-1){
                   sig=vec[j];
               }
            }
            mayor=sig;
            sig=-1;

        }
        out.flush();

    }
}

Hi.
Is O(N^2) solution good for this problem? I got TL on 8th test. Should I reduce constant in O() or should I find N*logN solution? It's strange that 25M operations take over 2 seconds.

I use Python 3.5
Is it right that it's prohibited to import function gcd from library math?
But it's allowed to import this function from library fractions

Edited by author 27.11.2015 02:04

If there is three equal points than perimeter equals zero?

I know i am stupid but help me to understand this formula!
n*(n+1)/2*(n+2)

Edited by author 02.11.2013 03:06

Edited by author 02.11.2013 03:12

// del
got AC

Edited by author 26.11.2015 22:07

Edited by author 27.03.2016 21:21

here is my code if someone can help me, thanks you and greetings.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Scanner;

public class P1100 {

    public static void main(String[] args) {
       Scanner in = new Scanner(System.in);
        PrintWriter out = new PrintWriter(System.out);

        int n = in.nextInt();
        int [] vec=new int[n*2];
        for(int i=0;i<n*2;i++)vec[i]=in.nextInt();
        int [] aux=new int[n];
        int mayor=0,menor=100;
        for(int i=1;i<n*2;i=i+2){
            if(menor>vec[i]){
                menor=vec[i];
            }
            if(mayor<vec[i]){
                mayor=vec[i];
            }
        }
        int sig=-1;
        for(int i=0;i<n;i++){
            for(int j=1;j<n*2;j=j+2){
               if(mayor==vec[j] && vec[j]!=-1 ){
                   System.out.printf(" %d %d",vec[j-1],vec[j]);
                   vec[j]=-1;

               }
               if(sig<mayor && sig < vec[j] && vec[j]!=-1){
                   sig=vec[j];
               }
            }
            mayor=sig;
            sig=-1;

        }
        out.flush();

    }
}

import java.io.PrintWriter;
import java.util.Scanner;


public class P1581 {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        PrintWriter out = new PrintWriter(System.out);

        int n = in.nextInt();
        int [] vec=new int[n];
        for(int i=0;i<n;i++)vec[i]=in.nextInt();
        int cont=0,num;
        num=vec[0];
        for(int i=0;i<n;i++){
          if(vec[i]==num){
              cont=cont+1;
          }
          if(vec[i]!=num || i+1==n){
              if(i+1!=n){
              System.out.printf("%d %d ",cont,num);
              }else{
                  System.out.printf("%d %d",cont,num);
              }
              num=vec[i];
              cont=1;
            }

        }
        out.flush();
    }
}

----
THANKS YOU, GREETINGS.

Edited by author 26.11.2015 05:45