My solution in Python 3 took 0.078 seconds and 516 KB with recursion. Can you do it faster?

Can anybody that had WA7 give me some hints?
Thanks

what is case 8 like,i just can't solve it with divede and conquer...

I have solved 1009&1012 using dp. My algorithm is O(n). Obviously it can't pass this problem's test. I think maybe there are some ways to make it quicker but I can't figure out. When I was searching in internet for solutions, I found that they are all for 1012. I'm a Junior high school students and my math is poor (for this question) TAT. Can anybody help me?? THx in advance.

My program passed sample But I HAVE WA#1!
My output:
8.6000
4
EDWS

Please give me some hint!

Edited by author 17.05.2007 19:32

rt

Many thank to Oracle[Lviv NU]. His test data helped me a lot. But now my program solves all that tests as well as any test that I can imagine.
Can anyone give test cases that he consider to be hard.

Thanks!

Recursion solution - tl5, recursion with non-asymptotic optimization - ac 0.046

I precalculated this numbers by algo like bfs, the last most complex numbers have 92160, 96768, 98304, 103680 divisors. Wa17 - max test.
I have wa17 because of wrong right border in binary search. Check your program, may be it hepls you.

Also you can visit https://oeis.org/A002182

#include <bits/stdc++.h>

using namespace std;

int main()
{
    string s;
    int pe = 0;
    while(getline(cin, s)) {
        for (int i = 0; i < s.length(); i++) {
            if (s[i] == '.' || s[i] == '!' || s[i] == '?' || (s[i] == '-' && i )) {
                pe = 0;
            }
            if ((s[i] - '0' + '0' >= 65 && s[i] - '0' + '0' <= 90) && pe != 0) {
                s[i] = s[i] - '0' + 32 + '0';
            }
            if (pe == 0 && s[i] != ' ' && s[i] != '.' && s[i] != '!' && s[i] != '?' && s[i] != '-') {
                if (s[i] - '0' + '0' > 90) {
                    s[i] = s[i] - '0' - 32 + '0';
                }
                pe = 1;
            }
        }
        cout << s << '\n';
    }
}

Edited by author 16.08.2018 18:05

Edited by author 16.08.2018 18:05

Try this abacabadabacab.
The problem is in hash.
Answer is : a bacabadabacab

Edited by author 15.08.2018 21:18

I use suffix array but WA3.
Give me some tests.

#include <string>
#include <iostream>
using namespace std;

int min(int x, int y) { return x < y ? x : y; }
int max(int x, int y) { return x > y ? x : y; }
int Min(int l, int r);

const int nmax = 1005;
const int maxlen = 1000 * 105;
const int alphabet = 256;

int n, m, sum;
int p[maxlen], cnt[maxlen], c[maxlen];
int pn[maxlen], cn[maxlen], lcp[maxlen];
int who[maxlen], up[maxlen], down[maxlen], a[nmax], b[nmax];
int ans_len[nmax], ans_ind[nmax];
string s, str[nmax];

int main()
{
    cin>>m;
     for(int i=0;i<m;i++) cin>>str[i], s+=str[i];
     m++;
     str[m-1]="#";
     s+=str[m-1];

    n = s.length();

    memset(cnt, 0, alphabet * sizeof(int));
    for (int i = 0; i<n; ++i) ++cnt[s[i]];
    for (int i = 1; i<alphabet; ++i) cnt[i] += cnt[i - 1];
    for (int i = 0; i<n; ++i) p[--cnt[s[i]]] = i;
    c[p[0]] = 0;
    int classes = 1;
    for (int i = 1; i<n; ++i)
    {
        if (s[p[i]] != s[p[i - 1]])  ++classes;
        c[p[i]] = classes - 1;
    }

    for (int h = 0; (1 << h)<n; ++h)
    {
        for (int i = 0; i<n; ++i)
        {
            pn[i] = p[i] - (1 << h);
            if (pn[i] < 0)  pn[i] += n;
        }
        memset(cnt, 0, classes * sizeof(int));
        for (int i = 0; i<n; ++i) ++cnt[c[pn[i]]];
        for (int i = 1; i<classes; ++i) cnt[i] += cnt[i - 1];
        for (int i = n - 1; i >= 0; --i) p[--cnt[c[pn[i]]]] = pn[i];
        cn[p[0]] = 0;
        classes = 1;
        for (int i = 1; i<n; ++i)
        {
            int mid1 = (p[i] + (1 << h)) % n, mid2 = (p[i - 1] + (1 << h)) % n;
            if (c[p[i]] != c[p[i - 1]] || c[mid1] != c[mid2]) ++classes;
            cn[p[i]] = classes - 1;
        }
        memcpy(c, cn, n * sizeof(int));
    }

    n--, m--, s.erase(n, 1);
    for (int i = 0; i < n; i++) p[i] = p[i + 1];

    sum = 0;
    for (int i = 0; i < m; i++) a[i]=sum, b[i]=sum+str[i].length()-1, sum += str[i].length();

    for (int i = 0; i < n; i++)
    {
        int j = 0;
        while (!(a[j] <= p[i] && p[i] <= b[j])) j++;
        who[i] = j;
    }

    for (int i = 0; i <= n - 2; i++)
    {
        lcp[i] = 0;
        int hr = max(p[i], p[i+1]);
        int gr = min(b[who[i]]-p[i]+1, b[who[i+1]]-p[i+1]+1);
        while (hr+lcp[i]<n && lcp[i]<gr && s[p[i] + lcp[i]] == s[p[i + 1] + lcp[i]]) lcp[i]++;
    }

    down[0] = -1;
    for (int i = 1; i < n; i++) down[i] = who[i - 1] == who[i]? down[i - 1] : i - 1;

    up[n - 1] = -1;
    for (int i = n - 2; i >= 0; i--) up[i] = who[i + 1] == who[i] ? up[i + 1] : i + 1;

    for (int i = 0; i < m; i++) ans_len[i] = str[i].length(), ans_ind[i]=a[i];

    for (int i = 0; i < n; i++)
    {
        int val1 = down[i] == -1 ? 0 : Min(down[i], i - 1);
        int val2 = up[i] == -1 ? 0 : Min(i, up[i]-1);
        int now_len = max(val1, val2) + 1;
        if (now_len<=b[who[i]]-p[i]+1 && ans_len[who[i]] > now_len) ans_len[who[i]] = now_len, ans_ind[who[i]] = p[i];
    }

    for (int i = 0; i < m; i++)
    {
        for (int j = 0; j < ans_len[i]; j++) cout << s[ans_ind[i] + j];
        if(i+1<m) cout << endl;
    }

    return 0;
}


int Min(int l, int r)
{
     int res=maxlen+5;
     for(int i=l;i<=r;i++) res=min(res, lcp[i]);
     return res;
}

Edited by author 16.08.2018 00:42

This tests helped me to find bugs with wa5 and wa84

5 8
answer:
1
3
5 4 8
-----
5 18
answer:
1
3
5 6 18
-----
7 25
answer:
2
3
7 5 25

this is my code G++
#include<bits/stdc++.h>
using namespace std;

int n,k;


void pl(int a[],int b[],int c[])
{
  for(int i=1;i<=210;i++)
    {
    c[i]+=a[i]+b[i];
    c[i+1]+=c[i]/10;
    c[i]%=10;
  }
}

void cheng(int a[],int x)
{
  for(int i=1;i<=210;i++)
    {
    a[i]*=x;
    a[i]+=(a[i-1]/10);
    a[i-1]%=10;
  }
}

int f[2000][222];

int main()
{
    scanf("%d%d",&n,&k);
    f[0][0]=0;
    f[1][0]=1;
    f[1][1]=k-1;
    for(int i=2;i<=n;i++)
    {
        pl(f[i-2],f[i-1],f[i]);
         cheng(f[i],k-1);
    }
    for(int i=1;i<=210;i++)
    {
    f[n][i]+=f[n-1][i];
    f[n][i+1]+=f[n][i]/10;
    f[n][i]%=10;
  }
    int h=221;
    while(!f[n][h])    h--;
    for(int i=h;i>=1;i--)
        printf("%d",f[n][i]);
 return 0;
 }

I use "string ch" AC,but " char ch[maxn]" WA4,I don't know why .....

Test: ((**)*)
My answer is YES, but if we delete comment (**) it will remain only (*) and it must be arithmetic expr, but it's not cuz arithmetic expressions can't start with (*, so the right answer is NO, am I wrong?

Could you specify in the problem statement that the coordinates of the point in the last line are integer?

Also, could you specify the kind of precision near 10^{-14}? Is it absolute or relative?

New tests have been added to the problem which exploit a common mistake when using acos function. Hint: try to calculate acos(sqrt(3.0) * sqrt(3.0) - 4.0) in your programming language. 649 authors (60%) with accepted solutions have been challenged.

in this test Petr should go to 1 floor