Mảnh đất trồng cây (mdtrongcay.*)

Được vua cha cho một miếng đất phía tây thành phố, Po quyết định lấy một phần đất hình vuông có kích thước \(n \times n\) để làm vườn trồng cây, phần đất này được Po chia thành \(n\) dòng và \(n\) cột, các dòng được đánh số thứ tự từ 1 đến \(n\) từ trên xuống dưới, các cột được đánh số thứ tự từ 1 đến \(n\) từ trái qua phải, ô ở dòng \(i\) cột \(j\) được gọi là ô \((i,j)\). Trên mỗi ô, Po trồng một loại cây khác nhau, các loại cây được đánh số hiệu từ 1 đến \(n^{2}\);

Po trồng cây vào các ô theo quy luật như sau:

- Đầu tiên, Po chia vườn thành 4 phần đều nhau, mỗi phần có \(\frac{n^{2}}{4}\) ô:

+ Phần 1 gồm các ô ở phía trên bên trái, chọn các loại cây có số hiệu nhỏ nhất để trồng;

+ Phần 2 gồm các ô ở phía trên bên phải, chọn các loại cây có số hiệu nhỏ nhất chưa trồng ở Phần 1 để trồng;

+ Phần 3 gồm các ô ở phía dưới bên phải, chọn các loại cây có số hiệu nhỏ nhất chưa trồng ở Phần 1 và Phần 2 để trồng;

+ Phần 4 gồm các ô ở phía dưới bên trái, chọn các cây có số hiệu lớn nhất để trồng;

- Tiếp theo, với mỗi phần, Po tiếp tục chia nhỏ thành 4 phần và chọn loại cây trồng theo quy luật như trên cho đến khi mỗi phần có kích thước \(1 \times 1\) thì thực hiện trồng cây.

Ví dụ với \(n = 4\), loại cây trồng ở mỗi ô như hình:

Sau một thời gian mưa thuận gió hòa, cây trồng phát triển tươi tốt. Vua cha biết tin rất vui mừng nên vi hành đến thăm Po đồng thời đưa ra hai loại câu hỏi:

• Loại 1: Hãy cho biết loại cây \(c\) được trồng ở ô nào?

• Loại 2: Hãy cho biết ô \((x,y)\) đang trồng loại cây gì?

Yêu cầu: Hãy giúp Po trả lời các câu hỏi của vua cha.

Dữ liệu vào:

- Dòng đầu tiên ghi số nguyên dương \(n\ (2 \leq n \leq 10^{9})\);

- Dòng thứ 2 ghi số nguyên dương \(q\ (q \leq 10^{5})\) cho biết số lượng câu hỏi của vua cha;

- \(q\) dòng tiếp theo, mỗi dòng ghi 2 hoặc 3 số nguyên dương có dạng:

1 \(c\): tương ứng với câu hỏi loại 1 \((c \leq n^{2})\); hoặc

2 \(x\ y\): tương ứng với câu hỏi loại 2 \((1 \leq x,y \leq n)\).

Dữ liệu vào luôn đảm bảo tồn tại cách trồng cây thỏa yêu cầu đề bài.

Kết quả:

- In ra \(q\) dòng tương ứng với câu trả lời của \(q\) câu hỏi theo đúng thứ tự trong Dữ liệu vào.

Ví dụ:

Ràng buộc:

- Subtask 1 (10% số điểm): \(n = 2\);

- Subtask 2 (20% số điểm): \(n \leq 8\);

- Subtask 3 (30% số điểm): \(n \leq 1000\) và \(q \leq 10\);

- Subtask 4 (15% số điểm): chỉ có câu hỏi loại 1;

- Subtask 5 (15% số điểm): chỉ có câu hỏi loại 2;

- Subtask 6 (10% số điểm): không có ràng buộc gì thêm.

Bạn cần Đăng nhập để nộp bài

Chia phần (chiaphan_kh.*)

Nam và Việt cùng hợp tác thực hiện một dự án kinh doanh. Khi dự án kết thúc, tài sản còn lại gồm \(n\) vật dụng, vật dụng thứ \(i\ (i = 1,2,\ldots,n)\) có giá trị là \(c_{i}\).

Hai người cần chia các vật dụng thành hai phần để sở hữu riêng sao cho tổng giá trị của hai phần bằng nhau. Do mỗi vật dụng là nguyên khối và không thể tách nhỏ, nên không phải lúc nào cũng có thể sử dụng toàn bộ vật dụng để thực hiện cách phân chia này.

Sau khi chia các vật dụng thành hai phần có tổng giá trị bằng nhau và lớn nhất. Các vật dụng còn lại (nếu có) được bán cho đại lý để nhận phiếu mua hàng có giá trị bằng hai lần tổng giá trị của chúng. Giá trị phiếu mua hàng được chia đều và cộng vào tổng tài sản của mỗi người.

Yêu cầu: Cho giá trị của \(n\) vật dụng ban đầu, hãy xác định tổng giá trị cuối cùng mỗi người nhận được.

Dữ liệu vào:

- Dòng đầu tiên ghi số nguyên dương \(n\ (n \leq 500)\) là số lượng vật dụng;

- \(n\) dòng tiếp theo, mỗi dòng ghi một số nguyên dương \(c_{i}\ (c_{i} \leq 10^{5})\) là giá trị của vật dụng thứ \(i\).

Dữ liệu vào bảo đảm \(\sum_{i = 1}^{n}c_{i} \leq 10^{5}\).

Kết quả:

- Một số nguyên duy nhất là tổng giá trị mà mỗi người nhận được.

Ví dụ:

Ràng buộc:

- Subtask 1 (50% số điểm): \(n \leq 13\);

- Subtask 2 (30% số điểm): \(n \leq 50;\) tổng giá trị vật dụng không vượt quá 1000;

- Subtask 3 (20% số điểm): Không ràng buộc gì thêm.

Bạn cần Đăng nhập để nộp bài

Phần mềm thu ngân

Hoàng sinh viên năm 2 ngành Kỹ sư Công nghệ thông tin là một trong những ngành đang được ưa chuộng nhất hiện nay chuyên ngành kỹ thuật phần mềm trường Đại Học Bách Khoa. Hè đến rồi, để củng cố các kiến thức mà mình đã học. Hoàng quyết định sẽ đi làm thêm giúp đỡ bố mẹ, công việc mà Hoàng chọn là lập trình phần mềm Thu ngân cho một quán café gần nhà. Để hoàn thiện được các chức năng của phần mềm Hoàng dạo phố trải nghiệm hoạt động của một quán café truyền thống với công việc kế toán, trong đó có 4 thao tác:

• \(I\ K\): Thêm một nhân viên mới với mức lương ban đầu là \(K\).

• \(A\ K\): Tăng lương tất cả nhân viên trong quán lên \(K\) đơn vị.

• \(S\ K\): Giảm lương tất cả nhân viên trong quán xuống \(K\) đơn vị.

• \(F\ k\): Tìm và in ra lương của nhân viên có lương cao thứ \(k\) trong toàn bộ nhân viên của quán.

Ngoài ra, có các điều kiện cho các thao tác:

• Số lượng thao tác \(I\) và \(F\) không vượt quá \(10^{5}\).

• Số lượng thao tác A và S không vượt quá 100.

• Thao tác A và S có điều kiện thỏa mãn: \(K \leq 1000.\)

• Thao tác I có điều kiện thỏa mãn: \(K \leq 10^{5}.\)

• Thao tác F có điều kiện thỏa mãn: \(k \leq 10^{5}.\)

Tuy nhiên, chúng ta đều biết con người làm việc để duy trì sự sống, và với mức lương quá thấp, họ sẽ không thể tiếp tục làm. Trong quán café này cũng vậy. Bất cứ nhân viên nào có số lương thấp hơn \(X\) sẽ đi tìm những công việc khác do đãi ngộ tốt hơn.

Qua thực tế Hoàng đã nắm được các công việc mà mình cần hoàn thiện phần mềm. Hãy cho biết với mỗi thao tác \(F\) , đáp án sẽ là bao nhiêu. Ngoài ra, Hoàng cần tính số lượng nhân viên nghỉ việc sau toàn bộ thao tác.

Yêu cầu: Với mỗi thao tác \(F\ k\), in ra đáp án cần tìm. Nếu số lượng nhân viên ít hơn 𝑘, in ra -1. Cho biết số lượng nhân viên nghỉ việc sau toàn bộ thao tác.

Dữ liệu vào:

+ Dòng đầu tiên chứa số nguyên dương \(N\) và \(X\ (1 \leq N,X \leq 10^{5})\) là số lượng thao tác và mức lương tối thiểu nhân viên chấp nhận làm việc.

+ \(N\) dòng tiếp theo, mỗi dòng gồm một thao tác như đã được miêu tả ở trên.

Kết quả:

Với mỗi thao tác \(F\), in ra đáp án là một dòng tương ứng.

Dòng cuối cùng là số lượng nhân viên nghỉ việc sau toàn bộ thao tác.

Ví dụ:

Giải thích:

Sau 2 thao tác đầu, có 2 nhân viên hưởng 60 và 70 lương. Thao tác 3 giảm lương nhân viên 10 và 20. Nhân viên có mức lương cao thứ 2 bây giờ là 10. Sau tất cả các thao tác, có tổng cộng 2 nhân viên nghỉ việc.

Ràng buộc:

Subtask 1: Có 30% số test thỏa mãn: \(N\ \leq \ 1000\).

Subtask 2: Có 20% số test thỏa mãn: Không có thao tác \(F\).

Subtask 3: Có 20% số test thỏa mãn: Không có thao tác \(A\) và \(S\).

Subtask 4: Có 30% số test thỏa mãn: Không có ràng buộc gì thêm.

Bạn cần Đăng nhập để nộp bài

Tổng phân số (tongphanso.*)

Cho hai phân số \(\frac{x_{1}}{y_{1}}\) và \(\frac{x_{2}}{y_{2}}\);

Yêu cầu: Hãy tính tổng hai phân số đã cho?

Dữ liệu vào:

- Một dòng ghi lần lượt 4 số nguyên dương \(x_{1},y_{1},x_{2},y_{2}\); \((x_{1},y_{1},x_{2},y_{2} \leq 10^{9})\).

Kết quả:

- Một dòng ghi lần lượt 2 số \(n,\ m\) cho biết \(n\) là tử số, \(m\) là mẫu số của kết quả \(\frac{x_{1}}{y_{1}} + \frac{x_{2}}{y_{2}}\) sau khi tối giản.

Ví dụ:

Bạn cần Đăng nhập để nộp bài

Số hạng thứ k (minxk.)

Dãy số nguyên dương \(A\) được định nghĩa như sau: \(a_{0} = 1\), \(a_{1} = 2\), \(a_{n} = a_{n - 1} + 3a_{n - 2}\).

Yêu cầu: Cho số nguyên dương \(k\), tìm số hạng thứ \(k\) của dãy \(A\).

Dữ liệu vào: Số nguyên dương \(k\) (\(0 \leq k \leq 55\))

Kết quả: ghi số hạng thứ \(k\) của dãy \(A\).

Ví dụ:

Bạn cần Đăng nhập để nộp bài

Dãy tăng liên tiếp (daytanglientiep.*)

Cho số nguyên dương \(n\) và dãy số nguyên dương \(a_{1},a_{2},\ldots,a_{n}\). Với mỗi thao tác bạn có thể chọn số \(a_{i}\) bất kì để tăng giá trị lên 1 đơn vị hoặc giảm giá trị xuống 1 đơn vị.

Yêu cầu: Hãy cho biết cần thực hiện ít nhất bao nhiêu thao tác để từ dãy số ban đầu tạo thành dãy mới sao cho các phần tử trong dãy mới thỏa mãn \(a_{i} - a_{i - 1} = 1\ (\forall i = 2\ldots n)\)?

Dữ liệu vào:

- Dòng đầu tiên ghi số nguyên dương \(n\ (2 \leq n \leq 2000)\);

- Dòng thứ hai ghi lần lượt các số nguyên \(a_{1},a_{2},\ldots,a_{n}\ ({0 < a}_{i} \leq 10^{9})\).

Kết quả:

- Ghi một số nguyên duy nhất cho biết kết quả bài toán.

Ví dụ:

Ràng buộc:

- Subtask 1 (50% số điểm): \(n = 2\);

- Subtask 2 (50% số điểm): không có ràng buộc gì thêm.

Bạn cần Đăng nhập để nộp bài

Cá sấu (casau.*)

Một trại nuôi cá sấu có một hồ nước hình vuông có kích thước cạnh là \(a\). Ở giữa hồ người ta chứa một đảo nhỏ hình chữ nhật có kích thước \(b \times c\) để cho cá sấu bò lên phơi nắng sao cho cái đảo nhỏ không chạm với bờ hồ.

Hãy cho biết diện tích của mặt nước sau khi xây đảo nhỏ?

Dữ liệu vào:

+ Một dòng ghi lần lượt ba số nguyên \(a,\ b,\ c\ (0 < a,b,c \leq 10000,b < a,c < a)\)

Kết quả:

+ Ghi một số nguyên cho biết kết quả bài toán

Ví dụ:

Bạn cần Đăng nhập để nộp bài

Phát quà (phatqua2.*)

Lập trình ngày nay đang là một môn học yêu thích của giới trẻ. Nam là tình nguyện viên dạy lập trình cho các em tại trung tâm ITCENTER, thấy các em học tập say mê và tràn đầy nhiệt huyết Nam quyết định tặng quà cho hai em học sinh chăm chỉ và có điểm số cao nhất lớp học hôm nay là Bình và An nhằm khuyến khích phong trào học tập trong lớp. Nam mang tới lớp học của Bình và An \(n\) gói quà đánh số từ 1 tới \(n\), gói quà thứ \(i\) có giá trị \(a_{i}\). Nam nói rằng trong hai em mỗi em được chọn đúng k món quà có chỉ số liên tiếp trong dãy \((k \leq \frac{n}{3})\) và không được cùng chọn bất cứ món quà nào.

Nghe vậy Bình xung phong chọn trước và An chọn sau. Vì bản tính hiếu thắng, Bình muốn An nhận được dãy quà có tổng giá trị nhỏ nhất có thể.

Yêu cầu: Tìm số \(x\) nhỏ nhất sao cho tồn tại phương án Bình chọn quà mà An không thể có cách chọn được tổng giá trị quà lớn hơn \(x\).

Dữ liệu vào:

Dòng 1: Chứa 2 số nguyên \(n,k\ (3 \leq n \leq 10^{6};1 \leq k \leq \frac{n}{3})\).

Dòng 2 chưa \(n\) số nguyên \(a_{1},a_{2},...,a_{n};(\forall i:1 \leq a_{i} \leq 10^{6}).\).

Kết quả: Ghi một số nguyên duy nhất là giá trị 𝑥 tìm được.

Ví dụ:

Giải thích: Bình chọn món quà thứ 4 và thứ 5, khi đó An chỉ có thể chọn quà với tổng giá trị tối đa bằng 7 (Chọn món quà thứ 9 và thứ 10).

Ràng buộc:

Subtask 1: Có 30% số điểm thỏa mãn \(3 \leq n \leq 50;a_{i} \leq 10^{5}.\)

Subtask 2: Có 30% số điểm thỏa mãn \(3 \leq n \leq 5000;a_{i} \leq 10^{5}.\)

Subtask 3: Có 40% số điểm không có ràng buộc gì thêm.

Bạn cần Đăng nhập để nộp bài

Giá trị lớn nhất của đồ thị (valg.*)

Cho đồ thị \(G\) có \(n\) đỉnh, các đỉnh được đánh số từ 1 đến \(n\). Ban đầu đồ thị không có cạnh nào. Cho một danh sách \(X\) gồm \(m\) cạnh, cạnh \(\left( u_{i},\ v_{i} \right)\ \forall\ i \in \lbrack 1,m\rbrack\) nối đỉnh \(u_{i}\) với \(v_{i}\). Bạn hãy chọn các cạnh trong danh sách \(X\) để thêm vào đồ thị \(G\) theo một thứ tự nhất định sao cho sao cho giá trị của đồ thị là lớn nhất. Giá trị của đồ thị được tính theo quy tắc:

1. Gọi giá trị của đồ thị \(G\) là \(valG\), lúc đầu chưa có cạnh nào được đưa vào đồ thị thì \(valG = 0\)

2. Khi thêm một cạnh \((u,v)\) vào đồ thị thì số lượng đỉnh đến được từ \(u\) và số lượng đỉnh đến được từ \(v\) trong đồ thị được cộng vào \(valG\). Một đỉnh \(x\) được gọi là đến được từ đỉnh \(y\) nếu có đường đi từ \(x\) đến \(y\).

Ví dụ: cho đồ thị có \(n = 5\) và danh sách \(X\ \)có \(m = 4\) cạnh \((1,\ 2);(3,\ 4);(4,5);(5,3)\ \)

• Nếu thêm lần lượt các cạnh theo đúng thứ tự trong danh sách \(X\) thì giá trị của đồ thị:

Đồ thị ban đầu		\[valG = 0\]
Thêm cạnh \((1,2)\)		\[valG + = 1 + 1 + 0 + 0 + 0\] \[\rightarrow valG = 2\]
Thêm cạnh \((3,4)\)		\[valG + = 1 + 1 + 1 + 1 + 0 + 0\] \[\rightarrow valG = 2 + 4 = 6\]
Thêm cạnh \((4,5)\)		\[valG + = 1 + 1 + 2 + 2 + 2\] \[\rightarrow valG = 6 + 8 = 14\]
Thêm cạnh \((3,5)\)		\[valG + = 1 + 1 + 2 + 2 + 2\] \[\rightarrow valG = 14 + 8 = 22\]

Giá trị của đồ thị là \(valG = 22\)

• Nếu thêm các cạnh của đồ thị theo thứ tự \((3,4);(4,5);(1,2);(3,5)\) thì giá trị của đồ thị:

Đồ thị ban đầu		\[valG = 0\]
Thêm cạnh \((3,4)\)		\[valG + = 0 + 0 + 1 + 1 + 0\] \[\rightarrow valG = 0 + 2 = 2\]
Thêm cạnh \((4,5)\)		\[valG + = 0 + 0 + 2 + 2 + 2\] \[\rightarrow valG = 2 + 6 = 8\]
Thêm cạnh \((1,2)\)		\[valG + = 1 + 1 + 2 + 2 + 2\] \[\rightarrow valG = 8 + 8 = 16\]
Thêm cạnh (3,5)		\[valG + = 1 + 1 + 2 + 2 + 2\] \[\rightarrow valG = 16 + 8 = 24\]

Giá trị của đồ thị trong trường hợp này là \(valG = 24\). Đây cũng là giá trị lớn nhất đồ thị nhận được.

Dữ liệu vào:

+ Dòng đầu tiên ghi 2 số nguyên dương \(n,\ m\ (1 \leq n \leq 10^{5};0 \leq m \leq {2 \times 10}^{5})\) lần lượt là số đỉnh của đồ thị \(G\) và số cạnh trong tập \(X\)

+ \(m\) dòng tiếp theo, dòng thứ \(i\) ghi 2 số nguyên dương \(u_{i},\ v_{i}\ (1 = 1\ldots m;1 \leq u_{i},\ v_{i} \leq n;u_{i} ≠ v_{i})\) cho biết một cạch trong tập \(X\)

Kết quả: ghi một số nguyên duy nhất là giá trị lớn nhất của đồ thị \(G\).

Ví dụ:

Ràng buộc:

+ 30% số test tương ứng 30% số điểm có \(m \leq 10\)

+ 30% số test khác tương ứng 30% số điểm có \(m\) cạnh tạo thành đồ thị liên thông

+ 40% số test còn lại không có ràng buộc gì thêm.

Bạn cần Đăng nhập để nộp bài

Trò chơi hái hoa (trochoihh.*)

Trong đợt trại hè Tin học miền trung diễn ra tại thành phố ĐNN, ban tổ chức đã tổ chức cho các đoàn trò chơi hái hoa như sau: Có \(k\ (1 \leq k \leq 10)\) loại hoa (các loại hoa được đánh chỉ số từ 1 đến \(k\)) được ban tổ chức sắp xếp tại \(n\ (1 < n \leq 1000)\) vị trí (các vị trí được đánh chỉ số từ 1 đến \(n\)). Có \(m\ (1 \leq m \leq 30000)\) đoạn đường 2 chiều nối giữa các vị trí với nhau đảm bảo luôn có đường đi giữa hai vị trí bất kì, thời gian đi lại trên đoạn đường nối giữa hai vị trí \(x\) và \(y\ (1 \leq x,y \leq n)\) là \(t\ (1 \leq t \leq 10000)\ \). Nhiệm vụ của mỗi đội là xuất phát từ vị trí 1 di chuyển đến đích là vị trí \(n\) sao cho hái được đủ \(k\) loại hoa và thời gian về đích là ít nhất. Vì mỗi đội có 2 người chơi nên hoa của mỗi đội là số hoa của cả 2 người gộp lại và thời gian về đích là thời gian lớn nhất của 2 người trong đội. Mỗi người trong đội có thể chọn một hành trình bất kì, có thể đi các đoạn đường giống nhau và mỗi vị trí có thể đến nhiều lần.

Yêu cầu: Xác định thời gian ít nhất của đội giành chiến thắng.

Dữ liệu vào:

+ Dòng đầu ghi 3 số nguyên \(n,\ m,\ k\);

+ Trong \(n\) dòng tiếp theo, dòng thứ \(i\) ghi thông tin về các loại hoa được bố trí tại ví trí thứ \(i\ (1 \leq i \leq n)\); số đầu tiên ghi số nguyên \(c\ (0 \leq c \leq k)\) là số lượng các loại hoa, \(c\) số tiếp theo là chỉ số các loại hoa ở vị trí đó.

+ Trong \(m\) dòng cuối, mỗi dòng ghi thông tin về một đoạn đường gồm 3 số lần lượt là \(x,\ y,\ t\).

Các số trong tệp cách nhau ít nhất một dấu cách.

Kết quả: Ghi một số duy nhất là thời gian ít nhất tìm được.

Ví dụ:

Ràng buộc:

+ Có 20% số test tương ứng 20% số điểm có \(k = 1\);

+ Có 30% số test tương ứng 30% số điểm có \(k = 2\);

+ Có 50% số test thương ứng 50% số điểm có \(3 \leq k \leq 10\).

Bạn cần Đăng nhập để nộp bài