Državno natjecanje 2016. godine za 1. i 2. razred Srednje Škole - 1. zadatak - Dan 1

Soundex je algoritam kojim se imena u engleskom jeziku kodiraju s ciljem da imena koja slično zvuče (a različito se pišu) dobiju isti kod. Za potrebe ovog zadatka, ime je niz od dva ili više slova engleske abecede u kojem je prvo slovo uvijek veliko, a sva ostala slova su mala. Soundex kod je niz od točno četiri znaka — jednog velikog slova te tri znamenke — koji se dobiva od imena na sljedeći način:

1. Zapamtimo prvo slovo imena.

2. Uklonimo iz imena sva slova “w” i “h” osim eventualnog prvog slova imena.

3. Ostale suglasnike engleskog jezika (uključujući i prvo slovo ako je suglasnik) zamijenimo znamenkama prema sljedećim pravilima:

• b, f, p, v → 1

• c, g, j, k, q, s, x, z → 2

• d, t → 3

• l → 4

• m, n → 5

• r → 6

1. U svakoj grupi susjednih jednakih znamenaka obrišemo sve osim prve znamenke.

2. Izbrišemo sva pojavljivanja slova “a”, “e”, “i”, “o”, “u”, “y” osim eventualnog prvog slova imena.

3. Ako je prvi znak znamenka onda je zamijenimo s originalnim prvim slovom zapamćenim u prvom koraku.

4. Dokle god niz ima manje od četiri znaka dodajemo znamenku “0” na kraj. Ukoliko niz ima više od četiri znaka, obrišemo sve znakove osim prva četiri.

Ako, na primjer, računamo soundex kod za ime “Schmidt”, nakon koraka 2. dobijemo niz “Scmidt”, nakon koraka 3. niz “225i33”, nakon koraka 4. niz “25i3”, nakon koraka 5. niz “253”, nakon koraka 6. niz “S53”, te nakon koraka 7. imamo izračunat soundex kod “S530”.

Zadan je niz imena, za svako ime odredi njegov soundex kod.

ULAZNI PODACI

U prvom redu nalazi se prirodni broj n (n ≤ 10) – broj zadanih imena. U k-tom od sljedećih n redova nalazi se k-to ime. Svako ime je niz od najmanje 2 i najviše 20 slova engleske abecede. Prvo slovo imena je uvijek veliko dok su sva ostala mala.

IZLAZNI PODACI

U k-ti red ispišite soundex kod k-tog imena.

PRIMJERI TEST PODATAKA

ulaz

5
Schmidt
Robert
Rupert
Rrupert
Ashcraft

izlaz

S530
R163
R163
R163
A261

ulaz

6
Smith
Smythe
Washington
Lee
Tymczak
Gutierrez

izlaz

S530
S530
W252
L000
T522
G362