using System;

namespace Training
{
    class Program
    {
        static void Main(string[] args)
        {
            string[] n = Console.ReadLine().Split(' ');
            int N = Convert.ToInt32(n[0]);
            int M = Convert.ToInt32(n[1]);
            double cnt = 1;
            int arr = 0;

            int[] ans = new int[M];
            double[] vs = new double[N];

            for (int i = 0; i < M; i++)
                ans[i] = Convert.ToInt32(Console.ReadLine());

            Array.Sort(ans);
            Array.Resize(ref ans, ans.Length+1);

            Console.WriteLine();

            for (int j = 0; j < M; j++)
            {
                if (ans[j] == ans[j + 1])
                    cnt++;
                else
                {
                    double x = Math.Round(cnt / M * 100, 2);
                    if ((int)x == x)
                        Console.WriteLine(x + ".00%");
                    else
                        Console.WriteLine(x + "%");
                    arr++;
                    cnt = 1;
                }
            }
            if (arr < N)
                for (int j = 0; j < N - arr; j++)
                    Console.WriteLine("0.00%");
        }
    }
}

Python 3
when counting by force I met TLE on the 45th test.
I printed out all the values of the function and saw that it is mirrored after 40 values.
f (40) = f (41)
f (39) = f (42)
...
f (2) = f (79)
therefore, counting only to 40, I got Accepted

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

const int maxn = 12;
const int maxst = 50000 + 5;

const int orz = 19260817;

struct Hash
{
    int cnt[orz];
    ull val[orz];
    int head[orz], nxt[orz], sz;

    void inline insert(ull u, int c)
    {
        int v = u % orz, i, lst = 0;
        for(i = head[v]; i; lst = i, i = nxt[i]) if(val[i] == u) break;
        if(i) cnt[i] = c;
        else {
            if(lst) nxt[lst] = ++sz;
            else head[v] = ++sz;
            val[sz] = u, cnt[sz] = c;
        }
    }

    int inline find(ull u)
    {
        int v = u % orz, i;
        for(i = head[v]; i; i = nxt[i]) if(val[i] == u) return cnt[i];
        return 0;
    }
} vti;
ull itv[maxst]; int tot;

int n, m;
char board[maxn + 3][maxn + 3];
int ptn[maxst][maxn + 2];
int fi, fj;

void inline getptn(int id)
{
    ull st = itv[id];
    int stk[maxn], cnt = 0;
    for(int i = 1; st; st >>= 2, ++i) {
        int p = st & 3;
        if(p == 1) stk[++cnt] = i;
        else  if(p == 2) ptn[id][i] = stk[cnt], ptn[id][stk[cnt--]] = i;
    }
}

void dfs(ull st, int dep, int k)
{
    if(dep > n + 1) {
        if(k) return;
        itv[++tot] = st;
        vti.insert(st, tot);
        return;
    }
    if(k > n + 1 - dep + 1) return;
    dfs(st, dep + 1, k); // #
    dfs(st | (1 << (2 * (dep - 1))), dep + 1, k + 1); // (
    if(k) dfs(st | (2 << (2 * (dep - 1))), dep + 1, k - 1); // )
}

void inline Init()
{
    scanf("%d %d", &n, &m);
    for(int i = 1; i <= n; ++i) scanf("%s", board[i] + 1);
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= m; ++j)
            if(board[i][j] == '*') board[i][j] = 0;
            else board[i][j] = 1;
    dfs(0, 1, 0);
    for(int i = 1; i <= tot; ++i) getptn(i);
//    printf("tot = %d\n", tot);
    for(int i = n; i; --i) {
        for(int j = m; j; --j) {
            if(board[i][j]) {
                fi = i, fj = j;
//                printf("fi = %d, fj = %d\n", fi, fj);
                return;
            }
        }
    }
}

ll f[maxn + 2][maxn + 2][maxst];

ull inline fillas(ull S, int k, int c) {
    S &= ~(3 << (2 * (k - 1)));    // set zero
    S |= c << (2 * (k - 1));    // set c
    return S;
}

void inline Solve()
{
    f[0][m][vti.find(0)] = 1;
    for(int i = 0; i <= n; ++i) {
        for(int j = 1; j <= m; ++j) {
            for(int k = 1; k <= tot; ++k) {
                ull st = itv[k];
                if(!f[i][j][k]) continue;    // cut (=^o^=)
//                printf("f[%d][%d][%d] = %lld\n", i, j, k, f[i][j][k]);
                int tj = j + 1, ti = i; if(tj > m) tj = 1, ti = i + 1; // get target.

                int left = (st >> (2 * (tj - 1))) & 3;    // left plug
                int top = (st >> (2 * tj)) & 3;            // top plug
//                printf("[%d, %d] -> [%d, %d] with left = %d, top = %d.\n", i, j, ti, tj, left, top);

                if(!left && !top) {    // no plug
                    if(!board[ti][tj]) {    // if cannot
                        ull S = st;    // do nothing
                        if(tj == m) S = fillas(S, n + 1, 0), S <<= 2;
                        f[ti][tj][vti.find(S)] += f[i][j][k];
                    } else if(board[ti + 1][tj] && board[ti][tj + 1]) {    // can ?
                        ull S = fillas(fillas(st, tj, 1), tj + 1, 2); // fill it
                        if(tj == m) S = fillas(S, n + 1, 0), S <<= 2;
                        f[ti][tj][vti.find(S)] += f[i][j][k];
                    }
                }

                else if(left == 1 && top == 1) { // double left
                    int pp = ptn[k][tj + 1]; // get partner
                    ull S = fillas(fillas(fillas(st, tj, 0), tj + 1, 0), pp, 1);
                    if(tj == m) S = fillas(S, n + 1, 0), S <<= 2;
                    f[ti][tj][vti.find(S)] += f[i][j][k];
                }

                else if(left == 2 && top == 2) {    // double right
                    int pp = ptn[k][tj];    // get partner
                    ull S = fillas(fillas(fillas(st, tj, 0), tj + 1, 0), pp, 2);
                    if(tj == m) S = fillas(S, n + 1, 0), S <<= 2;
                    f[ti][tj][vti.find(S)] += f[i][j][k];
                }

                else if(left == 2 && top == 1) {    // right and left
                    ull S = fillas(fillas(st, tj, 0), tj + 1, 0);    // connect them directly
                    if(tj == m) S = fillas(S, n + 1, 0), S <<= 2;
                    f[ti][tj][vti.find(S)] += f[i][j][k];
                }

                else if(left == 1 && top == 2) {    // left and right
                    if(ti == fi && tj == fj) {    // end block only
                        ull S = fillas(fillas(st, tj, 0), tj + 1, 0);    // connect them directly
                        if(tj == m) S = fillas(S, n + 1, 0), S <<= 2;
                        f[ti][tj][vti.find(S)] += f[i][j][k];
                    }
                }

                else {    // one have plug but another no
//                    printf("ah?\n");
                    if(board[ti + 1][tj]) {    // if down can to
                        ull S = fillas(fillas(st, tj, left + top), tj + 1, 0);    // set
                        if(tj == m) S = fillas(S, n + 1, 0), S <<= 2;
//                        printf("%d %llu\n", vti.find(S), S);
                        f[ti][tj][vti.find(S)] += f[i][j][k];
                    }
                    if(board[ti][tj + 1]) {    // if right canto
                        ull S = fillas(fillas(st, tj, 0), tj + 1, left + top);    // set
                        if(tj == m) S = fillas(S, n + 1, 0), S <<= 2;
                        f[ti][tj][vti.find(S)] += f[i][j][k];
                    }
                }
            }
        }
    }
}

int main()
{
    Init();
/*    for(int i = 1; i <= tot; ++i) {
        printf("id: %d, st: %llu\n", i, itv[i]);
    }*/
    Solve();
    printf("%lld\n", f[n][m][1]);
    return 0;
}

Somebody had this test case?

Is there any algorithm to be applied except sorting?

#include <iostream>

using namespace std;

int main()
{
    int n,sum=0;
     cin>>n;
     if(n==0 || n==1)
    {
        cout<<1<<endl;
    }

   if(n>1)
   {
       for(int i=2;i<=n;i++)
   {

       sum=sum+i;
   }
       cout<<sum<<endl;
   }
   if(n<0)
   {
       n=n*-1;
       for(int i=2;i<=n;i++)
   {

       sum=sum+i;
   }
       cout<<"-"<<sum<<endl;
   }

    return 0;
}

try this test:
21 1
1 2
2 3
3 4
4 5
4 6
6 7
7 8
5 9
9 10
10 11
11 12
1 13
12 14
14 15
15 16
13 17
16 18
18 19
19 20
20 21
8 15

answer:
21

Try this tets:

1999992
2000002

1009002
1010101

Input:
2 3
RT,
RT,
,
B,
,
.

Output:
6
2 3
2 4
3 3
3 4
4 2
4 3

Считаем кол-во клеток ( квадрат + 2 треугольника сверху и снизу )

156 мс, как ускорить программу? сократить формулу? найти более легкую закономерность?

n = int(input())
def tr(size):
    ans = 0
    for i in range(1, size+1):
        ans += i
    return ans
for j in range(n):
    print()
    for i in range(n):
        if i >= j:
            print((n-i-1)*j + tr(j) + tr(n-i-2) + 1 + j + (n-i-1), end = ' ')
        else:
            print(n*n - (i+1)*(n-j) - tr(n-j-1) - tr(i-1) + 1, end = ' ')

k, n = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
if sum(a) - n * k <= 0:
    print(0)
else:
    print(sum(a) - n * k)

Can someone give idea or hint of dynamic prog solution?

Помогите ,пожалуйста , что не так?
#include <iostream>
#include <string>
using namespace std;
int main() {
    int n, s = 0;
    cin >> n;
    string a[1000];
    for (int i = 0; i < n; i++) {
        getline(cin, a[0]);
        for (int j = n + 1; j < n; j++) {
            if (a[i] == a[j]) {
                break;
                s++;
            }
        }
    }
    cout << s;
    return 0;
}


Edited by author 02.12.2019 20:46

I passed all test cases mentioned in the discussion.

There are 4 tests in my algorithm:
- is there a loop (from M and N) ?
- is the graph connected ?
- is there a cycle?
- for each component of the graph:
  find the longest path and compare the length with S

any hint?

Edited by author 06.09.2017 11:02

Edited by author 06.09.2017 11:02

10
RGRGRBGBGB

Possible answer:
7
4 6
3 6
2 6
1 6
1 7
1 8
1 9

will somebody helps me?

I just rewritten my AC solution in python (it was originally written in Java) and I got Runtime Error on test #7. Any hint on why this happen ? Any test ? It gives me the same results as my Java solution ..

solution found
1
1

Edited by author 16.12.2019 16:48

Edited by author 16.12.2019 16:51

#include <iostream>
#include <iomanip>
#include <cmath>
#include <vector>

using namespace std;

int main() {
    cout << setprecision(4);
    vector<double> v;
    double n;
    while (cin >> n)
        v.push_back(n);
    for (int i = v.size() - 1; i >= 0; i--)
        cout << sqrt(v[i]) << endl;
}