Algorithm

Problem Name: 2 AD-HOC - beecrowd | 1652

Deli Deli

Local Contest, University of Ulm Germany

Timelimit: 1

Mrs. Deli is running the delicatessen store "Deli Deli". Last year Mrs. Deli has decided to expand her business and build up an online store. She has hired a programmer who has implemented the online store.

Recently some of her new online customers complained about the electronic bills. The programmer had forgotten to use the plural form in case that an item is purchased multiple times. Unfortunaly the programmer of Mrs. Deli is on holiday and now it is your task to implement this feature for Mrs. Deli. Here is a description how to make the plural form:

1. If the word is in the list of irregular words replace it with the given plural.
2. Else if the word ends in a consonant followed by "y", replace "y" with "ies".
3. Else if the word ends in "o", "s", "ch", "sh" or "x", append "es" to the word.
4. Else append "s" to the word.

Input

The first line of the input file consists of two integers L and N (0 ≤ L ≤ 20, 1 ≤ N ≤ 100). The following L lines contain the description of the irregular words and their plural form. Each line consists of two words separated by a space character, where the first word is the singular, the second word the plural form of some irregular word. After the list of irregular words, the following N lines contain one word each, which you have to make plural. You may assume that each word consists of at most 20 lowercase letters from the english alphabet ('a' to 'z').

Output

Print N lines of output, where the ith line is the plural form of the ith input word.

 Sample Input Sample Output 3 7 rice rice spaghetti spaghetti octopus octopi rice lobster spaghetti strawberry octopus peach turkey rice lobsters spaghetti strawberries octopi peaches turkeys

Code Examples

#1 Code Example with C Programming

```Code - C Programming```

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

#define true 1
#define false 0

typedef struct noArv{

char string[50];
char string_p[50];
struct noArv *left;
struct noArv *right;

} tree_t;

tree_t * push(tree_t *, char *, char *);
tree_t * search(tree_t *, char *);
void plural(char *);
_Bool check(char *, const int);

int main (int argc, char **argv)
{

tree_t *t = NULL;
unsigned i, l, n;
char palavra[30], plural_p[20];

scanf("%u %u", &l, &n);
for (i = 0; i  <  l; ++i)
{

scanf("%s %s", palavra, plural_p);
t = push(t, palavra, plural_p);

}

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

scanf("%s", palavra);
tree_t *tmp = search(t, palavra);
if (tmp)
printf("%s\n", tmp->string_p);
else
plural(palavra);

}

return 0;

}

tree_t * push(tree_t *tree, char *s1, char *s2)
{

if (!tree)
{

tree = (tree_t *) malloc(sizeof(tree_t));
tree->left = tree->right = NULL;
strcpy(tree->string, s1);
strcpy(tree->string_p, s2);

}
else if (strcmp(tree->string, s1)  <  0)
tree->left = push(tree->left, s1, s2);
else if (strcmp(tree->string, s1) > 0)
tree->right = push(tree->right, s1, s2);

return tree;

}

tree_t * search(tree_t *tree, char *s1)
{

if (!tree)
return NULL;

if (strcmp(tree->string, s1) == 0)
return tree;

if (strcmp(tree->string, s1)  <  0)
return search(tree->left, s1);
else if (strcmp(tree->string, s1) > 0)
return search(tree->right, s1);

}

void plural(char *s1)
{

int pos = strlen(s1);
if (s1[pos - 2] != 'a' && s1[pos - 2] != 'e' && s1[pos - 2] != 'i' && s1[pos - 2] != 'o' && s1[pos - 2] != 'u' && s1[pos - 1] == 'y')
s1[pos - 1] = 0, strcat(s1, "ies");
else if (check(s1, pos))
strcat(s1, "es");
else
strcat(s1, "s");

printf("%s\n", s1);

}

_Bool check(char *s1, const int size)
{

if (s1[size - 1] == 'o')
return true;

if (s1[size - 1] == 's')
return true;

if (s1[size - 1] == 'x')
return true;

if (s1[size - 2] == 'c' && s1[size - 1] == 'h')
return true;

if (s1[size - 2] == 's' && s1[size - 1] == 'h')
return true;

return false;

}
``````
Copy The Code &

Input

cmd
3 7
rice rice
spaghetti spaghetti
octopus octopi
rice
lobster
spaghetti
strawberry
octopus
peach
turkey

#2 Code Example with C++ Programming

```Code - C++ Programming```

``````
#include<bits/stdc++.h>
using namespace std;

int main(){
string s,s1;
int n,k;
cin >> n >> k;
map  <  string , string > ans;
while(n--){
cin >> s >> s1;
ans.insert(pair  <  string , string > (s,s1));
}
while(k--){
cin >> s;
s1 = s;
if(ans.count(s) != 0)
cout << ans.find(s)->second << endl;
else{
if(s[s.size()-1] == 'y' and (s[s.size()-2] != 'a' and s[s.size()-2] != 'e' and s[s.size()-2] != 'i' and s[s.size()-2] != 'o' and  s[s.size()-2] != 'u'))
s[s.size()-1] = 'i',s +="es";
else if(s[s.size()-1] == 'o' or (s[s.size()-1] == 's') or (s[s.size()-2] == 'c' and (s[s.size()-1] == 'h')) or (s[s.size()-2] == 's' and s[s.size()-1] == 'h') or (s[s.size()-1] == 'x'))
s += "es";
else
s += "s";
cout << s << endl;
ans.insert(pair < string,string>(s1,s));
}
}
return 0;
}
``````
Copy The Code &

Input

cmd
3 7
rice rice
spaghetti spaghetti
octopus octopi
rice
lobster
spaghetti
strawberry
octopus
peach
turkey

Output

cmd
rice
lobsters
spaghetti
strawberries
octopi
peaches
turkeys