maya

Time limit: 0.1s Memory limit: 4MB Input: maya.in Output: maya.out


Regina stupului este plecată, iar cele NN albinuțe nou născute trebuie hrănite. Maya este albina care trebuie să îndeplinească această sarcină. Maya își face un plan pentru a putea acționa. Pentru fiecare albinuță, Maya pornește dintr-o celulă inițială ce conține cantitatea de miere necesară și se deplasează din celulă în celulă, până la albinuța pe care o va hrăni.

Un fagure este format din coloane numerotate cu litere mari ale alfabetului englez de la AA la ZZ, iar poziția fiecărei celule de pe o coloană este identificată prin valori 11, 22, 33, 44, 55, \dots de jos în sus, ca în figură. Fiecare celulă a fagurelui are formă hexagonală. Dintr-o celulă se poate ajunge în cele 66 celule vecine, prin deplasarea în direcțiile: 1 - sus, 2 - dreapta sus, 3 - dreapta jos, etc. (ca în figura alăturată).


Fagurele este circular, astfel după coloana ZZ urmează, spre dreapta, coloana AA, iar înainte de coloana AA se află, la stânga, coloana ZZ.

Cerință

Știind care sunt adresele celulelor din care va pleca Maya, se cere:

  1. Să se afișeze coloanele care conțin cele mai multe celule inițiale.
  2. Cunoscând, în plus, secvențele de mutări pe care le va executa Maya, pentru a ajunge la fiecare albinuță, se cer adresele celor NN celule destinație.

Date de intrare

Fișierul de intrare maya.in conține pe prima linie numărul natural CC (11 sau 22) reprezentând cerința problemei. Pe linia următoare va fi numărul natural NN reprezentând numărul de celule inițiale. Pe următoarea linie vor fi NN adrese separate prin câte un spațiu, o adresă fiind de forma ColoanăNumăr.

Pentru cerința 22, vor mai exista, în continuare, NN linii conținând fiecare: un număr natural reprezentând numărul de mișcări, urmat, după un spațiu, de o secvență de cifre 11, 22, 33, 44, 55 sau 66 (fără spații între ele) reprezentând direcțiile în care se va deplasa Maya pentru a ajunge la celula destinație.

Date de ieșire

Fişierul de ieşire maya.out:

  • dacă cerința este 11, va conţine o secvență de litere mari, în ordine alfabetică, separate prin câte un spațiu, reprezentând coloanele care conțin un număr maxim de celule inițiale;
  • dacă cerința este 22, va conţine NN linii formate din adrese de forma ColoanăNumăr reprezentând celulele destinație.

Restricții și precizări

  • 1N1 0001 \leq N \leq 1 \ 000;
  • Fiecare secvență de mutări este formată din cel mult 200200 de cifre;
  • În teste nu vor exista deplasări în direcția 44 pentru celulele aflate pe primele poziții din fiecare coloană (A1\text{A1}, B1\text{B1}, C1\text{C1}, \dots, Z1\text{Z1}) și nici în direcțiile 33 și 55 pentru fiecare dintre coloanele: B1\text{B1}, D1\text{D1}, F1\text{F1}, H1\text{H1}, \dots
  • Pe fiecare verticală, coloanele pot conține cel mult 5 0005 \ 000 de celule.

Exemplul 1

maya.in

1
5
D2 A3 A7 E2 D101

maya.out

A D

Explicație

Coloana AA conține două celule inițiale, coloana DD tot două, iar coloana EE una singură. Coloanele cu cele mai multe celule inițiale sunt AA și DD.

Exemplul 2

maya.in

2
5
D2 A3 A7 E2 D101 3 123
7 1111111
6 121212
4 1156
7 4444441

maya.out

F3
A10
D12
C4
D96

Explicație

Pentru celula inițială D2\text{D2}, drumul albinei este: D2 D3 E3 F3.

Log in or sign up to be able to send submissions!