It's not so interesting to publish ready code, but for those who stuck on this problem the following algorithm could be useful:

1. First of all, build generator, that will generate random tests with specified phone number length and number of words. It will helpful, since you don't know, which tests are runned when you send you code for check.

2. Convert your words to digits and remove those of them that aren't contained in phone number. Also remove duplications that can appear after this converting. During this process build dictionary that will contain converted word as a key, and original word as a value. Last one will be needed to output the result.

3. Sort converted words by length in descendent order.

4. Take every converted word and find all its inclusions to the phone number. Build dictionary that will contain found index as key and list of converted words as value.

5. Now use recursive function which initially will get index=0 as argument, find all words from dictionary for the index and loop them, taking their length to get next index.
If next index equals phone number length, you found one of the solutions.

6. Optimize the function to eleminate redundant calls. I mean, on specific step you can check if the next searched solution is expected to be better than found one or not.

I'm not sure that this algorithm is the best, but at least I got "accepted" on C# with 600 ms performance.

My approach divides into 2 cases

I) A>= sqrt(N) or B>=sqrt(N)
  this can be solved by brute force in O(sqrt(N))

II) A<sqrt(N) and B<sqrt(N)
  now this is more interesting
  in case of gcd(A,B)=1
  you can proof that there exist x,y>=0 that A*x+B*y = N
    since A*x congruent to N (mod B) -> x = N*inv(A,B) % B
    hence 0<=x<=B-1 but B<sqrt(N) and A<sqrt(N)
    then A*x < N so y >= 0
  in case of gcd(A,B)>1
    that's your work!

:)

My program answer true for input from example(for big number too), but i get "Wrong answer" on test 1.

#include <stdio.h>
#include <math.h>
#define N 1000000
int main(int argc, char **argv)
{
    long long int array[N];
    int i=0;
    while (scanf("%Ld", &array[i])>0) {
        i++;
    }
    for(i-=1;i>=0;i--)
        printf("%.4f\n", sqrt(array[i]));
    return 0;
}

I don't think problem statement is clear.. and obviously algorithm difficult is far not worth than 10000+ reading comprehension is possible

Edited by author 16.10.2016 11:24

Don't use scanf !!!!!!

Edited by author 16.10.2016 18:23

For 2 4 it should be days 2 and 4.
For 100 200 it shoould be 100, 102...148(count must be 25 already)...200(count is 51).

I used the formulas with phi and solved a system of 2 equations to get the coefficients, in python using floats.

Any hint why I get WA8? all tests on the forum work.

Hello! Why I got WA?
I can't understand :| IMO this must work... Tnx all.
----------------------------------------------------
dayTotal = (LastDay - FirstDay) + 1;
   for(counter = 1; counter <= dayTotal; counter++)
      {
    n = counter % 2;
    if(n != 0)
       fuse++;
    }
-----------------------------------------------------

I think it takes first player 5 turns to get '*', and 3 turns to move outside,it is at least 8 turns. why is 5 turns?

Wrote on Pascal:

var
  i, j: integer;
  ms, a, b: integer;
  arrg: array of integer;
begin
  Read(ms);
  SetLength(arrg, ms);

  for i := 0 to arrg.Length - 1 do begin
    var temp: integer;
    Read(temp);
    arrg[i] := temp;
  end;

  for j := 1 to arrg.Length - 1 do
    for i := 1 to arrg.Length - j do
      if arrg[i - 1] > arrg[i] then
        Swap(arrg[i - 1], arrg[i]);

  a := arrg.Length div 2;

  for i := 0 to a do
    b := b + arrg[i] div 2 + 1;

  Write(b);
end.

Wrong answer ( test 1 ).

        long ans[] = new long[23];
        ans[2]=lim[2];
        for (int i=4; i<=20; i+=4) {
            int half=i/2;
            ans[i]=lim[half]*lim[half];
            ans[i+2]=lim[half]*lim[half+2];
        }
        System.out.println(ans[N]);

Как узнать заранее, сколько выделять ячеек для решета?

#include <bits/stdc++.h>
using namespace std;
const int N = 112345;
int a[N];
int b[N];

main()
{
    string s, t;
    cin >> s;
    int cnt = 0;
    int mx=0;
    int l=0;
int cnte=0;
    for(int i = s.size() - 1; i >= 0; i --)
    {
        t = s[i] + t;
        a[0] = 0;

        for(int j = 1; j < t.size(); j ++)
        {
            int x = a[j - 1];
            while(x > 0 && t[x] != t[j])
                x = a[x - 1];
            if(t[x] == t[j])
                x ++;
            a[j] = x;
            mx = max(mx, a[j]);

        }
            b[i]=mx;
            if(mx==0)cnte++;
            mx=0;

    }
    if(cnte==s.size()){cout<<s;return 0;}
    else
for(int i=0;i<s.size();i++){if(b[i]>=1)cout<<s[i];}


}
// any suggestion guys I have no idea what can be  the fifth test thanks in advance

6 2
2 10 11 16 16 21
32
33

Can you give me a test for wa 7, please?

import sys
import math
string = sys.stdin.read()
def string_parsing(string):
    result = []
    str = ''
    for j in range(len(string)):
        if string[j] != ' ' and string[j] != '\n':
            str += string[j]
        elif str !='':
            result.append(str)
            str = ''
    return result

list = string_parsing(string)
list = [round(math.sqrt(float(elem)), 5) for elem in list]
list = ["{0:.5f}".format(elem) for elem in list]
for i in range(len(list)):
    sys.stdout.write(str(list.pop()) + '\n')

#What's wrong?



Edited by author 12.10.2016 16:17

6
0 0
5 -10
10 -10
5 -5
10 -5
20 0

7
1 2 10
2 3 30
3 5 20
5 4 20
4 2 20
3 6 10
1 6 7

ans:
17
1 2 10
2 3 30
3 5 20
5 4 20
4 2 20
3 6 10
1 6 7

Is this output acceptable? Or do we have to remove flow cycles?

update: got ac without removing cycles.

Edited by author 13.10.2016 06:41

What is in test 4?
I have WA and I dont know what is wrong.

I did it! I have TL 15 for a long time, but now I solved the problem. I use treap with gcd, but treap has a big constant and gcd works for O(log), so I write binary algorithm of calculating gcd instead of Euclid and it works!

hello,i got wa3.can you tell me why?or give me some tests.thank you very much!
the source:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;


namespace Timus1003
{
    class Program
    {
        static void Main(string[] args)
        {
            System.Threading.Thread.CurrentThread.CurrentCulture = System.Globalization.CultureInfo.InvariantCulture;
            List<Phone> arrayList=new List<Phone>();
            while(true)
            {


                string phoneNumber=Console.ReadLine();
                if(phoneNumber=="-1")
                {
                    break;
                }
                Phone phone = new Phone();
                phone.PhoneNumber =phoneNumber ;
                phone.Size =Convert.ToInt32(Console.ReadLine());
                string[] dics = new string[phone.Size];
                int n=0;
                while(n<phone.Size)
                {
                    dics[n] = Console.ReadLine();
                    n++;
                }
                phone.Dics = dics;
                arrayList.Add(phone);
            }
    //        Console.WriteLine("out");
            for(int i=0;i<arrayList.Count;i++)
            {

                Phone phone = arrayList[i];
                phone.Dics = phone.Dics.OrderByDescending(s => s.Length).ToArray<string>();
                String[] str = new String[phone.Dics.Length];
                for(int j=0;j<phone.Dics.Length;j++)
                {
                    str[j] = wordToNumber(phone.Dics[j]);
                }
                phone.HasSolution=find(phone.PhoneNumber, str, phone);
                if(phone.HasSolution)
                {
                    string solutionStr = "";
                    for(int k=0;k<phone.Solutions.Count;k++)
                    {
                        if(k==phone.Solutions.Count-1)
                        {
                            solutionStr = solutionStr + phone.Solutions[k] + "";
                        }
                        else
                        {
                            solutionStr = solutionStr + phone.Solutions[k] + " ";
                        }

                    }

                    Console.WriteLine(solutionStr);
                }
                else
                {
                    Console.WriteLine("No solution.");
                }
            }

            Console.ReadLine();


        }

        public static bool find(string phoneNumber,string[] dics,Phone phone)
        {

            for (int i = 0; i < dics.Length;i++ )
            {

          //      if (phoneNumber == "") return true;
                if (phoneNumber == dics[i])
                {
                    phone.Solutions.Add(phone.Dics[i]);
                    //Console.Write(phone.Dics[i] + " ");
                    return true;
                }

                if (phoneNumber.IndexOf(dics[i]) == 0)
                {
                    phone.Solutions.Add(phone.Dics[i]);
                   // Console.Write(phone.Dics[i] + " ");
                    string newPhoneNumber = phoneNumber.Substring(dics[i].Length);
                    if(find(newPhoneNumber, dics, phone))
                    {
                        return true;
                    }
                    else
                    {
                        phone.Solutions.RemoveAt(phone.Solutions.Count-1);
                        continue;
                    }

                }


            }
         //   Console.WriteLine("No solution.");
            return false;
        }


        public static string wordToNumber(string word)
        {
            char[] wordArr = word.ToCharArray();
            char[] numArr = new char[wordArr.Length];
            for (int i = 0; i < wordArr.Length;i++ )
            {
                numArr[i] = charToNumber(wordArr[i]);
            }
            return new String(numArr);
        }

        public static char charToNumber(char mychar)
        {
            switch(mychar)
            {
                case 'i':
                case 'j':
                    return '1';
                case 'a':
                case 'b':
                case 'c':
                    return '2';
                case 'd':
                case 'e':
                case 'f':
                    return '3';
                case 'g':
                case 'h':
                    return '4';
                case 'k':
                case 'l':
                    return '5';
                case 'm':
                case 'n':
                    return '6';
                case 'p':
                case 'r':
                case 's':
                    return '7';
                case 't':
                case 'u':
                case 'v':
                    return '8';
                case 'w':
                case 'x':
                case 'y':
                    return '9';
                case 'o':
                case 'q':
                case 'z':
                    return '0';
                default:
                    return mychar;
            }

        }
    }

    class Phone
    {
        string phoneNumber;

        public string PhoneNumber
        {
            get { return phoneNumber; }
            set { phoneNumber = value; }
        }
        int size;

        public int Size
        {
            get { return size; }
            set { size = value; }
        }
        string[] dics;

        public string[] Dics
        {
            get { return dics; }
            set { dics = value; }
        }

        List<string> solutions = new List<string>();

        public List<string> Solutions
        {
            get { return solutions; }
            set { solutions = value; }
        }

        bool hasSolution;

        public bool HasSolution
        {
            get { return hasSolution; }
            set { hasSolution = value; }
        }

    }
}