def SUM(n):
    ans=0
    while n:
        ans+=n%10
        n/=10
    return ans



def main():
    n=int(raw_input())
    n/=2

    m={}

    for i in range(0,10**n):
        try:
            m[SUM(i)]+=1
        except:
            m[SUM(i)]=1
    ans=0

    for i in m:
        ans+=m[i]*(m[i])
        #print i, m[i]
    print ans
main()

I used dictionary ( in c/c++ it's map)

Edited by author 25.07.2014 18:56

Edited by author 25.07.2014 18:57

Please, give me test if anybody have it

Both my AC submissions answer wrong (locally) on test,
which is generated by following code:

int n = (int)1e5;
printf("%d %d\n", n, n);
printf("1 %d\n", n);
printf("1 2 97\n");
printf("1 3 98\n");

for (int i = 2; i <= n - 2; i++)
   printf("%d %d %d\n", i, i + 2, 99);
printf("%d %d 98\n", n - 1, n);

To be exact, they answer
50001 1.0000000
1 2 ... n-2 n

On the other side, answer is obviously path
1 3 ... n-1 n, because probability to not meet Kraken is (4 / 100^(n/2)) for it
and (3 / 100^(n / 2)) for path 1, 2, ...

By the way, it is far from the worst test. Actually, any test like this
(with two diverging paths of same length), but where difference between products
of (1 - probability of meeting Kraken) on edges of paths is 1 and these products
are big is going to be much, much worse.

P. S. If I am misunderstanding something (for example, 10^(-6) error is allowed for
answer, not only for output (though even if it is true, it is not clear from
Russian problem statement)), then I am very sorry.

P. P. S. In hindsight it looks like statement is a bit unclear, but tests are OK
(it looks like checker does allow any path with probability to meet Kraken not more
than 10^(-6) + lowest probability), but formally, it is said in statement that path
should be optimal, just answer can be written with some error). If it is so, I
apologize for "wrong call", but I still would like to see some tweaks to statement.

Edited by author 30.07.2014 04:29

I've read all posts but still do not understand what's wrong.
my solution:
-ignores names mentioned twice
-output 2 spaces, but not points
-outputs only 20 first names
-consists of 'sun' in the beginning

can anyone please give any tests or hints?

Hope it will help:

5 5 6
5 5 5 5 5 0

2 5 4
3 3 3 1

41 17 16
44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 37

41 17 15
47 47 47 47 47 47 47 47 47 47 47 47 47 47 39

31 13 20
21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 4

3 3 6
2 2 2 2 1 0

5 6 4
8 8 8 6

5 2 3
4 4 2

3 2 9
1 1 1 1 1 1 0 0 0

3 4 10
2 2 2 2 2 2 0 0 0 0

2 3 9
1 1 1 1 1 1 0 0 0

6 2 13
1 1 1 1 1 1 1 1 1 1 1 1 0

4 5 10
2 2 2 2 2 2 2 2 2 2

I solve this problem with C++ first and got WA#6, but I can't find where is my problem, so I rewrite it with C# with the same solution, but to my surprise, this time I got AC.
And even till now I don't know what are the differences between my two lovely code.
Any idea?
//Sorry for my poor English

«прийти» вместо «придти»

Hi,

Does anyone know what the test case is? I've tried my solution against the following, and they seem to be correct. A little lost right now.

"No", "OnLine", "AbabaAab", "abaabaaba", "2101221012", "122212221", "A", "AA", "aba", "saaasaaas", "babab"

Solutions
=========
NoN
OnLineniLnO
AbabaAababA
abaabaabaaba
210122101221012
1222122212221
AA
AAA
ababa
saaasaaasaaas
bababab


Thanks!

Edited by author 03.03.2012 08:35

Какие есть способы избежать Time limit?

What are the ways to avoid Time limit?

This is my Prog:

var
  i,n,k,l,g:integer;
begin
  read(n,k);
  l:=1;
  i:=1;
  while i<k do
  begin
    l:=l+i;
    inc(g);
    if l<n then
    i:=i*2
    else break;
  end;
  while l<n do
  begin
    l:=l+k;
    inc(g);
  end;
  writeln(g);
end.

flow can solve this.

Edited by author 19.02.2010 16:08

If u used Dijkstra alg, u should add min price for all pices, and theh deduct it from unswer multiplying on count of the tops.

Sorry for my eng :D

I got WA 10, where is wrong?


///////////////////////
#include <iostream>
using namespace std;
int main()
{
    int N,M,sum,counter,mul;
    counter=0;
    cin>>N>>M;
    sum=M;
    mul=N*M;
    while(sum!=mul)
    {
        N--;
        sum+=N;
        counter++;
        if(sum==mul)
            break;
        M--;
        sum+=M;
        counter++;
    }
    cout<<counter<<endl;

}

Try different epsilons. I got AC with solution that had WA 30,32,34 before that. And all that i changed was epsilon.

#include <iostream>
#include <math.h>
#include <iomanip>

using namespace std;

int main()
{
    float a[4] = { 0 };
    int i;

    for (i = 0; i < 4; i++){
        cin >> a[i];
    }

    for (i = 0; i < 4; i++){
        printf("%.4f\n", sqrt(a[i]));
    }

    return 0;
}

Hi all.

I tried to solve this problem with standart method. I devide all numbers on GCD, and calculate all x in A*x + B*y and I tried find the maximum T, T <= N.

In cicle I write something like this:
if ( max < T )
{
   max = T;
   //something too
}
and have WA16.
After WA16 I tried fix my program, but don't find anything global. Fix something right on wrong, I 13 times get WA 1 - 16.

Then I changed ( max < T ) on ( max <= T ), and don't send, because did not think, what that will be changed WA16 on AC. I was wrong.

I don't know why that fix is right, can someone explain me?

Thanks. Sorry for bad English.

#include <iostream>
#include <string>


using namespace std;


int main()
{
    int n;
    cin>>n;
    int p[n];
    string posi;
    for(int i=0; i<n; i++)
    {
        cin>>posi;
        if ((posi[0]<'a'||posi[0]>'h')||(posi[1]<'1'||posi[1]>'8'))
            return 0;
        if (posi[0]>='c'&&posi[0]<='f')
        {
            if (posi[1]>='3'&&posi[1]<='6')
                p[i]=8;
            if (posi[1]=='2'||posi[1]=='7')
                p[i]=6;
            if (posi[1]=='1'||posi[1]=='0')
                p[i]=4;
        }
        if (posi[0]=='b'||posi[0]=='g')
        {
            if (posi[1]>='3'&&posi[1]<='6')
                p[i]=6;
            if (posi[1]=='2'||posi[1]=='7')
                p[i]=4;
            if (posi[1]=='1'||posi[1]=='8')
                p[i]=3;
        }
        if (posi[0]=='a'||posi[0]=='h')
        {
            if (posi[1]>='3'&&posi[1]<='6')
                p[i]=4;
            if (posi[1]=='2'||posi[1]=='7')
                p[i]=3;
            if (posi[1]=='1'||posi[1]=='8')
                p[i]=2;
        }
    }
    for (int i=0; i<n; i++)
        cout<<p[i]<<endl;

    return 0;
}

Can not get past this one, all tests in the discussion are passed correctly. Can anyone hint on why test #3 may be failed?

Help me. I got WA7.
Give me some test.

try this test:
11

answer is 11, not 1