Pe o tablă de şah cu n linii şi n coloane se află firimituri de pâine şi o furnică. Pentru fiecare pătrăţel, inclusiv cel în care se găseşte furnica, aflat pe linia i şi coloana j, cantitatea de firimituri de pâine este egală cu restul împărţirii lui i+j la 6. Astfel pentru n=4 tabla de şah conţine următoarele cantităţi de firimituri:

Furnica (notată cu F în figură) se poate deplasa din pătrăţelul unde se găseşte în toate cele opt pătrăţele vecine, numerotate ca mai jos:

Furnica se deplasează, pornind din pătrăţica aflată în colţul din stânga sus, în una dintre pătrăţelele vecine, şi aşa mai departe. Pe drumul său furnica se hrăneşte cu toată cantitatea de firimituri din pătrăţelele prin care a trecut (după ce iese din pătrăţică catitatea de firimituri devine 0). Drumul furnicii este dat printr-un şir de k numere naturale (cuprinse între 1 şi 8) care precizează, la fiecare pas, următorul pătrăţel din drum.

Cerința

Scrieţi un program care pentru un drum dat determină cantitatea totală de firimituri mâncată de furnică, precum şi numărul pătrăţelelor prin care aceasta a trecut de cele mai multe ori.

Date de intrare

Fişierul de intrare furnica.in conţine pe prima linie numerele n şi k, separate între ele printr-un spaţiu, iar pe linia următoare k numere naturale (1, 2, 3, 4, 5, 6, 7 sau 8) separate prin câte un spaţiu, reprezentând următorul pătrăţel din drum pentru un pătrăţel curent.

Date de ieșire

Fişierul de ieşire furnica.out va conţine, pe prima linie, cantitatea totală şi numărul pătrăţelelor din cerinţă separate printr-un spaţiu.

Restricții și precizări

• 1 < n < 101
• 0 < k < 201
• Drumul furnicii nu iese din tablou.

Exemplu

furnica.in

4 10
3 6 5 3 2 6 3 6 2 3

furnica.out

23 2

Explicație

Drumul furnicii trece prin pătrăţelele (linie, coloană) următoare:
(1,1)->(1,2)->(2,1)->(3,1)->(3,2)->(2,3)->(3,2)->(3,3)->(4,2)->(3,3)->(3,4).
Pe drum se mănâncă următoarea cantitate de firimituri: 2+3+3+4+5+5+0+0+0+0+1=23
Prin pătrăţelele de coordonate (3,2) şi (3,3) se trece de cele mai multe ori (de două ori).

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

ifstream cin ("furnica.in");
ofstream cout ("furnica.out");

int a[101][101] , di[10] , dj[10] , b[101][101] , n , s , k , val;

int main()
{
    cin >> n;
    di[1] = -1; di[2] = -1; di[3]= 0; di[4] = 1; di[5] = 1; di[6] = 1; di[7] = 0; di[8] = -1;
    dj[1] = 0; dj[2] = 1; dj[3] = 1; dj[4] = 1; dj[5] = 0; dj[6] = -1; dj[7] = -1; dj[8] = -1;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            a[i][j] = (i + j) % 6;
    s = a[1][1];
    b[1][1]++;
    cin >> k;
    int i = 1, j = 1;
    for (int ll = 0; ll < k; ll++)
    {
        cin >> val;
        i += di[val];
        j += dj[val];
        s += a[i][j];
        a[i][j] = 0;
        b[i][j]++;
    }
    cout << s << " ";
    int max = 0, sol = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
        {
            if(b[i][j] > max)
            {
                max = b[i][j];
                sol = 1;
            }
            else if(b[i][j] == max) sol++;
        }
    cout << sol;
    return 0;
}