LQDOJ Contest #5 - Bài 3 - Trò Chơi Số Hai - LQDOJ: Le Quy Don Online Judge

LQDOJ Contest #5 - Bài 3 - Trò Chơi Số Hai

Tác giả:

Dạng bài

Điểm: 1300 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

shiba quyết định chơi một trò chơi có độ khó cao. Trong trò chơi, có tất cả \(n\) cửa, cửa thứ \(i\) nếu thắng sẽ được thưởng một lượng điểm đúng bằng \(i\), ngược lại nếu thua sẽ bị trừ một lượng điểm đúng bằng \(i\). Trò chơi được thiết kế bởi _minhduc, mà cậu ấy bị ám ảnh với các số \(2\) nên các cửa là luỹ thừa của \(2\) thì sẽ được giảm độ khó.

Do kĩ năng chơi không quả hay của mình, shiba chỉ có thể thắng được các cửa được giảm độ khó. Hỏi số điểm shiba nhận được sau khi chơi đủ \(n\) trò chơi là bao nhiêu?

Input

Dòng thứ nhất chứa một số nguyên dương \(T\) (\(T \le 10^3\)) - số lượng bộ test.
\(T\) dòng tiếp theo, mỗi dòng chứa một số nguyên dương \(n\) (\(n \le 10^8\)).

Output

Gồm \(T\) dòng, mỗi dòng là một số nguyên là kết quả của bộ test đó.

Scoring

Subtask \(1\) (\(30\%\) số điểm): \(n \le 10^3\).
Subtask \(2\) (\(70\%\) số điểm): không có ràng buộc gì thêm.

Example

Test 1

Input

2
1
4

Output

1
4

Bình luận

1
SleanaVP 10:09 p.m. 16 Tháng 11, 2024
include<bits/stdc++.h>

define lli long long int

using namespace std;

int t;

void check(int n) {
int k = 0;
while ((1 << (k + 1)) <= n) {
k++;
}

lli sumpositive = (1LL << (k + 1)) - 1; lli sumnegative = (lli)n * (n + 1) / 2 - sumpositive; cout << sumpositive - sumnegative << "\n"; return;

}

int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);

cin >> t; while (t--) { int n; cin >> n; check(n); } return 0;

}

1 bình luận nữa