module Main where
--------------------------------------------------------------------------------
toCandetat :: Char -> [Char]
toCandetat '0' = "oqz"
toCandetat '1' = "ij"
toCandetat '2' = "abc"
toCandetat '3' = "def"
toCandetat '4' = "gh"
toCandetat '5' = "kl"
toCandetat '6' = "mn"
toCandetat '7' = "prs"
toCandetat '8' = "tuv"
toCandetat '9' = "wxy"
toCandetat n = error "unkown numb"
--------------------------------------------------------------------------------
convertToCandedat :: String -> [String]
convertToCandedat = map toCandetat
--------------------------------------------------------------------------------
testWord :: String -> [String] -> Bool
testWord str can = and $ zipWith elem str  can
--------------------------------------------------------------------------------
loop :: [String] -> String -> String
loop []     acc = tail acc
loop ["-1"] acc = tail acc
loop in_str acc = loop next (acc ++ "\n" ++ fixPart)
  where
   fixPart         = if part == "" then "No soluton." else part
   part            = partSolve test cand []
   (numb:count:xs) = in_str
   cand            = convertToCandedat numb
   int_count       = read count
   (test, next)    = splitAt int_count xs
--------------------------------------------------------------------------------
partSolve :: [String] -> [String] -> String -> String
partSolve []     []  acc                  = tail acc
partSolve (x:xs) can acc | testWord x can = skipX  ++ nextXs
                         | otherwise      = partSolve xs can             acc
  where
    lenX   = length x
    skipX  = partSolve xs can             acc
    nextXs = partSolve xs (drop lenX can) (acc ++ " " ++ x)
partSolve _      _   _                    = ""
--------------------------------------------------------------------------------
main :: IO ()
main = do
  in_str <- getContents
  putStr $ loop (words in_str) []
--------------------------------------------------------------------------------

what is test5 look like?

my solution passing all test from my head
can you advice what's wrong:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
import static java.util.stream.Collectors.toList;

/**
 * solution for http://acm.timus.ru/problem.aspx?space=1&num=1002
 */
public class Step {

    private static Map<Character, List<Character>> mapping;

    public static void main(String[] args) throws IOException {
        new Step().solveMe(new BufferedReader(new InputStreamReader(System.in)));
    }

    public static Map<Character, List<Character>> buildMapping() {
        Map<Character, List<Character>> map = new HashMap<>();
        map.put('1', Arrays.asList('i', 'j'));
        map.put('2', Arrays.asList('a', 'b', 'c'));
        map.put('3', Arrays.asList('d', 'e', 'f'));
        map.put('4', Arrays.asList('g', 'h'));
        map.put('5', Arrays.asList('k', 'l'));
        map.put('6', Arrays.asList('m', 'n'));
        map.put('7', Arrays.asList('p', 'r', 's'));
        map.put('8', Arrays.asList('t', 'u', 'v'));
        map.put('9', Arrays.asList('w', 'x', 'y'));
        map.put('0', Arrays.asList('o', 'q', 'z'));
        return map;
    }

    public static Trie buildTrie(List<String> dictionary) {
        return dictionary.stream().reduce(
                Trie.EMPTY_TRIE, (node, word) -> node.buildTree(node, word),
                (node, node2) -> node.append(node));
    }

    private void solveMe(BufferedReader in) throws IOException {
        String n;
        mapping = buildMapping();
        Map<String, Trie> input = new HashMap<>();
        while (!(n = in.readLine()).equals("-1")) {
            int s = Integer.parseInt(in.readLine());
            List<String> dict = in.lines().limit(s).collect(toList());
            input.compute(n, (key, val) -> buildTrie(dict));
        }
        input.forEach((s, trie) -> System.out.println(solution(s, trie)));
    }

    public String solution(String number, Trie root) {

        List<List<String>> result = root.filter(number);
        if (result.isEmpty()) {
            return "No solution.";
        }
        List<String> bestShot = result.stream().reduce((List<String> minList, List<String> other) -> {
            if (minList.size() >= other.size()) {
                return other;
            }
            return minList;
        }).get();
        return String.join(" ", bestShot);
    }

    public static class Trie {

        public static final Trie EMPTY_TRIE = new Trie((char) 0);
        private final Character ch;
        private final Map<Character, Trie> nexts;
        private final boolean isWord;

        public Trie(Character ch) {
            this(ch, new HashMap<>(), false);
        }

        private Trie(Character ch, boolean isWord) {
            this(ch, new HashMap<>(), isWord);
        }

        private Trie(Character ch, Map<Character, Trie> nexts, boolean isWord) {
            this.ch = ch;
            this.nexts = nexts;
            this.isWord = isWord;
        }

        public List<List<String>> filter(String number) {
            List<List<String>> lists = new ArrayList<>();
            List<String> e = new ArrayList<>();
            filterHelper(lists, e, number, "", this);
            return lists;
        }

        private void filterHelper(List<List<String>> acc, List<String> result, String number, String word, Trie node) {
            if (node.isWord) {
                if (number.length() == 0) {
                    result.add(word);
                    acc.add(result);
                    return;
                }
                List<String> res = new ArrayList<>(result);
                res.add(word);
                filterHelper(acc, res, number, "", this);
            }

            List<Character> maps = mapping.get(number.charAt(0));
            maps.forEach(e -> {
                Trie next = node.nexts.get(e);
                if (next != null) {
                    filterHelper(acc, new ArrayList<>(result), number.substring(1), word + next.ch, next);
                }
            });
        }

        public Trie buildTree(Trie root, String word) {
            char c = word.charAt(0);
            if (word.length() == 1) {
                Trie newTrie = new Trie(c, true);
                return root.append(newTrie);
            } else {
                Trie newTrie = new Trie(c, false);
                return root.append(buildTree(newTrie, word.substring(1)));
            }
        }

        public Trie append(Trie other) {
            Trie trieCopy = new Trie(this.ch, this.nexts, this.isWord);
            Trie newVal = other;
            if (trieCopy.nexts.containsKey(newVal.ch)) {
                Trie next = trieCopy.nexts.get(newVal.ch);
                Trie initial = new Trie(next.ch, next.nexts, next.isWord);
                newVal = newVal.nexts.values().stream().reduce(initial, Trie::append);
            }
            trieCopy.nexts.put(newVal.ch, newVal);
            return trieCopy;
        }

        @Override
        public String toString() {
            StringBuilder bld = new StringBuilder();
            bld.append(ch).append(" = [");
            nexts.forEach((c, n) -> bld.append(n).append(" "));
            return bld.append("]").append(isWord ? " = true" : "").toString();
        }
    }
}

def word_to_num(word):
    d=
{'a':'2','b':'2','c':'2','d':'3','e':'3','f':'3','g':'4','h':'4','i':'1','j':'1','k':'5','l':'5','m':'6','n':'6','o':'0','p':'7','q':'0','r':'7','s':'7','t':'8','u':'8','v':'8','w':'9','x':'9','y':'9','z':'0'}
    s=''
    for i in word:
        s+=d[i]
    return s
from itertools import permutations
while True:
    num_dict={}
    num_list=[]
    word_list=[]
    num = input()
    if num=='-1':
        break
    loop_len = int(input())
    for i in range(loop_len):
        word_list.append(input())
    for item in word_list:
        num_dict[word_to_num(item)]=item
        num_list.append(word_to_num(item))
    perm = permutations(num_list,2)
    x=0
    for k,v in list(perm):
        if k+v==num:
            print(num_dict[k]+' '+num_dict[v])
        else:
            x += 1

    if x==loop_len*(loop_len-1):
        print('No solution')

Each number maps to several letters of the alphabet. However, notice that several letters map to a single digit. If you can't go to the mountain, bring the mountain to you. Convert the words found in the dictionary for each case into digits, using the given map. Looking up which digit a letter maps to can be done in constant time if you use the right data structure. Then all that is left is to compare against the phone number given.

Does not pass even the first test.

Cod:

telefon={"i":1,"j":1,"a":2,"b":2,"c":2,"d":3,"e":3,"f":3,"g":4,"h":4,"k":5,"l":5,"m":6,"n":6,"p":7,"r":7,"s":7,"t":8,"v":8,"u":8,"w":9,"x":9,"y":9,"o":0,"q":0,"z":0}


def sortirovka(nomerok,slovarik):
    nomerok = str(nomerok)
    o=len(nomerok)
    k=[]
    for i in range(len(slovarik)):
        if len(slovarik[i])<=o:
            k.append(slovarik[i])
    return k

def perevod(slovarik):
    k=[]
    for i in range(len(slovarik)):
        p=''
        for o in range(len(slovarik[i])):
            c=telefon[slovarik[i][o]]
            p=p+str(c)
        k.append(p)
    return k

def bolodn(slovara,nomera):
    i=0
    l=[]
    z=0
    u=len(str(nomera))
    while i != len(slovara):
        n = int(len(str(slovara[i])))
        if slovara[i] == str(nomera)[0:n]:
            l.append(slovara[i])
            z+=len(slovara[i])
            nomera = str(nomera)[n:]
        i += 1
    if z==u:
        return l


def sdvig(l, p):
    return l[-p:] + l[:-p]


while True:

    nomer=int(input())
    if nomer == -1:
        break
    if nomer != -1:
        vslovare=int(input())
    i=0

    slovar=[]
    while i!=vslovare:
        c=input()
        slovar.append(c)
        i+=1



    slovar=sortirovka(nomer,slovar)

    slovar1=slovar
    slovar=(perevod(slovar))


    y={}
    for i in range(len(slovar1)):
        d=slovar1[i]
        d1=slovar[i]
        y[d1]=d

    for i in range(1):
        a=0
        z=[]
        while a!=len(slovar):

            k=bolodn(slovar,nomer)
            if k!=None:
                z.append(k)
            slovar=sdvig(slovar,1)
            a+=1

        if len(z)==0:
            print ("No solution.")
        if len(z)>0:

            b=len(z)-1
            min=len(z[0])
            t=0
            i=1
            if (len(z))>1:
                while i!=len(z):
                    if int(len(z[i]))<int(min):
                        min=z[i]
                        t=i
                    i+=1
                x = z[t]
            else:

                x=z[t]

            if len(x)>=1:
                j=''
                for i in range(len(x)):
                    ss=x[i]
                    j+=str(y[ss])
                    if i<len(x)-1:
                        j+=' '
                print (j)

Hello All,
Can someone please help to understand the first test case or where I am going wrong in my code , I haven't used any algorithm, its just a brute force approach.

```
#include <stdio.h>
#include <stdlib.h>

char number[100];
char words[50001][101];

int main(int argc, char **argv) {
    int map_alphabet[26], i , j , c , n, master_begin_index, master_end_index ,output_buffer_index, pivot, number_len, is_candidate;
    char output_buffer[101];
    map_alphabet['i'-97] = 1;
    map_alphabet['j'-97] = 1;
    map_alphabet['a'-97] = 2;
    map_alphabet['b'-97] = 2;
    map_alphabet['c'-97] = 2;
    map_alphabet['d'-97] = 3;
    map_alphabet['e'-97] = 3;
    map_alphabet['f'-97] = 3;
    map_alphabet['g'-97] = 4;
    map_alphabet['h'-97] = 4;
    map_alphabet['k'-97] = 5;
    map_alphabet['l'-97] = 5;
    map_alphabet['m'-97] = 6;
    map_alphabet['n'-97] = 6;
    map_alphabet['p'-97] = 7;
    map_alphabet['r'-97] = 7;
    map_alphabet['s'-97] = 7;
    map_alphabet['t'-97] = 8;
    map_alphabet['u'-97] = 8;
    map_alphabet['v'-97] = 8;
    map_alphabet['w'-97] = 9;
    map_alphabet['x'-97] = 9;
    map_alphabet['y'-97] = 9;
    map_alphabet['o'-97] = 0;
    map_alphabet['q'-97] = 0;
    map_alphabet['z'-97] = 0;

    while( 1 ) {
        number_len = i = j = 0;
        while ( ( c = getchar() ) != '\n' && c != EOF)
            number[ i ++ ] = c;
        number[ i ] = '\0';
        number_len = i;
        if ( number[0] == '-' && number[1] == '1')
            exit(0);

        scanf("%d",&n);
        // this is to flush stdin extra /n
        c = getchar();


        i = 0;
        while ( n--) {
            j = 0;
            while ( ( c = getchar() ) != '\n') {
                words[i][j ++ ] = c;
            }
            words[i][j] = '\0';
            i ++;
        }

        master_begin_index = 0;
        master_end_index = number_len ;
        output_buffer_index = 0;

        for ( i = 0 ; words[i][0] != '\0' ; i ++)  {
            is_candidate = 1;
            pivot = master_begin_index;
            for ( j = 0 ; words[i][j] != '\0' ; j ++ ) {
                if ( map_alphabet[ words[i][j] - 97] !=  number[pivot] - 48 || pivot >= master_end_index) {
                    is_candidate = 0;
                    pivot = master_begin_index;
                    break;
                }
                else {
                    pivot ++;
                }
            }
            if (is_candidate) {
                master_begin_index = pivot;
                if ( output_buffer_index != 0)
                    output_buffer[output_buffer_index ++] = ' ';
                for ( j = 0; words[i][j] != '\0'; j ++ ) {
                    output_buffer[output_buffer_index ++] = words[i][j];
                }
            }


        }
        if ( pivot == master_end_index ) {
            for ( i = 0 ; i < output_buffer_index; i++ )
                putchar(output_buffer[i]);
            putchar('\n');
        }
        else
            printf("No solution.\n");
    }

    return 0;
}
```

Problem solved. Was using a greedy solution which omitted some of the possibilities.

Edited by author 26.03.2018 11:18

Here is my code and here is my output. Everything should work! What's wrong ? What requirements have I not fulfilled?
http://lpaste.net/1392484352197132288
7325189087
5
it
your
reality
real
our
reality our
4294967296
5
it
your
reality
real
our
No solution.
-1

The code is written in pure C. The compiler is gcc

example = {'i': 1, 'j': 1, 'a': 2, 'b': 2, 'c': 2,
           'd': 3, 'e': 3, 'f': 3, 'g': 4, 'h': 4,
           'k': 5, 'l': 5, 'm': 6, 'n': 6, 'p': 7,
           'r': 7, 's': 7, 't': 8, 'u': 8, 'v': 8,
           'w': 9, 'x': 9, 'y': 9, 'o': 0, 'q': 0, 'z': 0}


def create_words(number, amount):
    words = {}

    for i in range(int(amount)):

        word = str(input())
        key = ""

        key = "".join([str(example.get(j)) for j in word])

        if key in str(number):
            words[key] = word

    return words


def create_answers(number, words):
    answers = {}

    for i in words.keys():

        if i != number[:len(i)]:
            continue

        answer = [words[i]]
        answer_key = i

        copy = number[len("".join(answer)):]
        x = len(copy)
        while x > 0:
            if copy[:x] in words.keys():
                answer.append(words[copy[:x]])
                answer_key += copy[:x]
                copy = copy[x:]
                x = len(copy) + 1
            x -= 1

        if len(answer) == 0:
            continue
        elif len(answer) in answers.keys():
            continue
        elif answer_key == n:
            answers[len(answer)] = answer
        else:
            continue

    return  answers

while True:
    n = input()

    if int(n) == -1:
        break

    a = input()

    i = create_answers(n, create_words(n, a))

    if len(i) == 0:
        print("No solution.")
    else:
        y = min(i.keys())
        print(" ".join(i[y]))

Edited by author 09.12.2017 22:06

I was trying to write TRIE for mnemonic words and DFS that tree with phone number.
And I have failed.
After that,  I wrote just 2-D dimensional dynamic programming solution.  DP[i] [j]  is minimal number of words to memorize substring [i;j].  And I got success.  Used Python.  Just input,  not stdin from sys.

¿Any idea of why a code can pass all the tests except the test 6 ? I prove my code with this imput, and it works fine

7325189087
5
it
your
reality
real
our
4294967296
5
it
your
reality
real
our
213456
12
id
a
h
lm
aid
aidhlm
hl
m
dhlm
ai
aid
hlm
2017697240238123468420176972402381234684201769724023812346842017697240238123468420176972402381234684
7
azipmwpbgqadtjafhmth
azipmwpbgqadtjafhmth
azipmwpbgqadtjafhmth
azipmwpbgqadtjafhmth
azipmwpbgqadtja
azipmwpbgqadtjafhmthazipmwpbgqadtjafhmthazipmwpbgqadtjafhmthazipmwpbgqadtjafhmth
fhmth
27386428376
0
97854668689678768
3
dfgdfhjghjdggzash
dfgkjt
nkhhdfsge
11111111111
5
ij
jj
ji
j
i
1234567890
5
bdh
txo
bdhkmp
i
kmp
-1

http://ideone.com/KOHykO

Examples and my examples work.
ideome works

How to look at all stdin ???

Edited by author 28.07.2017 03:35

Edited by author 12.06.2017 20:33

Не понимаю где ошибка.
Занимаюсь в целом программированием 3 недели (как хобби)
Проверял на исходном примере и на примерах, которые нашел на форуме. Ответы верны. Сюда загружаю выдаёт ошибку.

example = {'i' : 1, 'j' : 1, 'a' : 2, 'b' : 2, 'c' : 2,
               'd' : 3, 'e' : 3, 'f' : 3, 'g' : 4, 'h' : 4,
               'k' : 5, 'l' : 5, 'm' : 6, 'n' : 6, 'p' : 7,
               'r' : 7, 's' : 7, 't' : 8, 'u' : 8, 'v' : 8,
               'w' : 9, 'x' : 9, 'y' : 9, 'o' : 0, 'q' : 0, 'z' : 0}

while True:
    number = input()
    if int(number) == -1:
        break

    num_words = int(input())
    words = {}
    k = 500

    for i in range(num_words):
        word = input()
        if len(word) < k:
            k = len(word)
        key_word = ""
        for a in word:
            key_word += str(example.get(a))
        words[int(key_word)] = word

    answer = []
    loser = ""

    while True:
        copy = number[len("".join(answer)):]
        x = len(copy)
        while x >= k:
            if int(copy[:x]) in words.keys():
                if words[int(copy[:x])] != loser:
                    answer.append(words[int(copy[:x])])
                    copy = copy[x:]
                    x = len(copy) + 1
            x -= 1
        if len(answer) == 0:
            break
        elif len("".join(answer)) != len(number):
            loser = answer.pop()
        elif len("".join(answer)) == len(number):
            break

    if len(answer) == 0:
        print("No solution.")
    else:
        ans = " ".join(answer)
        print(ans)

Please, help some critical test case

ps. I fix it )

Edited by author 04.02.2017 18:08

I'm not getting the bug in the code :(. It would be helpful if someone pointed the mistake.

key = {'i' : 1, 'j' : 1,
       'a' : 2, 'b' : 2, 'c' : 2,
       'd' : 3, 'e' : 3, 'f' : 3,
       'g' : 4, 'h' : 4,
       'k' : 5, 'l' : 5,
       'm' : 6, 'n' : 6,
       'p' : 7, 'r' : 7, 's' : 7,
       't' : 8, 'u' : 8, 'v' : 8,
       'w' : 9, 'x' : 9, 'y' : 9,
       'o' : 0, 'q' : 0, 'z' : 0
      }

while True:
    n = raw_input()
    if(int(n) == -1):
        break
    l = int(raw_input())
    d = {}
    ans = []

    for a0 in xrange(l):
        temp = raw_input()
        d["".join([str(key[i]) for i in temp])] = temp

    i = len(n)
    while(i>0):
        if n[0:i] in d.keys():
            ans.append(d[n[0:i]])
            n = n[i:]
            i = len(n)+1
        i-=1

    print "No solution." if len(n) != 0 else " ".join(ans)

Please somebody help me. I can not find the reason not to be accepted my code.

#include <iostream>
#include <string>
#include <vector>
using namespace std;
bool found;
string convert(string str)
{
    string char_list = "22233344115566070778889990";
    string to_digit;
    for(int i=0; i<str.length(); i++)
    {
        to_digit += char_list[str[i]-97];
    }
    return to_digit;
}
void dfs(vector<int> index[], vector<int> ends[], string diction[], vector<int> track, int i, int n)
{
    if(found == true)
    {
        return;
    }
    if(i == n){
        for(int j=0; j<track.size(); j++)
        {
            cout<<diction[track[j]]<<" ";
        }
        found = true;
        return;
    }
    for(int k=0; k<ends[i].size(); k++){
        track.push_back(index[i][k]);
        dfs(index, ends, diction, track, ends[i][k], n);
        track.pop_back();
    }
}
int main()
{
    for(; ;){
        found = false;
        string number;
        cin>>number;
        if(number == "-1"){
            break;
        }
        int dic_size;
        cin>>dic_size;
        string diction[dic_size];
        for(int i=0; i<dic_size; i++){
            cin>>diction[i];
        }
        int n = number.size();
        vector<int> ends[n];
        vector<int> index[n];
        for(int j=0; j<dic_size; j++)
        {
            string str = convert(diction[j]);
            int len = diction[j].size();
            for(int i=0; i<n; i++)
            {
                if(number.substr(i,len) == str){
                    ends[i].push_back(i+len);
                    index[i].push_back(j);
                }
            }
        }
        vector<int> track;
        dfs(index, ends, diction, track, 0, n);
        if(found == false){
            cout<<"No solution.";
        }
    }
    return 0;
}

Edited by author 03.01.2017 20:24

http://pastebin.com/af0DFBg0
Look at my code please.
If someone could say me what wrong, it would be great.
Thank you!