a=int(input())
b=int(input())
i=a
w=0
while i<=b:
    w=w+1
    i=i+2
if (a%10==0):
    w=w-1
print(w)

1. DP,  f[i][j] represents when solving the substring from index i to j the minimum brackets should add. Then we have
    1) i <= j
    2) if i == j, then f[i][j] = 1. (you can add a bracket to match the one)
    3) if i < j, then f[i][j] = min(f[i][k], f[k+1][j])   i<=k<=(j-1)
    4) that's not the end.... a case when s[i] == s[j], get f[i+1][j-1]. should compare this value to above values in (3), and get the maximum.
 2. how to show the results
    when calculate f[i][j], you can use an array like ans[i][j] to record the way to get f[i][j]. for example, when f[i][j] get maximum when k = k1. so you can record k1 to ans[i][j]. Or f[i+1][j-1] get the maximum , you can record -1 to ans[i][j], or in the case i==j you get the maximum, set ans[i][j] to 0......
    Then you can get result by DFS.

hope it helps :)

as other participants i used dp. there are different explanations of dp approach, but somehow i find them pretty blurry. when calculating the min number of brackets to be added for the substring, i think there should be done only 2 simple steps:

1) check whether the substring is already correct - can be done using stack in linear time. if this happens to be true, than no sense going to step 2
2) if s is substring and d[i][j] is used for storing dynamic for substring of i length starting at j, then solution is:
d[i][j] = min(d[i - 2][j + 1] if s[j] == s[i + j], min(d[k][j] + d[i - k][j + k]) for 1 <= k < i))

why the 2nd step has that condition? that goes from the the problem definition itself. we can form regular sequence either from wrapping it in brackets, eg '(  (....)  )' or with concatenating two regular sequences, eg '( ...)    [ ... ]'.

hope this explanation brings some clarity on the approach.

How can I solve this problem by using segment tree??

import sys
n,m=map(int,input().split())
n1=n
m1=m
j=0
ans=0
if n1==1 or m1 ==1:
    print(0)
    sys.exit()
while n1>0 and m1>0:
    if ans%2==0 and j!=0:
        if m1>0:
            m1-=1
            ans+=1
            j+=1
        else:
            print(ans)
            sys.exit()
    elif ans%2==1 and j!=0:
        if n1>0:
            n1-=1
            ans+=1
            j+=1
    else:
        n1-=1
        m1-=1
        ans+=1
        j+=1
print(ans)

Does not pass even the first test.

Cod:

telefon={"i":1,"j":1,"a":2,"b":2,"c":2,"d":3,"e":3,"f":3,"g":4,"h":4,"k":5,"l":5,"m":6,"n":6,"p":7,"r":7,"s":7,"t":8,"v":8,"u":8,"w":9,"x":9,"y":9,"o":0,"q":0,"z":0}


def sortirovka(nomerok,slovarik):
    nomerok = str(nomerok)
    o=len(nomerok)
    k=[]
    for i in range(len(slovarik)):
        if len(slovarik[i])<=o:
            k.append(slovarik[i])
    return k

def perevod(slovarik):
    k=[]
    for i in range(len(slovarik)):
        p=''
        for o in range(len(slovarik[i])):
            c=telefon[slovarik[i][o]]
            p=p+str(c)
        k.append(p)
    return k

def bolodn(slovara,nomera):
    i=0
    l=[]
    z=0
    u=len(str(nomera))
    while i != len(slovara):
        n = int(len(str(slovara[i])))
        if slovara[i] == str(nomera)[0:n]:
            l.append(slovara[i])
            z+=len(slovara[i])
            nomera = str(nomera)[n:]
        i += 1
    if z==u:
        return l


def sdvig(l, p):
    return l[-p:] + l[:-p]


while True:

    nomer=int(input())
    if nomer == -1:
        break
    if nomer != -1:
        vslovare=int(input())
    i=0

    slovar=[]
    while i!=vslovare:
        c=input()
        slovar.append(c)
        i+=1



    slovar=sortirovka(nomer,slovar)

    slovar1=slovar
    slovar=(perevod(slovar))


    y={}
    for i in range(len(slovar1)):
        d=slovar1[i]
        d1=slovar[i]
        y[d1]=d

    for i in range(1):
        a=0
        z=[]
        while a!=len(slovar):

            k=bolodn(slovar,nomer)
            if k!=None:
                z.append(k)
            slovar=sdvig(slovar,1)
            a+=1

        if len(z)==0:
            print ("No solution.")
        if len(z)>0:

            b=len(z)-1
            min=len(z[0])
            t=0
            i=1
            if (len(z))>1:
                while i!=len(z):
                    if int(len(z[i]))<int(min):
                        min=z[i]
                        t=i
                    i+=1
                x = z[t]
            else:

                x=z[t]

            if len(x)>=1:
                j=''
                for i in range(len(x)):
                    ss=x[i]
                    j+=str(y[ss])
                    if i<len(x)-1:
                        j+=' '
                print (j)

Using long long hashes, any ideas?

I'm write on Python. Can anybody help me with this test?

As i read the problem, the configuration of two first rows are :

Window | A | Aisle | B | C | Aisle | D | Window

I check with my program and for 1A 'window' is AC while 'aisle' gives WA6


Edited by author 30.10.2011 20:54

Edited by author 30.10.2011 20:54

it should delete the first 8:00:00 in the input

I thought i'll never get AC at this problem, but after some time i wrote that very nice (as for me ^___^) functions doing the work.

void a( int n, int k )
{
-printf("sin(%d",k);
-if ( k < n )
-{
--if ( k % 2 )
---printf("-");
--else
---printf("+");
--a( n, k + 1 );
-}
-printf(")");
}

void s( int n, int k )
{
-if ( k < n )
-{
--printf("(");
--s( n, k + 1 );
--printf(")");
-}
-a( n - k + 1, 1 );
-printf("+%d",k);
}

For answer just need to call s( n, 1 ).
Good luck!

Edited by author 20.03.2010 18:23

Hi guys,

Could you please share any hint on how to optimize backtracking?

I've been trying to solve this problem, but it seems that I haven't got the idea good enough: my precalculation has been working for an hour and there's still N>45 cases to solve. :-)

Edited by author 10.07.2012 10:14

I think can set a challege problem  with range n<=1e5...

Hello ,
Can someone please tell me why I am getting wrong answer for test case 5?
I have used straight forward approach.
```
#include <stdio.h>
  2
  3 int group_distribution[10001];
  4
  5 void insertion_sort( int * arr, int size) {
  6     int i , j, key;
  7     for ( i = 1; i < size; i ++ ) {
  8         key = arr[i];
  9         j = i - 1;
 10         while ( arr[j] > key && j >= 0 ) {
 11             arr[j + 1] = arr[ j ];
 12             j = j - 1;
 13         }
 14         arr[ j + 1 ] = key;
 15     }
 16 }
 17
 18 int main( int argc, char **argv) {
 19     int k, ans = 0, i ;
 20     scanf("%d",&k);
 21     for ( i = 0; i < k ; i ++)
 22         scanf("%d",&group_distribution[i]);
 23     insertion_sort(group_distribution, k);
 24     for ( i = 0; i < (k+1)/2 ; i++ ) {
 25         ans += (group_distribution[0]+1)/2 ;
 26     }
 27     printf("%d\n",ans);
 28     return 0;
 29 }
```

So check below test:
100000 1

Answer is:
1 2 3 4 ... 99998 99999 100000

Hello All,
Can someone please help to understand the first test case or where I am going wrong in my code , I haven't used any algorithm, its just a brute force approach.

```
#include <stdio.h>
#include <stdlib.h>

char number[100];
char words[50001][101];

int main(int argc, char **argv) {
    int map_alphabet[26], i , j , c , n, master_begin_index, master_end_index ,output_buffer_index, pivot, number_len, is_candidate;
    char output_buffer[101];
    map_alphabet['i'-97] = 1;
    map_alphabet['j'-97] = 1;
    map_alphabet['a'-97] = 2;
    map_alphabet['b'-97] = 2;
    map_alphabet['c'-97] = 2;
    map_alphabet['d'-97] = 3;
    map_alphabet['e'-97] = 3;
    map_alphabet['f'-97] = 3;
    map_alphabet['g'-97] = 4;
    map_alphabet['h'-97] = 4;
    map_alphabet['k'-97] = 5;
    map_alphabet['l'-97] = 5;
    map_alphabet['m'-97] = 6;
    map_alphabet['n'-97] = 6;
    map_alphabet['p'-97] = 7;
    map_alphabet['r'-97] = 7;
    map_alphabet['s'-97] = 7;
    map_alphabet['t'-97] = 8;
    map_alphabet['u'-97] = 8;
    map_alphabet['v'-97] = 8;
    map_alphabet['w'-97] = 9;
    map_alphabet['x'-97] = 9;
    map_alphabet['y'-97] = 9;
    map_alphabet['o'-97] = 0;
    map_alphabet['q'-97] = 0;
    map_alphabet['z'-97] = 0;

    while( 1 ) {
        number_len = i = j = 0;
        while ( ( c = getchar() ) != '\n' && c != EOF)
            number[ i ++ ] = c;
        number[ i ] = '\0';
        number_len = i;
        if ( number[0] == '-' && number[1] == '1')
            exit(0);

        scanf("%d",&n);
        // this is to flush stdin extra /n
        c = getchar();


        i = 0;
        while ( n--) {
            j = 0;
            while ( ( c = getchar() ) != '\n') {
                words[i][j ++ ] = c;
            }
            words[i][j] = '\0';
            i ++;
        }

        master_begin_index = 0;
        master_end_index = number_len ;
        output_buffer_index = 0;

        for ( i = 0 ; words[i][0] != '\0' ; i ++)  {
            is_candidate = 1;
            pivot = master_begin_index;
            for ( j = 0 ; words[i][j] != '\0' ; j ++ ) {
                if ( map_alphabet[ words[i][j] - 97] !=  number[pivot] - 48 || pivot >= master_end_index) {
                    is_candidate = 0;
                    pivot = master_begin_index;
                    break;
                }
                else {
                    pivot ++;
                }
            }
            if (is_candidate) {
                master_begin_index = pivot;
                if ( output_buffer_index != 0)
                    output_buffer[output_buffer_index ++] = ' ';
                for ( j = 0; words[i][j] != '\0'; j ++ ) {
                    output_buffer[output_buffer_index ++] = words[i][j];
                }
            }


        }
        if ( pivot == master_end_index ) {
            for ( i = 0 ; i < output_buffer_index; i++ )
                putchar(output_buffer[i]);
            putchar('\n');
        }
        else
            printf("No solution.\n");
    }

    return 0;
}
```

L = []
string = input()

while string:
    [L.append(int(num)**0.5) for num in string.rstrip().split(' ') if num != '']
    string = input()

for i in L[::-1]:
    print('%.4f'%i)

Edited by author 06.05.2018 03:54

Edited by author 06.05.2018 03:54

Edited by author 06.05.2018 03:54

Edited by author 06.05.2018 03:54

I can't solve it, yet.
But i think that, it solviable as fermat point geometry construction (see wiki), and using angles, as Shen Yang suggested
<AOB = acos((c1*c1-c2*c2-c3*c3)/(2*c2*c3)),
<AOC = acos((c2*c2-c1*c1-c3*c3)/(2*c1*c3) and

<BOC = acos((c3*c3-c1*c1-c2*c2)/(2*c1*c2)) .
(c1,c2,c3 - are prices).
In wiki fermat point: constructed   triangles ABC'  , BCA'   and CAB'
where
<ABC' = 60, <BAC' = 60,
<CBA' = 60, <BCA' = 60,   and
<ACB' = 60, <CAB' = 60.

 Fermat point X - is intersection of AA'  and BB' and CC'  lines.

In there, we must construct triangles ABC' , BCA', and CAB' , with
<ABC' = <BAC' = <AOB / 2
<BCA' = <CBA' = <COB / 2
<ACB' = <CAB' = <AOC / 2

and intersection of AA'  , BB' and CC' - will be ans, iff it's in ABC triangle. otherwice A, B, or C will be ans.