ZIGZAG.cpp

#include<iostream>
using namespace std;

typedef unsigned long long ull;
const ull MAX = 300005;

ull N, K;
ull remember;
char Str[MAX];  // Lưu xâu đầu vào

/*
* Lấy ra số nhỏ nhất của một đường chéo thứ i
* Đường chéo thứ i là đường chéo có tổng chỉ số hàng và cột
* của mỗi ô là bằng i.
* @PARAM : i : chỉ số của đường chéo
* RETURN : giá trị số nhỏ nhất của đường chéo đó.
*/
ull GetMinDiagon(ull i)
{
	if(i < N) return (1 + (i*(i+1))/2);
	return (((3*N - i)*(i - N + 1))/2 + remember);
}

ull GetValue(ull row, ull col)
{
	// Tỉnh tổng chỉ số hàng và cột để suy ra chỉ số đường chéo
	ull sum = row + col;
	// Tính số nhỏ nhất của đường chéo đó.
	ull min_diagon = GetMinDiagon(sum);

	// chỉ số đường chéo là chẵn
	if(sum%2 == 0 && sum < N)
	{
		return min_diagon + col;
	}
	else if(sum%2 == 0 && sum >= N)
	{
		ull col_start = sum - (N-1);
		return min_diagon + (col - col_start);
	}
	// Chỉ số đường chéo là lẻ
	else if(sum%2 == 1 && sum < N)
	{
		return min_diagon + (sum - col);
	}
	else if(sum%2 == 1 && sum >= N)
	{
		return min_diagon + (N-1) - col;
	}
}

int main()
{
	freopen("input.txt","r",stdin);
	ios::sync_with_stdio(false);

	cin >> N >> K >> Str;
	remember = GetMinDiagon(N-1);

	// Khởi tạo vị trí ban đầu là [0][0] và tổng là 1
	ull row = 0, col = 0;
	ull sum = 1;

	// Duyệt từng kí tự để xác định cách nhảy của thỏ
	for(int i = 0; i < K; i++)
	{
		if(Str[i] == 'U') row -= 1;
		else if(Str[i] == 'D') row += 1;
		else if(Str[i] == 'R') col += 1;
		else if(Str[i] == 'L') col -= 1;

		// Cộng dồn các ô mà thỏ nhảy tới.
		sum += GetValue(row, col);
	}

	// In kết quả
	cout << sum << endl;

	return 0;
}