Giả sử chúng ta có một số n. Xét n số tự nhiên đầu tiên. Chúng ta phải chia chúng thành hai tập A và B sao cho mỗi phần tử thuộc đúng một tập và hiệu tuyệt đối giữa tổng các phần tử trong A và tổng các phần tử trong B là nhỏ nhất, và tìm hiệu đó.
Ví dụ, nếu đầu vào là n = 5, thì đầu ra sẽ là 1, vì nếu ta làm A = {1, 3, 4} và B = {2, 5}, thì các giá trị tổng là 8 và 7, nên hiệu là 1.
Các bước
Để giải quyết bài toán này, chúng ta sẽ làm theo các bước sau:
return (n * (n + 1) / 2) mod 2
Ví dụ
Xem triển khai sau để hiểu rõ hơn:
#include <bits/stdc++.h> using namespace std; int solve(int n) { return (n * (n + 1) / 2) % 2; } int main() { int n = 5; cout << solve(n) << endl; }Đầu vào
5
Đầu ra
1