Obvious solution looks as:
1) Suggest f(n) = amount of ones in numbers from 1 to n
2) Make binary search for f(i)
It is obvious right, but constraint for input number don't allow to fast writing this solution in cpp (because we need in BigInteger). So, in my opinion, constraint are bad.
If we want to make hardships with standart types in cpp and pascal, should take 1 <= n <= 10^100. In other hand, if we don't want to make it, should take 1 <= n <= 10^15.

Am I wrong?

What is wrong with this code... it does exactly what the description says and I can't find my error. Could somebody take a look and help me a bit?

using System;
using System.Collections.Generic;
using System.Text;

namespace _1002.Phone_numbers
{
    class Program
    {
        static void Main(string[] args)
        {
            List<char>[] dictionary = new List<char>[10];

            (dictionary[0] = new List<char>()).AddRange(new char[] { 'o', 'q', 'z' });
            (dictionary[1] = new List<char>()).AddRange(new char[] { 'i', 'j' });
            (dictionary[2] = new List<char>()).AddRange(new char[] { 'a', 'b', 'c' });
            (dictionary[3] = new List<char>()).AddRange(new char[] { 'd', 'e', 'f' });
            (dictionary[4] = new List<char>()).AddRange(new char[] { 'g', 'h' });
            (dictionary[5] = new List<char>()).AddRange(new char[] { 'k', 'l' });
            (dictionary[6] = new List<char>()).AddRange(new char[] { 'm', 'n' });
            (dictionary[7] = new List<char>()).AddRange(new char[] { 'p', 'r', 's' });
            (dictionary[8] = new List<char>()).AddRange(new char[] { 't', 'u', 'v' });
            (dictionary[9] = new List<char>()).AddRange(new char[] { 'w', 'x', 'y' });

            List<String> inputs = new List<string>();

            int c = -1;
            do
            {
                inputs.Add(Console.ReadLine());
                c++;
            } while (inputs[c] != "-1");

            bool procede = true;

            while (procede)
            {
                String number = inputs[0];
                List<String> words = inputs.GetRange(2, Int32.Parse(inputs[1]));
                inputs.RemoveRange(0, Int32.Parse(inputs[1]) + 2);

                if (inputs[0] == "-1") procede = false;

                String output = String.Empty;

                while (words.Count > 0)
                {
                    StringBuilder outputs = new StringBuilder();
                    for (int i = 0; i < number.Length; i++)
                    {
                        if (i == 1 && output == String.Empty)
                        {
                            words.Clear();
                            break;
                        }

                        foreach (String word in words)
                        {
                            bool check = false;

                            if (dictionary[Int32.Parse(number[i].ToString())].Contains(word[0]))
                            {
                                for (int j = 1, k = i + 1; j < word.Length && k < number.Length; j++, k++)
                                {
                                    if (dictionary[Int32.Parse(number[k].ToString())].Contains(word[j]) == false)
                                    {
                                        break;
                                    }
                                    else
                                    {
                                        check = true;
                                    }
                                }

                                if (check)
                                {
                                    outputs.Append(word + " ");
                                    i += word.Length - 1;
                                    words.Remove(word);
                                    break;
                                }
                            }
                        }
                    }

                    if (output == String.Empty)
                    {
                        output = outputs.ToString().TrimEnd();
                    }
                    else
                    {
                        if (outputs.ToString().TrimEnd().Split(' ').Length < output.Split(' ').Length)
                        {
                            output = outputs.ToString().TrimEnd();
                        }
                    }
                }

                if (output == String.Empty)
                {
                    Console.WriteLine("No solution.");
                }
                else
                {
                    Console.WriteLine(output);
                }
            }
        }
    }
}

In english language:
"and the hour-hand rotates 60 times slower than the minute-hand." ->
"and the hour-hand rotates 12 times slower than the minute-hand.", and similar mistake in russian.

I've got 'New judgements' letter with links like this:

http://acm.timus.ru/status.aspx?space=1&num=1463&author=

i.e. nothing after 'author='. I think there should be my author id.

What is idea for this priblem?
I fill matrix for chess:
n = 4
0101
1010
0101
1010
0 - smoll number
1 - big number
Why my solve is wrong?(((
I got WA4.

I tryed to minimize using of memory, but...


#include <cstdio>
#include <stack>
#include <map>

using namespace std;

map<unsigned int,stack<unsigned int> > m;

unsigned int n, i, b;
unsigned short a;
char c;


void main(void)
{
    scanf("%d",&n);

    for(i=0;i<n;i++){

        scanf("%s%s",c,c);

        if (c == 'U'){
            scanf("%d %d\n",&a,&b);
            m[a].push(b);
        }else{
            scanf("%d\n",&a);
            printf("%d\n",m[a].top());
            m[a].pop();
        }
    }
}

Some new tests by Alexander Kouprin were added. 38 authors lost AC after rejudge.

Could you please verify test #5 and my program's output on it? I'm checking everything inside my program and it does not get OLE, but still it gets WA#5.

Какой может быть 2 тест.
n = 1?  Если так то доблжен быть ответ в 3 строчки?
a
b
c?

At my first atempt I should get Crash 14,but I got WA 14,when I change the size of array I got Ac...

I have WA#10.
I can't find my error.
Please, help!

(C#)

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            System.Threading.Thread.CurrentThread.CurrentCulture = System.Globalization.CultureInfo.InvariantCulture;
            while (true)
            {
                String Number = Console.ReadLine().Trim();
                if (Number == "-1")
                {
                    break;
                }
                SortedList<String, String> Dict = new SortedList<string, string>();
                Int32 DictSize = Convert.ToInt32(Console.ReadLine().Trim());
                for (int i = 0; i < DictSize; i++)
                {
                    String Val = Console.ReadLine().Trim();
                    String Key = getPhoneByWord(Val);
                    if (!Dict.Keys.Contains(Key) && Key.Length > 0)
                    {
                        Dict.Add(Key, Val);
                    }
                }
                if (Dict.Count == 0 || Number.Trim().Length == 0)
                {
                    Console.WriteLine("No solution.");
                }
                else
                {
                    LinkedList<Byte>[] WaweDict = GetWaweDict(Number, Dict);
                    LinkedList<Byte> Zero = new LinkedList<Byte>();
                    Zero.AddLast(0);
                    SortedList<Byte, Byte> RP = new SortedList<Byte, Byte>();
                    Console.WriteLine(RPtoOutput(WaweForward(Zero, RP, WaweDict, Convert.ToByte(Number.Length)), Dict, Convert.ToByte(Number.Length), Number).Trim());
                }
            }
        }

        private static SortedList<String, String> replaceVata(SortedList<String, String> Input, String Number)
        {
            SortedList<String, String> Dict = new SortedList<string,string>();
            foreach (KeyValuePair<String, String> KVP in Input)
            {
                if (Number.Contains(KVP.Key))
                {
                    Dict.Add(KVP.Key, KVP.Value);
                }
            }
            return Dict;
        }

        private static String getPhoneByWord(String Input)
        {
            String Result = Input.Replace('i', '1');
            Result = Result.Replace('j', '1');
            Result = Result.Replace('a', '2');
            Result = Result.Replace('b', '2');
            Result = Result.Replace('c', '2');
            Result = Result.Replace('d', '3');
            Result = Result.Replace('e', '3');
            Result = Result.Replace('f', '3');
            Result = Result.Replace('g', '4');
            Result = Result.Replace('h', '4');
            Result = Result.Replace('k', '5');
            Result = Result.Replace('l', '5');
            Result = Result.Replace('m', '6');
            Result = Result.Replace('n', '6');
            Result = Result.Replace('p', '7');
            Result = Result.Replace('r', '7');
            Result = Result.Replace('s', '7');
            Result = Result.Replace('t', '8');
            Result = Result.Replace('u', '8');
            Result = Result.Replace('v', '8');
            Result = Result.Replace('w', '9');
            Result = Result.Replace('x', '9');
            Result = Result.Replace('y', '9');
            Result = Result.Replace('o', '0');
            Result = Result.Replace('q', '0');
            Result = Result.Replace('z', '0');
            return Result;
        }

        private static LinkedList<Byte>[] GetWaweDict(String Number, SortedList<String, String> Dict)
        {
            LinkedList<Byte>[] Result = new LinkedList<Byte>[Number.Length + 1];
            for (int i = 0; i < Result.Length; i++)
            {
                Result[i] = new LinkedList<byte>();
            }
            foreach (String Key in Dict.Keys)
            {
                String NumTemp = Number;
                Int32 Ins = NumTemp.IndexOf(Key);
                while (Ins != -1)
                {
                    if (!Result[Ins].Contains(Convert.ToByte(Ins + Key.Length)))
                    {
                        Result[Ins].AddLast(Convert.ToByte(Ins + Key.Length));
                    }
                    String Placebo = "";
                    for (int i = 0; i < Key.Length; i++)
                    {
                        Placebo += " ";
                    }
                    NumTemp = NumTemp.Substring(0, Ins) + Placebo + NumTemp.Substring(Ins + Key.Length, NumTemp.Length - Ins - Key.Length);
                    Ins = NumTemp.IndexOf(Key);
                }
            }
            return Result;
        }

        private static SortedList<Byte, Byte> WaweForward(LinkedList<Byte> Starts, SortedList<Byte, Byte> RP, LinkedList<Byte>[] WaweDict, Byte LenPlus1)
        {
            Boolean Drop = true;;
            LinkedList<Byte> RecurseInp = new LinkedList<byte>();
            foreach (Byte Start in Starts)
            {
                foreach (Byte End in WaweDict[Start])
                {
                    if (!RecurseInp.Contains(End))
                    {
                        RecurseInp.AddLast(End);

                    }
                    if (!RP.ContainsKey(End))
                    {
                        Drop = false;
                        RP.Add(End, Start);
                    }
                }
            }
            if (Drop)
            {
                return new SortedList<byte,byte>();
            }
            else
            {
                if (RP.ContainsKey(LenPlus1))
                {
                    return RP;
                }
                else
                {
                    return WaweForward(RecurseInp, RP, WaweDict, LenPlus1);
                }
            }
        }

        private static String RPtoOutput(SortedList<Byte, Byte> RP, SortedList<String, String> Dict,Byte LenPlus1,String Number)
        {
            if (LenPlus1 > 0)
            {
                if (RP.ContainsKey(LenPlus1))
                {
                    return RPtoOutput(RP, Dict, RP[LenPlus1], Number) + " " + Dict[Number.Substring(RP[LenPlus1], LenPlus1 - RP[LenPlus1])];
                }
                else
                {
                    return "No solution.";
                }
            }
            else
            {
                return "";
            }
        }
    }
}

Looks like that there is a mistake in the statement. Y is not less than 99, it is less than 999.
A solution where Y is stored in a variable of type Byte (in Pascal) gets WA 8. Having changed Byte with Integer I got AC.

Edited by author 15.11.2009 18:42

Подскажите набор входных данных для проверки данного теста

can anybody tell me what the #32 test is ????
i got wa on this test........thanks a lot /!!!!

Hello, my program does this:

i find the number of numbers with sum S and number of digits n/2, and store it in position SUM[S]
The total number of solutions is summation of SUM[S]*SUM[S] over all possible S

But I get the answer 669 in this case....where am I wrong?

Here's my code:
main()
{
 int N , sums[100] , end , t , t2 , cursum , total = 0;
 scanf("%d" , &N);
 for(t = 0 ; t <= 36 ; t++)
  sums[t] = 0;
 end = pow(10 , N / 2);
 for(t = 0 ; t < end ; t++)
 {
  cursum = 0;
  t2 = t;
  while(t2 > 0)
  {
   cursum += t2 % 10;
   t2 /= 10;
  }
  sums[cursum]++;
 }
 for(t = 0 ; t <= 36 ; t++)
  total += sums[t] * sums[t];
 printf("%d" , total);
}

Hello!
I don't understand, how can some people solve problems whis time=0,01?? In spite of my well solution has time=0,15..) They know tests?))

This is TEST N1 , excluded additional spaces and newlines...
(Enjoy)

17
11110001111100111
11110001111100111
11110001111100111
11110001111100111
11110001111100111
11111001111100111
11110101111100111
11110011111100111
11110001111100111
11110001111100111
11110001111100111
11110001111100111
11110001111100111
11110001111110111
11110001111101111
11110001111100111
11110001111100111

So what the f*ck? I got WA on Test 1, but my program works right. I think something is in the input. How to get input data?
(sorry for my bad english)