i understood my mistake

Edited by author 06.04.2014 16:16

Edited by author 06.04.2014 16:16

Edited by author 06.04.2014 16:27

Hey guys, I ACed with a cellular automata (a grid of 1000x1000 and a set of rules to transform 0s -> 1s).
But is there any other(faster?) way to find a 45 convex hull given a set of points without a cellular automata?

Please give test number 9. And as much as possible tests.

:(

Please unblock this problem for Java.
Thanks.

Check this:
2
10
10
110

#include<iostream>
#include<vector>
using namespace std;
int main()
{
     int n,x,m=0,k=0,g;
     cin>>n>>x;
    vector<int> a(n);
    if(n==1)
    {
        cin>>g;
        if(g<0&&x>0)
        {
            cout<<x<<" "<<-2*g+x;
        }
        else if(g>0&&x<0)
        {
              cout<<2*g-x<<" "<<-x;
        }
        else
        cout<<"Impossible";
    }
    else
     {
        for(int i=0;i<n;i++)
          {
            cin>>a[i];
            if(a[i]<x&&m==0)
            m=a[i];
            else if(a[i]<x&&a[i]>m&&m!=0)
            m=a[i];
            else if(a[i]>x&&k==0)
            k=a[i];
            else if(a[i]>x&&k!=0&&a[i]<k)
            k=a[i];
        }
        if(m<0&&k>0)
         {
            if(x<0)
            cout<<2*k-x<<" "<<-x;
            else
            cout<<x<<" "<<-2*m+x;
        }
        else if(m<0&&k==0&&x>0)
        {
               cout<<x<<" "<<2*x-m;
        }
        else if(k>0&&m==0&&x<0)
        {
            cout<<2*k-x<<" "<<-x;
        }
        else
        cout<<"Impossible";
     }

    return 0;
}

Hi! Can i see the test, where my decision have "Wrong answer" result?

New tests were added. All solutions were rejuded. 260 authors have lost AC. The most common verdict was Runtime error (stack overflow).

Well, i spent a lot of time for optimizing memory stuff in Java, but it seems that even empty program takes 5 MB.

I'm kindly asking administration to increase memory limit to doable one (9-10 MB).

# include <cstdio>
# include <iostream>
# include <vector>
# include <cstring>
# include <algorithm>
# include <map>
# include <string>
# include <set>
# include <cmath>

using namespace std;

const int M = 1e9 + 7;
const int N = 1000001;

int a[N], n, f[N], prime[170], sz;
bool used[N];

void get_primes(){
    for (int i = 2; i < 1001; i ++){
        for (int j = i + i; j < 1001; j += i) used[j] = true;
    }
    for (int i = 2; i < 1001; i ++){
        if (!used[i]) prime[sz++] = i;
    }
}

int main(){

    scanf("%d", &n);
    get_primes();

    f[1] = f[2] = 1;
    for (int i = 3; i <= n; i ++){
        f[i] = f[i - 1] + f[i - 2];
        if (f[i] >= M) f[i] -= M;
    }
    for (int i = n; i > 1; i --){
        int p = i;
        for (int j = 0; j < sz && prime[j] * prime[j] <= p; j ++){
            while (p % prime[j] == 0){
                p /= prime[j];
                a[prime[j]] += f[n - i + 1];
                if (a[prime[j]] >= M) a[prime[j]] -= M;
            }
        }
        if (p > 1){
            a[p] += f[n - i + 1];
            if (a[p] >= M) a[p] -= M;
        }
    }
    long long ans = 1;
    for (int i = 1; i <= n; i ++){
        ans = (ans * long long((a[i] + 1) % M)) % M;
    }
    printf("%lld", ans);

    return 0;
}

it said that the powerful spell is depend on the times it had repeated so in "abababa" "a" is 4 times or "ba" is 3... or in "qqq" whats the answer ?? "q" 3 times or "qqq" 1 time???

Please test this case:

4 2
0 0
1 0
2 0
3 0
1 2
3 4

Answer: NO

what is the answer for these tests?
10 6 14
?

10 6 19
?

10 1 13
?

11 6 23
?

thanks beforehand.

Recursive algorithm seems to slow for n=8. Actually, it depends on the order of moves, but the order fast for n=8 was slow for 6 or 7, the fast one for 7 was slow for 8 and so on... Anyway, I used pregenerated output to solve this.
Is there a way to optimize the algorithm?

Sorry, i understand my mistake

Edited by author 01.04.2014 01:43

#include <cstdio>
#include <cmath>
int main()
{
    unsigned int n,a,m = 0,p = 0;
    double x;
    char r[65536];
    scanf("%d",&n);
    while(n--){
        scanf("%d",&a);
        x = (sqrt(double(8*a-7))+1)/2;
        if (x==int(x))
            r[m++] = '1';
        else
            r[m++] = '0';
    }
    n = 0;
    while(m--)
        printf("%c ",r[n++]);
    printf("\n");
    return 0;
}

I think 1s is resonable,but 64M is too tight(unsigned long long hash table is too hard to fit in 64M),1s in ural oj can run many operations

Edited by author 31.03.2014 14:08

"1. Any (but only one) symbol 0 is replaced by 1. "

It means
 When the length=n
 It needn't to consider 1 is replaced by 0.

read problem carefully.!I got wa 6 times because of it..TAT.

Hope to help you a little.

Try this test:

2
3 -1

Answer:

1
3 3