Help pls with test 10

Guys, I have no idea why it doesn't pass this test. Any suggestions?


public static int getMinutes(int n, int k) {
        if (k == 1){
            return n * 2;
        } else if ( k >= n)  {
            return 2;
        } else if (n > k) {
            return n - k + 2;
        }
        return 0;
    }

BFS (Поиск в ширину).
[code deleted]

Edited by moderator 19.11.2019 23:14

If you decide to use SQRT-decomposition in C++ using std::set you can get TLE on test 13. All you need is to replace set -> unordered_set in your code :) (dont forget about C++11)

ez

ez

What is Test #3?

1 second is just enough.

what is test 10?

try this test:
1 0 0

answer:
0

var a,b:real;
begin
readln(a,b);
a:=a+b;
write (a);
end.

5 3 - 29.
100 0 - 1.
10000 10000 - http://pastebin.com/CMNizjgM .
100 100 - 1267650600228229401496703205376

Edited by author 02.03.2016 13:43

Edited by author 02.03.2016 13:44

Edited by author 23.12.2006 13:14

Edited by author 03.03.2016 03:38

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?