You have to divide the participants into equal teams (rounded)
For example, for "15 10" test - (1, 1, 1, 1, 1, 2, 2, 2, 2, 2)
Good luck :)

На каких значениях становить ввод?

I got TLE for both, straightforward sort-solution (n*logn) and Moore's algorithm (n).
You can avoid it using this line in your code:
- ios_base::sync_with_stdio(false);

Commands "cout" and "cin" are immensely slow and for large inputs, your code can get TLE.
Surprisingly, both approaches differ from each other only by 0.02 sec (with the aforementioned line included).

Here's my code-

#include <bits/stdc++.h>
using namespace std;

bool upp,downn,leftt,rightt,avleftt,avrightt,avupp,avdownn;


bool vis[105][105],vis2[105][105];
int dist[105][105];
int dist2[105][105];
int xmov[4]={0,-1,0,1};
int ymov[4]={-1,0,1,0};
int main()
{
    // cout << "Hello World!" << endl;
    ios::sync_with_stdio(false);
    for(int i=1;i<105;i++)for(int j=1;j<105;j++)dist[i][j]=INT_MAX;
    int n,m,l,x1,y1,x2,y2;
    cin>>n>>m>>l;
    cin>>x1>>y1;
    cin>>x2>>y2;

    queue <pair <int,int> > q;
    queue <int> distt;
    int ans=0;
    if(abs(x1-x2)+abs(y1-y2)==1){
        ans=1;
    }
    vis[x1][y1]=true;
    dist[x1][y1]=0;
    vis[x2][y2]=true;
    q.push(make_pair(x1,y1));
    distt.push(0);


    while(q.empty()==0){
        pair <int,int> topp=q.front();
        int curdist=distt.front();
        q.pop();
        distt.pop();
        int curx,cury,nextx,nexty;
        curx=topp.first;
        cury=topp.second;
        for(int i=0;i<4;i++){
            nextx=curx+xmov[i];
            nexty=cury+ymov[i];
            if(nextx>=1&&nextx<=n&&nexty>=1&&nexty<=m){

                if(vis[nextx][nexty]==false){
                    vis[nextx][nexty]=true;
                    q.push(make_pair(nextx,nexty));
                    distt.push(curdist+1);
                    dist[nextx][nexty]=curdist+1;
                }
            }
        }
    }


    q.push(make_pair(x2,y2));
    distt.push(-1);
    vis2[x2][y2]=true;
    dist2[x2][y1]=-1;
     while(q.empty()==0){
        pair <int,int> topp=q.front();
        int curdist=distt.front();
        q.pop();
        distt.pop();
        int curx,cury,nextx,nexty;
        curx=topp.first;
        cury=topp.second;
        for(int i=0;i<4;i++){
            nextx=curx+xmov[i];
            nexty=cury+ymov[i];
            if(nextx>=1&&nextx<=n&&nexty>=1&&nexty<=m){

                if(vis2[nextx][nexty]==false){
                    vis2[nextx][nexty]=true;
                    q.push(make_pair(nextx,nexty));
                    distt.push(curdist+1);
                    dist2[nextx][nexty]=curdist+1;
                }
            }
        }
    }

    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(i==x2&&j==y2){
                continue;
            }

            if(dist[i][j]!=INT_MAX){
                cout<<i<<" ::::: "<<j<<"\n";
                int totaldist=dist[i][j]+dist2[i][j];
                if(totaldist<=l){
                    ans=max(ans,max(abs(y2-j),abs(x2-i))+1);
                }
            }

        }
    }

    cout<<ans;
    return 0;
}

тест в примере верный? если нет можно правильный?

This problem can be solved using brute force. The asymptotics is O(n*2^n) but still the time limit is not hit, provided you use bit operations instead of generating arrays. For you beginners, I post my code here, but I strongly recommend to write this on your own first. The language I use is Java; nextInt() function returns the next integer from the input.

[code deleted]

Worst time is 0.187 sec, as reported by Timus.

Edited by moderator 21.10.2019 22:59

Please give me test 8!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

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