| # | Bài tập | Điểm | Thời gian: | Giới hạn bộ nhớ |
|---|---|---|---|---|
| 1 | JOI 2007 - Building | 100 (p) | 5.0s | 256M |
| 2 | JOI 2007 - Fermat | 100 (p) | 5.0s | 256M |
| 3 | JOI 2007 - Salt | 100 (p) | 5.0s | 256M |
Olympic Tin học Quốc tế sắp được tổ chức tại Nhật Bản. Để chào đón các thí sinh từ khắp nơi trên thế giới, ban tổ chức muốn trang trí các tòa nhà cao tầng dọc đường từ sân bay đến nơi lưu trú.
Nhà thiết kế yêu cầu các tòa nhà được chọn phải có chiều cao tăng nghiêm ngặt theo hướng từ sân bay đến nơi lưu trú. Nghĩa là nếu chiều cao của các tòa nhà được chọn, theo thứ tự từ gần sân bay đến xa sân bay, là \(h_1,h_2,h_3,\ldots\), thì phải có \(h_1<h_2<h_3<\ldots\).
Để khung cảnh rực rỡ nhất, ban tổ chức muốn chọn nhiều tòa nhà nhất có thể. Cho chiều cao của tất cả các tòa nhà theo thứ tự dọc đường, hãy tính số lượng tòa nhà lớn nhất có thể chọn.
Giới hạn thời gian là \(1\) giây cho mỗi bộ dữ liệu; giới hạn bộ nhớ là \(64\) MB.
Đọc từ đầu vào chuẩn:
Ghi ra đầu ra chuẩn một số nguyên là số tòa nhà lớn nhất có thể chọn để trang trí.
Có \(5\) bộ dữ liệu được chấm độc lập, tổng cộng \(100\) điểm. Không có điều kiện phân nhóm bổ sung được công bố.
Ví dụ 1
9
3
7
5
9
8
10
10
11
95Chiều cao của chín tòa nhà, theo hướng từ sân bay đến nơi lưu trú, là \(3,7,5,9,8,10,10,11,9\). Có thể chọn năm tòa nhà ở các vị trí \(1,3,5,6,8\), có chiều cao lần lượt là \(3,5,8,10,11\).
| Vị trí từ sân bay | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|
| Chiều cao | 3 | 7 | 5 | 9 | 8 | 10 | 10 | 11 | 9 |
Các chiều cao in đậm ứng với các tòa nhà được chọn. Số tòa nhà lớn nhất có thể chọn là \(5\).
Cho số nguyên tố \(p\) và số nguyên dương \(n\). Hãy đếm số bộ ba số nguyên có thứ tự \((x,y,z)\) thỏa mãn \(0 \le x,y,z \le p-1\) và
Ở đây, \(a \equiv b \pmod p\) nghĩa là \(a-b\) chia hết cho \(p\). Gọi số bộ ba cần tìm là \(m\).
Giới hạn thời gian là \(0{,}5\) giây cho mỗi bộ dữ liệu; giới hạn bộ nhớ là \(64\) MB.
Đọc từ đầu vào chuẩn:
Ghi ra đầu ra chuẩn một dòng chỉ chứa số nguyên \(m\).
Có \(5\) bộ dữ liệu được chấm độc lập, tổng cộng \(100\) điểm. Không có điều kiện phân nhóm bổ sung được công bố.
Ví dụ 1
3
59Có chín bộ ba thỏa mãn \(x^5+y^5 \equiv z^5 \pmod 3\):
\((0,0,0)\), \((0,1,1)\), \((0,2,2)\), \((1,0,1)\), \((1,1,2)\), \((1,2,0)\), \((2,0,2)\), \((2,1,0)\), \((2,2,1)\).
Ví dụ 2
19
21487Có \(487\) bộ ba \((x,y,z)\) với \(0 \le x,y,z \le 18\) thỏa mãn \(x^{21}+y^{21} \equiv z^{21} \pmod {19}\).
Gói này dùng giao diện C++17 sau thay cho chương trình đọc tệp salt.in:
#include "saltc.h"
void solve(int n, const int *u, const int *v);
Không định nghĩa main. Bộ chấm C++ đọc cây từ đầu vào chuẩn rồi gọi solve.
Hai mảng u, v có n-1 phần tử, chỉ số từ 0, mô tả các cạnh ban đầu.
Dùng hàm turn với quy ước bên dưới và trở về ngay khi nhận (0,0).
Không đọc đầu vào hoặc ghi đầu ra chuẩn trong lời giải.
Thư viện và đối thủ lịch sử không còn trong tài liệu được phát hành. Đối thủ
cục bộ dùng thuật toán giả ngẫu nhiên với hạt giống cố định; đây là bản thay thế
để kiểm tra luật chơi và API, không tái tạo đối thủ hoặc điểm số lịch sử.
Phần dưới giữ nguyên mô tả lịch sử; giao diện cục bộ ở trên được ưu tiên khi nộp bài.
SALT TREE XV là trò chơi dành cho hai người. Ban đầu, hai người được cho một cây. Họ luân phiên xóa một cạnh hoặc một đỉnh còn tồn tại. Khi xóa một cạnh, chỉ cạnh đó biến mất. Khi xóa một đỉnh, đỉnh đó cùng tất cả các cạnh đang nối với nó đều biến mất. Người xóa đỉnh cuối cùng là người thắng.
Có thể chứng minh rằng người đi trước luôn có chiến lược thắng, bất kể người đi sau chơi như thế nào. Hãy viết chương trình đóng vai người đi trước và luôn giành chiến thắng.
Cây là một đồ thị liên thông, không có chu trình và có ít nhất một đỉnh. Một đỉnh đứng riêng cũng là cây; một đồ thị có chu trình hoặc không liên thông thì không phải cây. Trong quá trình chơi, đồ thị còn lại không nhất thiết liên thông.
Đây là bài tương tác qua thư viện. Giới hạn thời gian là \(3\) giây cho mỗi bộ dữ liệu; giới hạn bộ nhớ là \(64\) MB.
Chương trình đọc cây ban đầu từ tệp salt.in:
Mỗi cạnh xuất hiện đúng một lần. Thứ tự liệt kê các cạnh không có ý nghĩa.
Với C/C++, chương trình phải khai báo:
#include "saltc.h"
Thư viện cung cấp hàm:
void turn(int u, int v, int* ru, int* rv);
ru và rv phải là hai con trỏ hợp lệ, trỏ đến hai vùng nhớ khác nhau.*ru và *rv mô tả nước đi của đối thủ theo cùng quy ước: hai giá trị bằng nhau biểu thị xóa một đỉnh; giá trị thứ nhất nhỏ hơn giá trị thứ hai biểu thị xóa một cạnh. Luôn có *ru <= *rv.*ru = *rv = 0. Khi đó, chương trình phải kết thúc ngay, không gọi thêm bất kỳ hàm API nào.Chương trình không được xuất bất kỳ dữ liệu nào. Hai chương trình dùng đầu vào và đầu ra chuẩn để liên lạc thông qua thư viện; chương trình của bạn không được tự đọc đầu vào chuẩn hoặc ghi đầu ra chuẩn vì điều đó có thể làm hỏng giao tiếp.
Có \(5\) bộ dữ liệu, tổng cộng \(100\) điểm. Không có điều kiện phân nhóm bổ sung được công bố. Với mỗi bộ dữ liệu, chương trình chơi một số ván và chỉ nhận điểm nếu thắng tất cả các ván. Nếu có một ván mà chương trình đưa ra nước đi không hợp lệ, thua, hoặc kết thúc trước khi thắng, chương trình nhận \(0\) điểm cho bộ dữ liệu đó.
Tệp salt.in chứa cây sau:
Ví dụ 1
7
3 4
5 7
4 6
2 4
1 4
1 7Cây ban đầu có dạng:
2
|
3-4-1-7-5
|
6
Sau đây là các nước đi đầu tiên trong một ván chơi minh họa:
| Lượt | Nước đi | Biểu diễn qua API |
|---|---|---|
| Bạn | Xóa cạnh \((5,7)\) | Truyền u = 5, v = 7 cho turn |
| Đối thủ | Xóa đỉnh \(4\) | Lời gọi trên nhận về *ru = 4, *rv = 4 |
| Bạn | Xóa đỉnh \(3\) | Truyền u = 3, v = 3 cho lời gọi turn tiếp theo |
Ngay sau khi bạn xóa cạnh \((5,7)\), đỉnh \(5\) vẫn còn nhưng đứng riêng:
2
|
3-4-1-7 5
|
6
Sau khi đối thủ xóa đỉnh \(4\), các cạnh \((2,4)\), \((3,4)\), \((4,6)\) và \((1,4)\) cũng biến mất:
2
3 1-7 5
6
Sau khi bạn xóa đỉnh \(3\), trạng thái trở thành:
2
1-7 5
6
Các hình trên chỉ minh họa một phần ván chơi, chưa mô tả một ván kết thúc.