HHHHHH.KJDFDKJ(newline)
ADFFG

right answer

Hhhhhh.Kjdfdkj
adffg

I WA here for five times

Edited by author 25.07.2008 08:43

Edited by author 25.07.2008 08:54

subj

if you use dp, l, r can be (>30000).

Edited by author 26.10.2018 11:42

Edited by author 26.10.2018 11:42

You may just want to continue the sequence from sample, for me it was enough to get it for n = 5
{ 1, 3, 2, 6, 8, 4, 11, 5 } to start noticing the pattern.

Alternatively, just plug it into OEIS and come across A019444 with an explanation how to compute the answer :D

suppose the slope of line on the x>0 is k ,and slope of (0,0) to n
points is k1,k2,...kn then intersection point of x1==1/(k1-k),x2=1/(k2-k)...xn=1/(kn-k)
then we choose (x4-x1)/(x2-x1)==(x4'-x1')/(x2'-x1') and (x3-x2)/(x3-x4)==（x3'-x2'）/(x3'-x4')
we multiply these two equations guess what happens, yes: k is offset
then we can get (k4-k1)*(k3-k2)/((k2-k1)*(k3-k4))==(k4'-k1')*(k3'-k2')/((k2'-k1')*(k3'-k4'))
en.. this convert to string matching prolems,so suffix array can solve it

#include <iostream>
#include <cmath>

void rSqrt(void)
{
    unsigned long int n = 0;
    if (scanf("%lu", &n) != -1)
    ¦  rSqrt();
    else
    ¦   return;
    printf("%.4f\n", sqrt(n));
    return;
}

int main()
{
    rSqrt();
    return 0;
}

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)