There is no checker in this problem. In my solution I
1. Print new line after query even if there is no strings which satisfy it
2. Don't print new line after last query

input:
2
b 1
a 1

2
a
b

output:
a
[empty]
b

hope can help you!
GOOD LUCK!

I set the length of my array to 15 then got WA at #14 while I set16 then I got AC

My code doesn't leave empty line after the last query. What can be the cause of WA2? Seeing many people also got WA2 :((

Edited by author 21.04.2017 07:33

Edited by author 21.04.2017 07:33

Can someone help me? Please?
I do it with Python3 ,and does not print out empty line after last queue
here's my code:

def getSecond(temp):
                return temp[1]

if __name__ == '__main__':
    while True:
        try:

            N = int(input())
            Words = []
            for n in range(N):
                Words.append(input().split())
                Words[n][1] = int(Words[n][1])

            M = int(input())
            Beginners = []
            for m in range(M):
                Beginners.append(input())

            for mm in range(M):
                start = list(Beginners[mm])
                matchs = []
                for nn in range(N):
                    word = list(Words[nn][0])
                    flag = True
                    for s in range(len(start)):
                        if start[s] != word[s]:
                            flag = False
                            break
                    if(flag):
                        matchs.append(Words[nn])
                if matchs != []:
                    matchs.sort()
                    matchs.sort(key = getSecond, reverse = True)
                    count = 0
                    for match in matchs:
                        if count > 10:
                            break
                        print(match[0])
                        count += 1

                if mm != M-1:
                    print()


        except:
            break

So, when user starts looking for words, my program immediately writes the answer. Maybe that's why it isn't correct. For example:
user -> 2
user -> ab
program -> abc
user -> xz
program -> xzy

WA On TEST#3 .. any help plz ???

Edited by author 11.09.2018 15:53

Edited by author 11.09.2018 15:53

If you've got WA #11 then your program deals bad with repeatative queries.

Try this test:
--------------------
2
acm 10000
acmicpc 10000
2
ac
ac
---------------------
Correct answer is:
---------------------
acm
acmicpc

acm
acmicpc
---------------------

Написал лобовой вариант и всё равно WA10! Значит, вывод не верен. Кто может подсказать, как выводить ответ?(Форум не помог)

#define _CRT_SECURE_NO_WARNINGS
#define mk make_pair

#include <string>
#include <map>
#include <iostream>
using namespace std;

typedef map <string, int> mymap;

const int nmax = 100005;

mymap t[4 * nmax];
mymap answer[nmax];
string word[nmax];
int cnt[nmax];
int n, m;
string w_print[11];
int c_print[11];

mymap Search(int L, int R);
int BinaryDown(int L, int R, string s);
int BinaryUp(int L, int R, string s);
mymap Optimal(mymap map1, mymap map2);
void Print(mymap M);
void QSort_W(int L, int R);
void QSort2(int L, int R);
void QSort3(int L, int R);

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> word[i] >> cnt[i];
    QSort_W(1, n);
    cin >> m;
    for (int i = 1; i <= m; i++)
    {
        string s;
        cin >> s;
        int L, R;
        L = BinaryDown(1, n, s);
        R = BinaryUp(1, n, s);
        answer[i].clear();
        if (L != -1 && R != -1) answer[i] = Search(L, R);
    }

    for (int i = 1; i <= m; i++)
    {
        Print(answer[i]);
        if(i!=m) cout<<endl;
        if(!(answer[i].empty()) && i!=m) cout<<endl;
    }

    return 0;
}

mymap Search(int L, int R)
{
    mymap res;
    res.clear();
    for(int i=L;i<=R;i++)
    {
        mymap x;
        x.insert(mk(word[i],cnt[i]));
        res=Optimal(res,x);
    }
    return res;
}

void Print(mymap M)
{
    int n = 0;
    for (mymap::iterator it = M.begin(); it != M.end(); it++)
    {
        w_print[++n] = it->first;
        c_print[n] = it->second;
    }
    if (n == 0) return;
    QSort2(1, n);
    for (int i = 1; i <= n;)
    {
        int j = i + 1;
        while (j <= n && c_print[j] == c_print[i]) j++;
        QSort3(i, j - 1);
        i = j;
    }
    for (int i = 1; i<n; i++) cout << w_print[i] << endl;
    cout << w_print[n];
}

void QSort2(int L, int R)
{
    int i, j;
    int X = c_print[(L + R) / 2];
    i = L, j = R;
    while (i <= j)
    {
        while (c_print[i] > X) i++;
        while (c_print[j] < X) j--;
        if (i <= j)
        {
            string Y = w_print[i]; w_print[i] = w_print[j]; w_print[j] = Y;
            int k = c_print[i]; c_print[i] = c_print[j]; c_print[j] = k;
            i++;
            j--;
        }
    }
    if (L < j) QSort2(L, j);
    if (i < R) QSort2(i, R);
}

void QSort3(int L, int R)
{
    int i, j;
    string X = w_print[(L + R) / 2];
    i = L, j = R;
    while (i <= j)
    {
        while (w_print[i] < X) i++;
        while (w_print[j] > X) j--;
        if (i <= j)
        {
            string Y = w_print[i]; w_print[i] = w_print[j]; w_print[j] = Y;
            int k = c_print[i]; c_print[i] = c_print[j]; c_print[j] = k;
            i++;
            j--;
        }
    }
    if (L < j) QSort3(L, j);
    if (i < R) QSort3(i, R);
}


void QSort_W(int L, int R)
{
    int i, j;
    string X = word[(L + R) / 2];
    i = L, j = R;
    while (i <= j)
    {
        while (word[i] < X) i++;
        while (word[j] > X) j--;
        if (i <= j)
        {
            string Y = word[i]; word[i] = word[j]; word[j] = Y;
            int k = cnt[i]; cnt[i] = cnt[j]; cnt[j] = k;
            i++;
            j--;
        }
    }
    if (L < j) QSort_W(L, j);
    if (i < R) QSort_W(i, R);
}

int BinaryDown(int L, int R, string s)
{
    for(int i=L;i<=R;i++) if(s==word[i].substr(0, s.length())) return i;
    return -1;
}

int BinaryUp(int L, int R, string s)
{
    for(int i=R;i>=L;i--) if(s==word[i].substr(0, s.length())) return i;
    return -1;
}


mymap Optimal(mymap map1, mymap map2)
{
    mymap res;
    res.clear();
    if (map1.size() + map2.size() <= 10)
    {
        res = map1;
        for (mymap::iterator it = map2.begin(); it != map2.end(); it++) res.insert(mk(it->first,it->second));
        return res;
    }
    else
    {
        res = map1;
        for (mymap::iterator it = map2.begin(); it != map2.end(); it++)
        {
            if (res.size() < 10) res.insert(mk(it->first, it->second));
            else
            {
                if (res.begin()->second < it->second)
                {
                    res.erase(res.begin());
                    res.insert(mk(it->first, it->second));
                }
            }
        }
        return res;
    }
}

don't print endline symbol after last query:

for(int i=0;i<queries;i++){
answer_the_query();
if(i!=queries-1) printf("\n") //without this line it got wa#1!
}

Edited by author 15.09.2010 08:42

Can anyone help with this?
I do not print at the end of an empty string. all the tests of the discussions my program passes.

/*
My program got WA on test 11!!!
What's wrong with my code?
Anyone can help me!!!
*/
#include <map>
#include <set>
#include <ctime>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <string>
#include <cstdlib>
#include <cstring>
#include <utility>
#include <iostream>
#include <algorithm>

#define FI            first
#define SE            second
#define LSON(x)            (x<<1)
#define RSON(x)            ((x<<1)|1)
#define Benefit(x,y)        x=max(x,y)
#define CS            const static
#define SORT_CMP(s,l,r,cmp)    sort(s+(l),s+(r)+1,cmp)
#define SORT(s,l,r)        sort(s+(l),s+(r)+1)
#define MP(x,y)            make_pair(x,y)
#define Randomize        srand( (unsigned int) time ( NULL ) )
#define INOUT(x,y)        freopen(x,"r",stdin),freopen(y,"w",stdout)

using namespace std;

typedef char name[20];

CS int MaxN = 100010 ;

struct word
{
    name x;
    int val,len;
    word()    {x[0] = 0; val = 0;}
};

struct Trie
{
    Trie * next[26];
    word * ans[10];
    Trie()
    {
        for(int i=0;i<26;i++)    next[i] = NULL ;
        for(int i=0;i<10;i++)    ans[i] = NULL ;
    }
} * Tree;

word p[MaxN];

name ask;

int n,m,asklen;

void Insert(Trie * x,int _y,int pos)
{
    int i;    word & y = p[_y];
    for(i=0;i<10;i++)
        if((x->ans[i]==NULL)||(x->ans[i]->val<y.val))    break;
    if(i<10)
    {
        for(int j=9;j>i;j--)
            x -> ans[j] = x->ans[j-1];
        x -> ans[i] = p + _y;
    }
    if(pos!=y.len)
    {
        int u = y.x[pos] - 'a';
        if(!x->next[u])    x -> next[u] = new Trie ;
        Insert(x->next[u],_y,pos+1);
    }
}

void Init()
{
    scanf("%d\n",&n);    Tree = new Trie ;
    for(int i=1;i<=n;i++)
    {
        scanf("%s %d\n",p[i].x,&p[i].val);    p[i].len=strlen(p[i].x);
        Insert(Tree,i,0);
    }
}

void Query(Trie * x,int pos)
{
    if(pos == asklen)
    {
        for(int i=0;i<10;i++)
            if(x->ans[i])    printf("%s\n",x->ans[i]->x);
            else        break;
        return ;
    }
    int u = ask[pos] - 'a';
    if(x->next[u])    Query(x->next[u],pos+1);
}

void Solve()
{
    scanf("%d\n",&m);
    while(m--)
    {
        scanf("%s\n",ask);    asklen = strlen(ask) ;
        Query(Tree,0);    if(m)    printf("\n");
    }
}

int main()
{
    Init();    Solve();
    return 0;
}

Edited by author 31.05.2012 14:40

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

namespace _1542
{
    public class word
    {
        public  string line;
        public  int count;
        public  word(string g="", int f=0)
        {
            line=g;
            count =f;
        }
    }
    class sortim: IComparer<object >
    {
        public int Compare(object x, object y)
        {
            word a, b;
            a = (word)x;
            b = (word)y;
            if (a.count < b.count) return 1;
            else if (a.count > b.count) return -1;
            else return String.Compare(a.line, b.line);

        }
    }
    class Program
    {
        static void Main(string[] args)
        {
            sortim sort = new sortim();
            int n = Convert.ToInt32(Console.ReadLine());
            word[] wor = new word[n];
            for (int i = 0; i < n; i++)
            {
                string[] temp = Console.ReadLine().Split(' ');
                wor[i] = new word(temp[0], Convert.ToInt32(temp[1]));
            }
            int g= Convert.ToInt32(Console.ReadLine());

            for (int i = 0; i < g; i++)
            {
                string request = Console.ReadLine();
                word[] select = Array.FindAll(wor, e => e.line.Substring(0,request.Length)==request );
                Array.Sort(select, sort);
                for (int i1 = 0; i1 < Math.Min(select.Length,10); i1++)
                {
                    Console.WriteLine(select[i1].line);
                }
                if (i!=g-1) Console.WriteLine();
            }
        }
    }
}

why??

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<climits>
#include<string>
#include<string.h>
#include<vector>
#define sf scanf
#define pf printf
#define cls(a) memset(a,0,sizeof(a))
#define _cls(a) memset(a,-1,sizeof(a))

using namespace std;

struct Edge_t{
    int to,next;
}edge[400000];
int hed[200000];
int et;


struct tree{
    tree *br[26];
    vector<int>vec;
    tree(){
        for(int i=0;i<26;++i) br[i]=NULL;
        vec.clear();
    }
};

struct Input{
    char str[18];
    int val;
}inp[100010];
tree *head;

inline void adde(int u,int v){
    edge[et].to=v,edge[et].next=hed[u],hed[u]=et++;
}

inline void addtree(char *st,int index){
    int id,i;
    tree *s=head;
    for(i=0;st[i];++i){
        id=st[i]-'a';
        if(!s->br[id])
            s->br[id]=new tree;
        s=s->br[id];
    }
    s->vec.push_back(index);
}
inline bool cmp(int a,int b){
    if(inp[a].val==inp[b].val) return strcmp(inp[a].str,inp[b].str)<0;
    return inp[a].val>inp[b].val;
}

void DEL(tree *s){
    int i;
    for(i=0;i<26;++i)
        if(s->br[i]) DEL(s->br[i]);
    s->vec.clear();
    delete(s);
}
int res[1000010];


void deal(char *st,int index){
    int i,id,j;
    tree *s=head;
    for(i=0;st[i];++i){
        id=st[i]-'a';
        if(!s->br[id]) return;
        s=s->br[id];
        for(j=0;j<s->vec.size();++j)
            adde(s->vec[j],index);
    }
}

int main(){
    int i,j;
    int n,m,sk;
    char str[18];
    while(scanf("%d",&n)!=EOF){
        head=new tree;
        _cls(hed);
        for(i=et=0;i<n;++i)
            sf("%s%d",inp[i].str,&inp[i].val);
        sf("%d",&m);
        for(j=0;j<m;++j){
            sf("%s",str);
            addtree(str,j);
        }
        for(i=0;i<n;++i)
            deal(inp[i].str,i);
        int e;
        for(i=0;i<m;++i){
            if(i) puts("");
            for(sk=0,e=hed[i];e!=-1;e=edge[e].next)
                res[sk++]=edge[e].to;
            if(!sk) continue;
            sort(res,res+sk,cmp);
            //if(sk>0)
            for(j=0;j<sk && j<10;++j)
                pf("%s\n",inp[res[j]].str);
        }
        DEL(head);
    }
    return 0;
}

/*
2
ab 10
ac 20
1
f

*/

I can't pass test 9. Who can help me?

#include <cstdlib>
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

using namespace std;

bool compar1(pair<string, int> a, pair<string,int> b)
{
     if (a.second>b.second) return true;
     else return false;
}

int main(int argc, char *argv[])
{
    int n = 0;
    cin >> n;
    vector<pair<string, int> > v(n);
    for (int i = 0; i<n; i++) {
        string tmp;
        int num;
        cin >> tmp;
        cin >> num;
        v.push_back(make_pair(tmp, num));
    }
    sort(v.begin(), v.end(), compar1);
    int m = 0;
    cin >> m;
    for (int i = 0; i<m; i++) {
        string str;
        cin >> str;
        for (int j = 0; j<n; j++) {
            if (v[j].first.find(str)==0&&j<10) {
               cout << v[j].first << endl;
            }
        }
        if (i!=m-1) cout << endl;
    }
    system("PAUSE");
    return 0;
}

Be sure that you don't print empty line when it's the last query.

Edited by author 23.05.2012 01:02

1) What should be output when there are no words starting with input string? 2 successive empty lines in the output are weird, so I ask.

2) If input contains some word exactly as it is, should I place this word in the output? I.e. does the verb "start" allow equality as well?

My old prob got AC before rejudge, but MLE 21 now, I tried to make it better but failed. Any hint?