Passed all the test given in the discussion
I ran 1 bfs from 'r' and another bfs from 's' where i also kept data for those nodes who can have multiple parents.
than I while restoring path from destination to source I selected the node who has higher level from 'r' (that selection occurs if only the node has possibility multiple parents)
returned the ans which is the minimum among the final path

I got AC with 0.015s,216Kb
I had read the problem several time until understand.
N is the length of the digit number.
It will be something like that
a1 a2 a3 ...an
for each ai in a1 a2 a3..an, 0 <= ai < K.
The output number i used was interger (compiler C++ 2010). (no big number).

hope it can help you.
And sorry for my poor English.

Edited by author 25.04.2014 23:05

https://ideone.com/Ocpa4V

I can't figure out what's wrong with my code. I used 'Queue' data structure.

Edited by author 23.01.2018 16:02

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<string>
#include<cmath>
using namespace std;



vector<long long > C(20000,0);
void mult(vector<long long> A,vector<long long> B)
{
    int d=0;
    for(int i=0;i<300;i++)
    {
        for(int j=0;j<300;j++)
        {
            C[i+j]+=B[i]*A[j];
            C[i+j+1]=C[i+j+1]+C[i+j]/100000000;
            C[i+j]=C[i+j]%100000000;
        }
    }
    C[0]++;
    for(int i=0;i<6000;i++)
    {
        C[i+1]=C[i+1]+C[i]/100000000;
        C[i]=C[i]%100000000;
    }
}
vector<long long> D(20000,0);
void mult1(vector<long long> A,vector<long long> B)
{
    int d=0;
    for(int i=0;i<300;i++)
    {
        for(int j=0;j<300;j++)
        {
            D[i+j]+=B[i]*A[j];
            D[i+j+1]=D[i+j+1]+D[i+j]/100000000;
            D[i+j]=D[i+j]%100000000;
        }
    }
    for(int i=0;i<6000;i++)
    {
        D[i+1]=D[i+1]+D[i]/100000000;
        D[i]=D[i]%100000000;
    }
}
void write(vector<long long> A)
{
    bool f=false;
    for(int i=9999;i>=0;i--)
    {
        if(A[i]!=0)
            f=true;
        if(f)
            cout<<A[i];
    }
    cout<<"\n";
}
int main()
{
#ifdef _DEBUG
    freopen("input.txt","rt",stdin);
    freopen("output.txt","wt",stdout);
#endif
    int n;
    cin>>n;

    vector<long long> A(10000,0);
    vector<long long> B(10000,0);
    A[0]=1;
    B[0]=1;
    for(int i=0;i<n;i++)
    {
        mult(A,B);
        mult1(A,B);
        for(int i=0;i<4000;i++)
        {
            B[i]=D[i];
        }
        for(int i=0;i<4000;i++)
        {
            A[i]=C[i];
        }
        for(int i=0;i<4000;i++)
        {
            C[i]=0;
            D[i]=0;
        }
        write(A);
    }
}

Вот код, скорее всего он не пройдет макс тест, но при запуске на первом тесте он выдает мне в студии ответ правильный, а тут нет

I don't understand!!! How given (2, aa) answer is 6. I think that must be 4!!!  Please help, who know that!!!!! (Я не понел Как 2 и аа могут дать ответ 6 Я думаю что должно быть 4 Помогите------------)

I am getting WA 5   Can anyone provide me the test case 5..  or hint to test case 5..

var a,b,c,d,cen,k:integer;
begin
read(a,b,c,d);
while k<>1 do begin
if (a+b>c) then begin
k:=1;cen:=c;end
else a:=a+b;
if(c-d<a)then begin
k:=1;cen:=a;end
else c:=c-d;end;
writeln(cen);
end.

try to change your variables to double, and don't use int.

I think it's clear for the system of linear equations, that if M<N, than it's impossible. If M=N then it may be possible (and I know how to check). How about case M>N? We need to select N pairs that get an unambiguous solution?

http://acm.timus.ru/problem.aspx?space=1&num=1513
It seems that those are the same problem.  In 1513,  just b=INF.
But that problem is of rating of 100, and Lemon Tale is of rating of around 500.

I'd like to thank authors for this problem - it became one of my favorite on Timus!
Thanks again for very interesting problem!
:-)

Unfortunately entirely deterministic version of this algorithm fails on Test #10. So I'm very curious about this Test #10. Because I've done a lot of testing in MATLAB of varoius modification of Floyd-Steinberg dithering algo, including zig-zag proseccing and edge attending. In all cases constraint in statement can be hardened from 20 to 10 and even less. On normal images error is about 6-8.

I guess Test #10 some kind of periodic image, that has bad compatibility with that unnatural restriction put in the problem. I mean it square form and discontinuous nature. I think dithering yield much more better image than that which can be produced by uniform minimization of constrain function.

I solve this issue whit Test #10 by adding a little bit of randomness in my dithering algo. I mean in place of this threashold function:

int quantize(int value) {
    if (127 < value) {
        return 255;
    }
    return 0;
}

I'm using this function:

int quantize(int value, int randomness) {
    if (127 - randomness + rng.nextInt(2 * randomness + 1) < value) {
        return 255;
    }
    return 0;
}

This provides me with magical parameter "randomness" varying which and playing tambourine I got my AC. 8-] I think I should add constraints checking and reprocessing in case the check was a fail, but I'm too lazy, I guess in case of possible future rejudging everything will be fine. :)

I express my sincerest thanks to authors of this beautiful problem. It has bugged me a lot in era of matrix printers how can they do this funny dotted images. Finally I have my answer and I can even do it myself!!!

Edited by author 17.01.2018 02:43

#include <iostream>
using namespace std;

int main()
{
    int k, n, res=0;
    cin >> k >> n;
    int *mas = new int[n];

    for (int i=0; i!=n; i++)
    {
        cin >> mas[i];

        if (mas[i] > k)
        {
            res = res + (mas[i] - k);
        }
        else
        {
            if (res!=0 )
            {
                if ((k - mas[i]) > res)
                {
                    res = 0;
                }
                else
                {
                    res = res - (k - mas[i]);
                }
            }
        }

    }
    cout << res;

    return 0;
}

ll n, m, ans;
st s;
int main(){
  while(cin >> s){
    for(int i = 0;i < s.sz;++i){
      if(s[i] == 'b' || s[i] == 'e' || s[i] == 'h' || s[i] == 'k' || s[i] == 'n' || s[i] == 'q' || s[i] == 't' || s[i] == 'w' || s[i] == 'z' || s[i] ==',')
          ans+=2;
         if(s[i] == 'a' || s[i] == 'd' || s[i] == 'g' || s[i] == 'j' || s[i] == 'm' || s[i] == 'p' || s[i] == 's' || s[i] =='v'|| s[i] == 'y' || s[i] == '.')
             ans+=1;
         if(s[i] == 'c' || s[i] == 'f' || s[i] == 'i' || s[i] == 'l' || s[i] == 'o' || s[i] == 'r' || s[i] == 'u' || s[i] == 'x'|| s[i] == '!')
              ans+=3;
      }
      ans++;
      }
  cout << ans - 1;
    }

Why did you got wa on test 3 ? I'm having the same problem... :(

If you're struggling with test 11, the test is:

1 0 1000000 -2000 1
Exact (up to 1e-14) answer is 0.00628318530714

If your solution passes this, it will most likely pass all tests :)

Только начал изучать С++. Решаю задачки для новичков. Что не так здесь?

#include <iostream>
#include <conio.h>

using namespace std;

int main()
{
    int A;

cout << "How many?";

cin >> A;

if(A < 1 || A > 2000) {
cout << "wrong input!";
}else { if(A <= 4)
        cout << "few";
else if(A <= 9)
        cout << "several";
else  if(A <= 19)
        cout << "pack";
else  if(A <= 49)
        cout << "lots";
else  if(A <= 99)
        cout << "horde";
else  if(A <= 249)
        cout << "throng";
else  if(A <= 499)
        cout << "swarm";
else  if(A <= 999)
        cout << "zounds";
else cout << "legion";}

return 0;
}

Edited by author 15.01.2018 06:34