WHO CAN GIVE ME A TEST....
THANK YOU VERY MUCH

//#pragma GCC optimize("Ofast,no-stack-protector")
//#pragma GCC target("avx")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;

#define re return
#define pb push_back
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define sqrt(x) sqrt(abs(x))
#define mp make_pair
#define pi (3.14159265358979323846264338327950288419716939937510)
#define fo(i, n) for(int i = 0; i < n; ++i)
#define ro(i, n) for(int i = n - 1; i >= 0; --i)
#define unique(v) v.resize(unique(all(v)) - v.begin())

template <class T> T abs (T x) { re x > 0 ? x : -x; }
template <class T> T sqr (T x) { re x * x; }
template <class T> T gcd (T a, T b) { re a ? gcd (b % a, a) : b; }
template <class T> int sgn (T x) { re x > 0 ? 1 : (x < 0 ? -1 : 0); }


typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<string> vs;
typedef double D;
typedef long double ld;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;
typedef unsigned long long ull;
typedef tree <int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> _tree;

const int maxn = (int) 5e4 + 10;
const int mod = (int) 1e9 + 7;
int dp[maxn][2];

inline int sum (int a, int b) {
    re (a + b) % mod;
}

int main() {
    int n, a, b;
    cin >> n >> a >> b;
    dp[0][0] = dp[0][1] = 1;
    fo(i, n) {
        for (int j = 1; j <= a && i + j <= n; ++j) dp[i + j][0] = sum (dp[i + j][0], dp[i][1]);
        for (int j = 1; j <= b && i + j <= n; ++j) dp[i + j][1] = sum (dp[i + j][1], dp[i][0]);
    }
    cout << sum (dp[n][0], dp[n][1]) << endl;
    re 0;
}

Its about precision

my solution is very fast using trie,but unfortuntly it use 1e6*27 memory ,and it is hard to optimize

What's wrong in this code?
#include <bits/stdc++.h>
using namespace std;
int main () {
    setlocale(LC_ALL, "Russian");
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    string k;
    map <int,int> mp;
    int i,j,m,n,s=0;
    cin>>n;
    for (i=0;i<n;i++){
        cin>>j;
        mp[j]=1;
    }
    cin>>m;
    for (i=0;i<m;i++){
        cin>>s;
        if (mp[s]>=1)
            mp[s]++;

    }
    int d=0;
    for (auto q:mp){
        if (q.second>1)
            cout<<q.second-1<<endl;
        else
            d++;
    }
    if (d==mp.size()) cout<<0<<endl;
}

I doubt test cases is weak...
I think  O(n^3/10) is reasonable complexity (this one 62ms)

Edited by author 04.05.2018 12:02

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. 269 authors (58%) with accepted solutions have been challenged.

Well, this is for those who didnt get the method.
Consider N: no of rows of blocks M: no of columns of the blocks (N+1 and M+1 are the input).
Crosspoint here refers to a point where a horizontal and a vertical line meet.

For each line that the plane intersects, a new block is introduced. Consider the south western most point also as one such point. No of horizontal lines intersected=N. No of vertical lines intersected=M. But the southwestern most point has been counted twice and it introduces the same first block.
If gcd(M,N)==1, there is no intermediate point where the line passes over a crosspoint. Hence no. of blocks = M+N-1.
If gcd(M,N)!=1, the whole grid can be split horizontally at
the points where the line passes over a crosspoint and each of them can be considered separately with that cross point as the south westernmost point of the subproblem. There are gcd(M,N) such points. Say a=gcd(M,N). Then in each subproblem  the line flies over M/a+N/a-1 blocks. Totally the line flies over a*(M/a+N/a-1) blocks. ie. M+N-a blocks.

Edited by author 29.11.2007 02:42

What's answers for this tests?
1)
3
0 1 0
2)
4
0 1 2 0
3)
4
2 0 0 0

Here is my code:
int main()
{
    int N, K;
    cin >> N >> K;
    int connect = 1;
    int temp = N;
    int largepow = 0;
// calculate the largest power of 2 less than K
    while(temp > 0)
    {
        if(pow(2, largepow) < K && pow(2, largepow + 1) < K)
            largepow++;
        temp /= 2;
    }
    N--;
    int count = 0;
// count the hours
    while(N > 0)
    {
        N -= connect;
        count++;
        if(connect < pow(2, largepow))
            connect *= 2;
        else if(connect >= pow(2, largepow) && connect < K)
            connect++;
    }
    cout << count;
    return 0;
}

Got WA4, then I tried something else:

int main ()
{
    long long n, k, exp;
    cin >> n >> k;
    for (exp = 0; (1 << exp) < n && (1 << exp) < k; exp++)
        if ((1 << exp) < n)
            exp += ((n - (1 << exp) - 1) / k) + 1;
    cout << exp;
    return 0;
}
Test case 4 again. What is wrong?

{bu-ga-ga};

Edited by author 29.01.2011 00:33

The property holds for all (i,j) if and only if it holds for all prefixes and all suffixes. You can prove this easily with pen and paper.
Prefix and suffix sums can be checked in linear time.

wordd
wo dd
ans??

1)What meaning of "equiprobable initial state"? P{state is GreenRed}=t1/(t1+t2+t3+t4), P{state is YellowRed}=t2/(t1+t2+t3+t4) ?

2)Can Sergey cross the street of Marks and then Engels, or first cross Engels and then Marks?

use StringComparison.Ordinal to sort cityes

Submission ID 7846927 (not my source, found online) gets Accepted but on this test it prints nan:

2 4 0
3 6 0
0 0 0
3

I'm pretty sure the test is correct (I plotted it). It's a sphere with center in origin and two points co-linear with the center which lie outside the sphere.

Submission ID 7846930 (also found online) also gets Accepted despite printing nan on the test above.

Edited by author 12.04.2018 03:03

Edited by author 12.04.2018 03:08

You do some matrix maltiplication and get an answer in the form (a%10^9)/(b%10^9), but it is not guaranteed that gcd (a, b) == 1. How to get irreducible fraction now???

in fact,we must regard plane is exactly on the surface of the earth so that we can get ac...

Same code gets AC in c++ but gets TLE in test 14 in Java.
Turns out, even if you dont use the condition of "powers of primes should be in non increasing order" , your c++ code gets AC, while for Java you have to use that condition.

Edited by author 25.04.2018 06:42

Edited by author 25.04.2018 06:42