Problemi 131

Kërkesa

Një lojë luhet në një tabelë drejtkëndore me N rreshta dhe M shtylla. Fillimisht kutitë e tabelës janë të pangjyrosura. Lojtari fillon ti ngjyrosë një nga një, dhe për çdo kuti që ngjyros merr aq pikë sa fqinjë të ngjyrosur ka kjo kuti (fqinjët e një kutie janë ato kuti që kanë një brinjë të përbashkët me të). Shuma e këtyre pikëve janë pikët që fitohen nga kjo lojë. Bëni një program që gjen se sa janë pikët maksimale që mund të fitohen në këtë lojë.

Referenca: https://www.codechef.com/problems/OMWG

Shembull

$ cat input.txt
1
2 2

$ python3 prog.py < input.txt
4

Në një tabelë me 2 rreshta dhe 2 shtylla, numri maksimal i pikëve që mund të fitohen është 4.

Zgjidhja

for _ in range(int(input())):
    n, m = map(int, input().split())
    print(2*n*m - n - m)

Sqarime

Sido që të ngjyrosen katrorët, në fund do kemi fituar një pikë për çdo brinjë që ndodhet midis dy katrorëve. Kështu që numri total i pikëve është gjithmonë i barabartë me numrin e këtyre brinjëve që ndodhen midis dy katrorëve.

Në një tabelë me përmasa NxM kemi NM katrorë të vegjël, të cilët gjithsej kanë 4NM brinjë. Po të heqim brinjët anësore, që nuk ndodhen midis dy katrorëve, na ngelen 4NM - 2(N + M) brinjë. Këto janë brinjët e brendshme, por të numëruara 2 herë, njëherë për llogari të njërit katror dhe njëherë për llogari të katrorit ngjitur me të. Kështu që numri i brinjëve të brendshme (që është edhe numri i pikëve) është: 2NM - N - M