Türkçe

Çözüm

Bir dikdörtgenin kenarlarından birinin uzunluğu çift sayı olduğu sürece beyaz kareleriyle siyah karelerinin sayısı eşit olacaktır. Fakat kenarlar uzunlukları tek sayıysa eğer sol üst köşesindeki 1x1 lik kare beyazsa beyaz sayısı 1 fazla, siyahsa siyah sayısı 1 fazla olan bir dikdörtgen olacaktır. Bu dikdörtgenlerin beyazı fazla olanların sol üst köşeleri ve sağ alt köşeleri beyaz siyahı fazla olanların siyah olmak zorundadır. Soruyu çözerken bu bilgiden yararlanacağız.

Soruyu ilk olarak kolaylaştırıp 1xM lik bir düzlem için çözelim. Bu durumda satır içindeki kareler [Beyaz,Siyah,Beyaz...] şeklinde ilerlemekte (veya çift sayılı bir satırı ölçüyorsak [Siyah,Beyaz,Siyah...]). Bu satırda toplamda (M+1)/2 adet beyaz kare bulunmakta (çift sayılı bir satırda M/2) bu sayıya C diyelim. Bu durumda elimizde:

• C adet 1x1
• C-1 adet 1x3
• ...
• ...

• 1 adet 1x(2*C-1) (M tek ise 1xM, M çift ise 1x(M-1) e denk gelmekte)

  Üstteki işlemle sadece bir satırda bulunan daha fazla beyaz kare içeren dikdörtgenleri bulduk. Şimdi 1 satır içinde seçtiğimiz 1xZ lik ROW1 adet dikdörgenin (Z, M den küçük bir tek sayı) satırdaki yerlerini değiştirmeden toplamda kaç adet dikdörtgen bulabileceğimizi hesaplayacağız. (yani dikdörtgenin sol üst köşesinin koordinatı x1,y1 sağ alt köşesinin koordinatı x2,y2 ise x1 ve x2 yi sabit tutup y1 ve y2 yi değiştirerek (y1\(\leq\)y2)). Bunu da ilk adımda yaptığımız gibi a=(N+1)/2 (eğer sütun çift numaralıysa N/2) daha sonra gaussunu alarak a*(a+1)/2 ile hesaplayabilirsiniz.

Önemli Bilgi

• Bir NxM lik bir satranç tahtasında ya tek sayılı satır ve sütun ya da çift sayılı satır ve sütun olmak üzerek iki adet beyaz fazla olan dikdörtgen oluşturabilirsiniz. Bu yüzden bu 2 duruma da dikkat edilmesi gerekiyor

English

Solution

If one of the rectangle's edge lengths is an even number, it will contain an equal number of white and black squares. Suppose the edge lengths are odd numbers, if the color of the top left 1x1 square is white, the number of white squares will be greater and if it is black, the number of black squares will be greater. The top left and bottom right 1x1 squares of rectangles that have more white squares than black squares have to be white. We will use that information in our solution.

Let's first make the problem easier and solve it for a 1xM grid. In this case, the squares of the row go like [white, black, white...] -or [black, white, black...] in an even indexed row-. There are (M+1)/2 white squares in this row (or M/2 if M is even). Let's call this number C. We have:

• C times 1x1
• C-1 times 1x3
• ...
• ...
• 1 1x(2*C-1) (will be equal to 1xM if M is odd, 1x(M-1) if M is even)-

We add these up and find (1+2+...+C)=C*(C+1)/2. Let's call this one ROW1.

We have found the number of rectangles that contain more white squares in 1 row. Now, we will calculate how many rectangles we can find without moving the 1xZ rectangles (Z is an odd integer less than M) we have found for one row. In other words, if the rectangle's top-left corner's coordinates are (x1,y1), and the bottom-right corner's coordinates are (x2,y2); we will change x2 and y2 without altering x1 and y1. And we will do this similar to the first step. First, we calculate a=(N+1)/2 (N/2 if it is an even indexed column) and then add them up a*(a+1)/2.

Important Point

• In an NxM chess board, you can form 2 rectangles with more white squares by either selecting an even indexed row and column or selecting an odd indexed row and column. Thus these 2 cases must be taken into account.

Code

#include <bits/stdc++.h>
#define ll long long

using namespace std;

int n, m;



ll gauss(ll x){
        // English: This function calculates how many ways we can select 2 points from the given vector (could be the same point / order is important)
        // Turkish: Bu fonksiyon verilen vektörden kaç şekilde 2 nokta seçebileceğimizi hesaplıyor(aynı nokta olabilir / sıra önemli)
    return x*(x+1)/2;
}

int main(){
    cin>>n>>m;
    ll a,b,c,d;

        // English: a is number of 1x1 white squares inside an odd numbered column 
             // and b is number of 1x1 white squares inside an even numbered column 
        // Turkish: a, tek sayılı bir sütunda kaç adet 1x1 lik beyaz kare olduğunu hesaplıyor
            //    b, çift sayılı bir sütunda kaç adet 1x1 lik beyaz kare olduğunu hesaplıyor
    a=(n+1)/2;
    b=n/2;

    c=(m+1)/2;
    d=m/2;
        // English: c is number of 1x1 white squares inside an odd numbered row
             // and b is number of 1x1 white squares inside an even numbered row
        // Turkish: a, tek sayılı bir satırda kaç adet 1x1 lik beyaz kare olduğunu hesaplıyor
             //   b, çift sayılı bir satırda kaç adet 1x1 lik beyaz kare olduğunu hesaplıyor

    cout<< gauss(a) * gauss(c) + gauss(b) * gauss(d) <<endl; 

}