JOI 2010 Final Camp - Ngày 2

Bộ đề bài

Trở lại kỳ thi
# Bài tập Điểm Thời gian: Giới hạn bộ nhớ
1 JOI 2010 - a + b problem 100 (p) 1.0s 64M
2 JOI 2010 - DNA Synthesizer 100 (p) 1.0s 64M
3 JOI 2010 - Regions 100 (p) 1.0s 64M

1. JOI 2010 - a + b problem

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

Cho hai số nguyên rất lớn được biểu diễn bằng các đoạn chữ số liên tiếp.

Yêu cầu

Hãy viết chương trình tính và in ra tổng của hai số nguyên.

Dữ liệu vào

Đọc từ đầu vào chuẩn. Hai số nguyên cần cộng được cho lần lượt theo định dạng sau:

  • Dòng đầu tiên của phần dữ liệu biểu diễn số nguyên thứ nhất chứa số nguyên \(m\). Trong \(m\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(a_i\) và \(l_i\), cách nhau bởi một dấu cách. Điều này có nghĩa là biểu diễn thập phân của số nguyên thứ nhất, từ chữ số có hàng cao nhất đến chữ số có hàng thấp nhất, gồm \(l_1\) chữ số \(a_1\), rồi \(l_2\) chữ số \(a_2\), \(\ldots\), rồi \(l_m\) chữ số \(a_m\).
  • Ngay sau phần dữ liệu biểu diễn số nguyên thứ nhất là phần dữ liệu biểu diễn số nguyên thứ hai, theo cùng định dạng.

Dữ liệu ra

Giả sử biểu diễn thập phân của tổng hai số nguyên, từ chữ số có hàng cao nhất đến chữ số có hàng thấp nhất, gồm \(L_1\) chữ số \(A_1\), rồi \(L_2\) chữ số \(A_2\), \(\ldots\), rồi \(L_M\) chữ số \(A_M\), trong đó \(0\le A_i\le9\), \(L_i\ge1\), \(A_1\ne0\) và \(A_i\ne A_{i+1}\) với \(1\le i\le M-1\).

In ra đầu ra chuẩn \(M+1\) dòng:

  • Dòng đầu tiên chứa số nguyên \(M\).
  • Dòng thứ \(i+1\) (\(1\le i\le M\)) chứa hai số nguyên \(A_i\) và \(L_i\) theo thứ tự này, cách nhau bởi một dấu cách.

Lưu ý quan trọng: Các giá trị \(L_i\) không nhất thiết nằm trong phạm vi biểu diễn của kiểu số nguyên 32 bit. Cần sử dụng kiểu dữ liệu 64 bit, chẳng hạn long long.

Ràng buộc

  • Giới hạn trong kỳ thi gốc: thời gian \(1\) giây, bộ nhớ \(64\) MB.
  • Trong kỳ thi gốc, kích thước ngăn xếp (stack) chỉ bị giới hạn bởi giới hạn bộ nhớ của bài, không có giới hạn riêng nhỏ hơn.

Các điều kiện sau áp dụng cho phần dữ liệu biểu diễn của mỗi số nguyên:

  • \(1\le m\le20\,000\).
  • \(0\le a_i\le9\) với \(1\le i\le m\).
  • \(1\le l_i\le100\,000\,000\) với \(1\le i\le m\).
  • \(a_1\ne0\).
  • \(a_i\ne a_{i+1}\) với \(1\le i\le m-1\).

Phân nhóm

Bài này có tổng cộng \(100\) điểm, gồm \(10\) bộ dữ liệu, mỗi bộ \(10\) điểm.

  • Nhóm test trị giá \(30\) điểm: Với mỗi số nguyên đầu vào, \(m\le1\,000\) và \(l_i\le1\,000\) với mọi \(1\le i\le m\).

Ví dụ

Ví dụ 1

Input 
3
1 3
2 4
3 5
3
9 4
8 3
7 2
Output 
4
1 2
2 8
1 1
0 1
Giải thích

Hai số nguyên được cho trong đầu vào là \(111222233333\) và \(999988877\). Tổng của chúng là \(112222222210\), nên đầu ra như trên.

2. JOI 2010 - DNA Synthesizer

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

Một phương pháp tổng hợp chuỗi DNA mới từ hai chuỗi DNA chỉ gồm các ký tự A, T, G, C đã được phát triển. Nếu phần đầu của một chuỗi và phần cuối của chuỗi kia có một đoạn chung liên tiếp gồm ít nhất một ký tự, ta có thể nối hai chuỗi bằng cách gộp hai đoạn chung này thành một.

Ví dụ, TTTATGC và ATGCAAA có đoạn chung ATGC ở cuối chuỗi thứ nhất và đầu chuỗi thứ hai, nên có thể nối chúng để tổng hợp chuỗi TTTATGCAAA. Ngoài ra, từ hai chuỗi AAA, ta có thể tổng hợp được cả chuỗi AAAA lẫn chuỗi AAAAA.

Để phát triển một loại thuốc mới, người ta muốn tổng hợp một chuỗi DNA nhất định từ các chuỗi DNA cơ sở có trong phòng thí nghiệm.

Yêu cầu

Phòng thí nghiệm có \(N\) loại chuỗi DNA cơ sở. Hãy viết chương trình tìm số chuỗi DNA cơ sở ít nhất cần dùng để tổng hợp chuỗi DNA đích bằng phương pháp nối trên. Nguồn dự trữ các chuỗi DNA cơ sở rất dồi dào, nên có thể sử dụng cùng một loại bao nhiêu lần tùy ý. Trong mọi bộ dữ liệu chấm, luôn tồn tại một cách kết hợp các chuỗi DNA cơ sở để thu được chuỗi DNA đích.

Dữ liệu vào

Đọc từ đầu vào chuẩn:

  • Dòng đầu tiên chứa số nguyên \(N\).
  • Dòng thứ hai chứa một xâu chỉ gồm các ký tự A, T, G, C, biểu diễn chuỗi DNA đích.
  • Trong \(N\) dòng tiếp theo, mỗi dòng chứa một xâu chỉ gồm các ký tự A, T, G, C, biểu diễn một loại chuỗi DNA cơ sở. Không có hai chuỗi DNA cơ sở trùng nhau trong danh sách này.

Dữ liệu ra

In ra đầu ra chuẩn một số nguyên là số chuỗi DNA cơ sở ít nhất cần dùng.

Ràng buộc

  • Giới hạn trong kỳ thi gốc: thời gian \(1\) giây, bộ nhớ \(64\) MB.

  • Trong kỳ thi gốc, kích thước ngăn xếp (stack) chỉ bị giới hạn bởi giới hạn bộ nhớ của bài, không có giới hạn riêng nhỏ hơn.

  • Số loại chuỗi DNA cơ sở \(N\) không vượt quá \(50\,000\).

  • Độ dài chuỗi DNA đích không vượt quá \(150\,000\).
  • Độ dài mỗi chuỗi DNA cơ sở không vượt quá \(20\).

Phân nhóm

Bài này có tổng cộng \(100\) điểm, gồm \(10\) bộ dữ liệu, mỗi bộ \(10\) điểm.

  • Nhóm test trị giá \(30\) điểm: \(N\) và độ dài chuỗi DNA đích đều không vượt quá \(1\,000\).

Ví dụ

Ví dụ 1

Input 
5
ATATATGCCCAT
ATAT
ATG
GCCC
GCCCAT
CAT
Output 
4
Giải thích

Lưu ý rằng có thể sử dụng cùng một loại chuỗi DNA cơ sở nhiều lần.

Ví dụ 2

Input 
1
AAAAAAAAAA
AAA
Output 
5
Giải thích

Từ hai chuỗi AAA, ta có thể tổng hợp được cả chuỗi AAAA lẫn chuỗi AAAAA.

Ví dụ 3

Input 
2
ATATATATAT
ATA
TAT
Output 
5

3. JOI 2010 - Regions

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

Đất nước JOI có \(N\) thành phố, được đánh số từ \(1\) đến \(N\). Các thành phố được nối với nhau bằng những con đường hai chiều tạo thành một cây. Nghĩa là giữa hai thành phố bất kỳ đều có thể đi lại theo các con đường, và đường đi đó là duy nhất. Khi đó, có \(N-1\) con đường.

Người ta quyết định chia các thành phố thành \(M\) vùng. Mỗi vùng phải chứa ít nhất một thành phố, và mỗi thành phố phải thuộc đúng một vùng. Ngoài ra, giữa hai thành phố bất kỳ trong cùng một vùng phải có thể đi lại theo các con đường mà không đi qua thành phố nào ngoài vùng đó.

Người ta muốn chia vùng sao cho giá trị lớn nhất trong các đường kính của các vùng, ký hiệu là \(d_{\max}\), nhỏ nhất có thể. Đường kính của một vùng là khoảng cách lớn nhất giữa hai thành phố thuộc vùng đó. Khoảng cách giữa hai thành phố là tổng độ dài các con đường trên đường đi nối chúng. Nếu một vùng chỉ chứa một thành phố thì đường kính của vùng đó được quy ước bằng \(0\).

Yêu cầu

Cho thông tin về các con đường và số vùng cần chia, hãy viết chương trình tính giá trị nhỏ nhất có thể của \(d_{\max}\).

Dữ liệu vào

Đọc từ đầu vào chuẩn:

  • Dòng đầu tiên chứa hai số nguyên \(N\), \(M\), cách nhau bởi một dấu cách.
  • Trong \(N-1\) dòng tiếp theo, mỗi dòng mô tả một con đường. Dòng thứ \(i\) trong số này chứa ba số nguyên \(A_i\), \(B_i\), \(C_i\), cách nhau bởi dấu cách, cho biết con đường thứ \(i\) nối hai thành phố \(A_i\), \(B_i\) và có độ dài \(C_i\).

Dữ liệu ra

In ra đầu ra chuẩn một số nguyên là giá trị nhỏ nhất có thể của \(d_{\max}\).

Ràng buộc

  • Giới hạn trong kỳ thi gốc: thời gian \(1\) giây, bộ nhớ \(64\) MB.

  • Trong kỳ thi gốc, kích thước ngăn xếp (stack) chỉ bị giới hạn bởi giới hạn bộ nhớ của bài, không có giới hạn riêng nhỏ hơn.

  • \(2\le N\le30\,000\): số thành phố.

  • \(2\le M\le N\): số vùng.
  • \(1\le A_i<B_i\le N\) với \(1\le i\le N-1\): hai thành phố được nối bởi con đường thứ \(i\).
  • \(1\le C_i\le100\) với \(1\le i\le N-1\): độ dài con đường thứ \(i\).

Phân nhóm

Bài này có tổng cộng \(100\) điểm, gồm \(10\) bộ dữ liệu, mỗi bộ \(10\) điểm.

  • Nhóm test trị giá \(20\) điểm: \(M=2\) và \(N\le1\,000\).
  • Nhóm test trị giá \(40\) điểm: \(M=2\).

Ví dụ

Ví dụ 1

Input 
5 2
1 4 2
2 3 3
2 4 1
4 5 1
Output 
3
Giải thích

Chia thành hai vùng: một vùng gồm các thành phố \(1,4,5\) và một vùng gồm các thành phố \(2,3\). Khi đó \(d_{\max}=3\), và đây là giá trị tối ưu.

Ví dụ 2

Input 
5 3
1 4 2
2 3 3
2 4 1
4 5 1
Output 
2
Giải thích

Chia thành ba vùng: một vùng chỉ gồm thành phố \(1\), một vùng gồm các thành phố \(2,4,5\), và một vùng chỉ gồm thành phố \(3\). Khi đó \(d_{\max}=2\), và đây là giá trị tối ưu.