- Nosaukums
- Tastatūra (tasta)
- Laika limits
- 1.00s
- Atmiņas limits
- 64.0 MB
- Grūtība
-
32%
Definīcija
Mazajam gudriniekam Pēterim jāuzraksta sacerējums. Viņš jau sacerēja visu tekstu, atlika tikai to uzrakstīt datorā. Tiesa, teksts ir pagarš, tāpēc Pēteris grib patērēt pēc iespējas mazāk laika, pārrakstot sacerējumu.
Pētera tastatūra ir N × M taustiņus liela. Vienkāršības labad visi iespējamie simboli ir doti ar skaitļiem no 1 līdz N · M. Katru no šiem simboliem var uzdrukāt ar tieši vienu taustiņu. Tastatūras rindiņas ir sanumurētas no 1 līdz N no augšas uz leju, un kolonnas no 1 līdz M no kreisās puses uz labo. Tāpēc katra taustiņa vietu var aprakstīt ar koordinātēm (i, j), kur i ir rindiņas numurs, bet j ir kolonnas numurs.
Pēteris drukā ar tikai diviem rādītājpirkstiem (šausmas!). Sākumā tie atrodas rūtiņās ar koordinātēm (N, 1) un (N, M). Pēteris drukā visus simbolus secīgi, un nekustina divas rokas vienlaicīgi (viņam tiešām jāiemācās drukāt normāli!). Vienā sekundē viņš var pabīdīt vienu no pirkstiem uz kādu no taustiņiem ar kopīgu malu. Lai uzspiestu taustiņu, netiek patērēts laiks. Abi pirksti vienlaicīgi var atrasties vienā rūtiņā. Kāds ir mazākais iespējamais laiks sekundēs, lai Pēteris varētu uzrakstīt sacerējumu uz datora?
Ievaddatu raksturojums
Pirmā rinda satur divus veselus skaitļus N un M, tastatūras izmērus (2 ≤ N, M ≤ 10). Nākamās N rindas katra satur M skaitļus, kārtējās tastatūras rindas aprakstu. Garantēts, ka tastatūra satur katru no skaitļiem no 1 līdz N · M tieši vienu reizi.
Nākamā rinda satur skaitli K, teksta garumu (1 ≤ K ≤ 105). Pēdējā rinda satur K skaitļus a1, ..., aK, sacerējuma tekstu (1 ≤ ai ≤ N · M).
Izvaddatu raksturojums
Izvadiet vienu skaitli, mazāko laiku sekundēs, kas vajadzīgs Pēterim, lai pilnībā pārrakstītu doto tekstu datorā!
Piezīmes
Apakšuzdevuma apraksts | Punktu skaits |
K ≤ 20 | 20 |
K ≤ 2000 | 50 |
Bez papildus ierobežojumiem | 30 |
Kopā: | 100 |
Paraugdati
Stdin
3 4 2 10 4 7 6 1 8 11 5 12 9 3 6 5 4 12 2 1 7
Stdout
10
Uzdevums tiek aizsargāts ar autortiesībām un tā kopēšana vai neatļauta izmantošana ir aizliegta.