Contest giao lưu Tin học trẻ 2024 - Lần thứ Ba (Bảng B2)

Cho số nguyên dương \(n\) \((n \le 10^{18})\). Tính tổng \(1 - 2 + 3 - 4 + 5 - 6 + \cdots \pm n\).

Input

• Một dòng gồm số nguyên dương \(n\).

Output

• Một dòng là kết quả của bài toán.

Scoring

• Có \(50\%\) số điểm ứng với \(n \le 10^6\).
• Có \(50\%\) số điểm còn lại ứng với \(n \le 10^{18}\).

Example

5

3

6

-3

Một bộ đèn pha lê đẹp mắt đang được bày bán trên TikTok. Anh N (chủ nhân của giải thưởng 40 triệu đồng) đang dự tính mua nó để trang trí cho nhà hàng của mình.

Bộ đèn gồm \(a\) bóng đèn màu xanh và \(b\) bóng đèn màu đỏ. Giá của mỗi bóng đèn màu xanh là \(x\) và mỗi bóng đèn màu đỏ là \(y\). Để đổi một bóng đèn bất kì từ xanh sang đỏ hoặc ngược lại thì anh ta phải trả thêm \(c\) đồng cho chủ shop. N được dùng thao tác đổi bóng đèn vô số lần, hãy giúp anh ta tìm chi phí tối thiểu để mua được bộ đèn đó.

Input

• Dòng đầu tiên chứa số nguyên dương \(T\) là số bộ dữ liệu
• Tiếp theo gồm \(T\) dòng, tương ứng với \(T\) bộ dữ liệu. Mỗi dòng chứa các số nguyên dương \(a, b, x, y, c\).

Output

• Gồm một số nguyên duy nhất là số tiền tối thiểu cần để mua bộ đèn.

Scoring

• \(T \le 100\) với mọi testcase.
• Gọi \(n = a + b\):
  • Subtask \(1\) (\(50\%\) số điểm): \(n, x, y, c \le 10^3\).
  • Subtask \(2\) (\(50\%\) số điểm): \(n, x, y, c \le 10^5\).

Example

3
2 1 1 1 1
3 2 10 100 1
0 5 10 1 1

3
52
5

Ông Sắc là một doanh nhân đại tài, ông đã xây dựng nên sự nghiệp của ông từ con số 1. Trong một khóa dạy kinh doanh, ông đã đưa ra bài toán cho những học trò của mình dựa trên trải nghiệm của mình:

Dãy \(a\) ban đầu chỉ có duy nhất phần tử \(1\). Chọn dãy con từ dãy \(a\) và chèn vào dãy \(a\) tổng của các phần tử trong dãy con ấy. Nói cách khác chọn \(k\) chỉ số khác nhau \(i_1, i_2, ..., i_k\) và chèn vào dãy a một giá trị \(a_{i_1} + a_{i_2} + ... + a_{i_k}\).

Cho trước một dãy \(b\). Hỏi từ dãy \(a\) có tạo được nên dãy \(b\) không?

Input

• Dòng đầu tiên chứa \(t\) là số lượng bộ dữ liệu khác nhau \((1 \le t \le 20)\).
• \(t\) nhóm sau, mỗi số gồm \(2\) dòng:
  • Dòng đầu chứa số nguyên dương \(n\) (\(n \le 10^5\));
  • Dòng tiếp theo chứa \(n\) số \(b_1, b_2, ..., b_n\) (\(b_i \le 2 * 10^5\)).

Output

• In ra \(\text{YES}\) nếu đúng yêu cầu đề bài, ngược lại in ra \(\text{NO}\).

Scoring

• Subtask 1: \(50\%\) số test tương ứng với \(50\%\) số điểm có \(n \le 10^3\), \(b_i \le 10^3\).
• Subtask 2: \(50\%\) số test tương ứng với \(50\%\) số điểm không có ràng buộc gì thêm.

5
1
1
4
1 1 1 1
3
2 4 6
4
1 5 3 1
5
1 3 1 1 5

YES
YES
NO
NO
YES

Ông Liêm là 1 kẻ trộm bò lừng lẫy, khét tiếng lúc bấy giờ khiến các chủ trang trại nghe tên là hoảng sợ. Ông Hai là 1 chủ trang trại bò lớn tại làng Hòn. Bỗng một ngày nghe tin ông Liêm đã tới làng của mình, ông Hai bèn nghĩ ra cách để đối phó với tên trộm đặc biệt này. Các chuồng bò của ông Hai được đánh số từ \(1\) đến \(n\), có \(m\) công tắc nối giữa \(2\) chuồng. Ban đầu các chuồng bò đều đóng cửa. Nếu ai tác động vào công tắc của một chuồng bất kì thì tất cả các chuồng nối với nó đều thay đổi trạng thái cánh cửa (đóng thành mở, mở thành đóng). Ông Liêm là 1 kẻ trộm tham lam, ông muốn một khi đã trộm thì phải trộm cho hết, do đó ông Liêm nhờ bạn tìm số công tắc tối thiểu cần tác động để mở được tất cả các chuồng bò của ông Hai.
Yêu cầu: Hãy tìm số tác động ít nhất để các cách cửa chuồng bò đều mở? Giả thiết là luôn có phương án để mở tất cả các chuồng bò.

Input

• Dòng 1 chứa 2 số nguyên dương \(n\) và \(m\) (\(1 \le n \le 40\), \(1 \le m \le \frac{n(n-1)}{2}\));
• \(m\) dòng sau, mỗi dòng ghi 1 cặp số \(a\) và \(b\) tương ứng có một công tắc nối giữa hai chuồng \(a\) và \(b\). Các dây điện nối với công tắc là dây điện hai chiều. Dữ liệu đầu vào được đảm bảo rằng mỗi cặp chuồng \((a, b)\) có duy nhất một công tắc nối giữa chúng.

Output

• Một số duy nhất là số lần tác động ít nhất.

Scoring

• Subtask 1: \(30\%\) số test tương ứng với \(30\%\) số điểm có \(n \le 22\);
• Subtask 2: \(70\%\) số test tương ứng với \(70\%\) số điểm không có ràng buộc gì thêm

5 6 
1 2 
1 3 
4 2 
3 4 
2 5
5 3

3