445219- No
4+4+5 = 13
2+1+9 = 12
13 and 12 = 1
Yes?
Why not?

If someone is interested Test# 4 is the following

Q=0;
Output = 10;

Can anybody give me the test case 1?

I am sure my solution is right. But I even can not pass the example.
Hope you can help me.
dp[i][0..1] means the expected time for the last i digits while the i th digit carried or not carried.
f[i] means the possibility for the i th digit to carried.
p[0..1][x][y] means the possibility for x, y have appeared in the last i digits while the i th digit carried or not carried.

I know my code is boring and long.
my code is here.
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <deque>
#include <vector>
#include <queue>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <ctime>
#include <iomanip>
using namespace std;
typedef long long LL;
typedef double DB;
#define MIT (2147483647)
#define INF (1000000001)
#define MLL (1000000000000000001LL)
#define sz(x) ((int) (x).size())
#define clr(x, y) memset(x, y, sizeof(x))
#define puf push_front
#define pub push_back
#define pof pop_front
#define pob pop_back
#define mk make_pair

const int N = 5010, M = 10;
int n;
DB cost[M][M], p[2][M][M], tmp[2][M][M], dp[N][2], f[N];

inline void input()
{
    scanf("%d", &n);
}

inline DB Cost(int x, int y, int t)
{
    DB ptxy = p[t][x][y] + p[t][y][x];
    return 1.0 * ptxy + cost[x][y] * (1 - ptxy);
}

inline void solve()
{
    for(int i = 0; i < 10; i++)
        for(int j = 0; j < 10; j++)
            if(i < 2 || j < 2) cost[i][j] = 1;
            else cost[i][j] = 2;
    int cnt = 0, cnt9 = 0;
    for(int x = 0; x < 10; x++)
        for(int y = 0; y < 10; y++)
        {
            if(x + y >= 10) cnt++;
            if(x + y == 9) cnt9++;
        }
    DB pJin = cnt / 100.0, p9 = cnt9 / 100.0;
    for(int i = 1; i < n; i++)
        f[i] = f[i - 1] * p9 + pJin;
    f[n] = f[n - 1] * (8 / 81.0) + (45.0 / 81.0);

    int cnt00, cnt01, cnt10, cnt11;
    DB tmp00, tmp01, tmp10, tmp11;
    for(int i = 1; i < n; i++)
    {
        cnt00 = cnt01 = cnt10 = cnt11 = 0, tmp00 = tmp01 = tmp10 = tmp11 = 0;
        for(int x = 0; x < 10; x++)
            for(int y = 0; y < 10; y++)
            {
                if(x + y <= 8)
                {
                    cnt00++, cnt10++;
                    tmp00 += Cost(x, y, 0), tmp10 += Cost(x, y, 1);
                }
                else if(x + y == 9)
                {
                    cnt00++, cnt11++;
                    tmp00 += Cost(x, y, 0), tmp11 += Cost(x, y, 1);
                }
                else if(x + y >= 10)
                {
                    cnt01++, cnt11++;
                    tmp01 += Cost(x, y, 0), tmp11 += Cost(x, y, 1);
                }
            }
        dp[i][0] += f[i - 1] * (dp[i - 1][1] + tmp10 / cnt10 + 1) +
                (1 - f[i - 1]) * (dp[i - 1][0] + tmp00 / cnt00);
        dp[i][1] += f[i - 1] * (dp[i - 1][1] + tmp11 / cnt11 + 1) +
                    (1 - f[i - 1]) * (dp[i - 1][0] + tmp01 / cnt01);
        dp[i][1] += 1; // write & mark

        for(int x = 0; x < 10; x++)
            for(int y = 0; y < 10; y++)
            {
                if(x + y <= 8)
                {
                    tmp[0][x][y] = (1 - f[i - 1]) * (p[0][x][y] + (1 - p[0][x][y]) / cnt00) +
                                   f[i - 1] * (p[1][x][y] + (1 - p[1][x][y]) / cnt10);
                    tmp[1][x][y] = (1 - f[i - 1]) * p[0][x][y] +
                                   f[i - 1] * p[1][x][y];
                }
                else if(x + y == 9)
                {
                    tmp[0][x][y] = (1 - f[i - 1]) * (p[0][x][y] + (1 - p[0][x][y]) / cnt00) +
                                   f[i - 1] * p[1][x][y];
                    tmp[1][x][y] = (1 - f[i - 1]) * p[0][x][y] +
                                   f[i - 1] * (p[1][x][y] + (1 - p[1][x][y]) / cnt11);
                }
                else if(x + y >= 10)
                {
                    tmp[0][x][y] = (1 - f[i - 1]) * p[0][x][y] +
                                   f[i - 1] * p[1][x][y];
                    tmp[1][x][y] = (1 - f[i - 1]) * (p[0][x][y] + (1 - p[0][x][y]) / cnt01) +
                                   f[i - 1] * (p[1][x][y] + (1 - p[1][x][y]) / cnt11);
                }
            }
        for(int t = 0; t < 2; t++)
            for(int x = 0; x < 10; x++)
                for(int y = 0; y < 10; y++)
                    p[t][x][y] = tmp[t][x][y];
    }

    for(int i = 1; i < n; i++)
        printf("%.12lf\n", dp[i][1] * f[i] + dp[i][0] * (1 - f[i]));

    cnt00 = cnt01 = cnt10 = cnt11 = 0, tmp00 = tmp01 = tmp10 = tmp11 = 0;
    for(int x = 1; x < 10; x++)
        for(int y = 1; y < 10; y++)
            if(x + y <= 8)
            {
                cnt00++, cnt10++;
                tmp00 += Cost(x, y, 0), tmp10 += Cost(x, y, 1);
            }
            else if(x + y == 9)
            {
                cnt00++, cnt11++;;
                tmp00 += Cost(x, y, 0), tmp11 += Cost(x, y, 1);;
            }
            else if(x + y >= 10)
            {
                cnt01++, cnt11++;
                tmp01 += Cost(x, y, 0), tmp11 += Cost(x, y, 1);
            }
    dp[n][0] += f[n - 1] * (dp[n - 1][1] + tmp10 / cnt10 + 1) +
                (1 - f[n - 1]) * (dp[n - 1][0] + tmp00 / cnt00);
    dp[n][1] += f[n - 1] * (dp[n - 1][1] + tmp11 / cnt11 + 1) +
                (1 - f[n - 1]) * (dp[n - 1][0] + tmp01 / cnt01);
    dp[n][1] += 1; // // write & mark & write next column

    DB ans = n + f[n] * (dp[n][1] + 1) + (1 - f[n]) * dp[n][0];
    printf("%.12lf\n", ans);
}

int main()
{
    ios::sync_with_stdio(0);
    input();
    solve();
    return 0;
}

Edited by author 01.03.2016 18:27

There is task fragment:
"However, you must round the result in such a way, that it is accurate to 8 inches (1 foot is equal to 12 inches)"

I thought it means that result should be int and (result*12) should be divided by 8 without reminder. I received WA3.

When I ignored requirement and used simple rounding like int(result+0.5) I got ac.

So, does requirement mean anything? Maybe it should be removed from task?

I have WA 2. I don't understand why? Give me some tests please, which will help me understand my mistake.
Thank you.

#include <iostream>
#include <string>
#include <vector>

using namespace std;

int test_horse(int, int);
int test(string);

int test(string run) {
    return test_horse(run[0] - 'a', run[1] - '1');
}

int test_horse(int x, int y) {
    int count = 0;
    if(x + 1 < 8 && y + 2 < 8) {count++;}
    if(x + 1 < 8 && y - 2 >= 0) {count++;}
    if(x - 1 >= 0 && y + 2 < 8) {count++;}
    if(x - 1 >= 0 && y - 2 >= 0) {count++;}

    if(x + 2 < 8 && y + 1 < 8) {count++;}
    if(x + 2 < 8 && y - 1 >= 0) {count++;}
    if(x - 2 >= 0 && y + 1 < 8) {count++;}
    if(x - 2 >= 0 && y - 1 >= 0) {count++;}

    return count;
}

int main() {
    vector<string>vec;

    int N;
    cin >> N;

    for(int i = 0; i < N; ++i) {
        string str;
        cin >> str;
        vec.push_back(str);
    }

    for(int i = 0; i < vec.size(); ++i) {
        cout << test(vec[i]) << endl;
    }


}

bool checkstrtod(char s[])
{
    char *end;
    strtod(s,&end);
    return int(end-s)==strlen(s);
}

http://www.cplusplus.com/reference/cstdlib/strtod/

Editorial 1222. Chernobyl’ Eagles

We need to find set of numbers k > 0 and a[i] > 0:
a1 + a2 + ... + ak = n
a1 * a1 * ... * ak -> inf

0. If n = 1 answer = 1, later let's suppose n > 1

1. First of all let's see that in optimal solution a[i] > 1:
Assume a[j] == 1 for some j, also it means that k > 1 (i.e. there is another a[f] in our solution, f != j):
a1 * a2 * ... * a[j-1] * 1 * a[j+1] * ... * ak =
a1 * a2 * ... * a[j-1] * a[j+1] * ... * ak  <
a1 * a2 * ... * a[j-1] * a[j+1] * ... * (ak + 1) =
a1 * a2 * ... * a[j-1] * a[j+1]) * ... * ak + a1 * a2 * ... a[j-1] * a[j+1]) * ... * a[k-1]

It means that such set of number (a1, a2, ..., a[j-1], 1, a[j+1], ..., ak) is not optimal solution

2. Now let's see that in optimal solution a[i] < 4:
Assume a[j] >= 4 for some j, now we can split a[j] to (a[j] - 2) and 2, and find which a[j] will give us better results:

a1 * a2 * ... * a[j] * ... * ak >= a1 * a2 * ... * (a[j] - 2) * 2 * ... * ak
(a[j] - 2) * 2    >= a[j]
2 * a[j] - 4    >= a[j]
a[j] - 4        >= 0
a[j]            >= 4 (as we assumed)

It means that optimal solution will be consist 2's and 3's:
2 * a + 3 * b = n
2 ^ a + 3 ^ b -> max

3. Consider all leftover form of solution which was not proved to be not optimal:

1) 3 * 3 * 3 * 3 * ... (a = 0)
2) 2 * 3 * 3 * 3 * ... (a = 1)
3) 2 * 2 * 3 * 3 * ... (a = 2)
4) 2 * 2 * 2 * 3 * ... (a = 3)
5...) .... a > 3

Solution's 4), 5), 6), ... - is not optimal because we can take any 3 of 2's and replace it with 2 of 3', because
2 * 2 * 2 = 8 < 9 = 3 * 3

It means that 1), 2), 3) potential form of optimal solution

4. Now show that none of the solutions 1), 2), 3) can be compared to each other and it will be mean that 1), 2) and 3) can not be improved, i.e. it is optimal solution.
For this let's look at constraint:
2 * a + 3 * b = n

1) 3 * b1 = n => n % 3 = 0
2) 3 * b2 + 2 = n => n % 3 = 2
3) 3 * b3 + 2 * 2 = 3 * b3 + 4 = 3 * (b3 + 1) + 1 = n => n % 3 = 1

Now we can see that form of optimal solution (1), 2) or 3)) depend on n % 3,
e.g. if n % 3 == 2, then form 2) is optimal solution and nor 1) nor 3) can be formed.

Memory limit test 1. C++.
using:
vector<string> str
str[i].erase()
str[i].insert()

using erace and insert it creats another string object. I know, so how can i insert '' or `` instead of " ?

How can I recognize mistake in my programm?

А что такое модуль?

What is expected answer for test like "10 0 1 3 1"?
Should answer be some number or "ambiguous"?

Thanks

If you use fenwick tree and got WA #7, don't write Get(r) - Get(l - 1). Write (Get(r) - Get(l - 1) + mod) % mod.

Stars are listed in ascending order of Y coordinate. Stars with equal Y coordinates are listed in ascending order of X coordinate.

Не могу понять что не так.

Used built-in Stack class, memory and time constraints seem to be OK. What could be the source of the problem?

pls help

Edited by author 24.02.2016 16:20