CHIA BÁNH

Bạn muốn chia n cái bánh cho m người, ban đầu mỗi cái bánh là một phần. Công cụ duy nhất bạn có là một dao cắt bánh, ở mỗi thao tác cắt, bạn được chia một phần bánh thành 2 phần với tỉ lệ tùy ý. Hãy tìm cách dùng ít thao tác nhất để chia bánh thành các phần chia cho m người, mỗi phần thuộc về đúng một người và lượng bánh mỗi người được nhận là bằng nhau.

Dữ liệu vào: Từ tệp văn bản SHARE.INP gồm một dòng chứa hai số nguyên dương n, m ≤10¹⁸

Kết quả: Ghi vào tệp văn bản SHARE.OUT một số nguyên duy nhất là số thao tác phải sử dụng.

Ví dụ:

SHARE.INP	SHARE.OUT
3 5	4

TẤN CÔNG THÀNH TRÌ.

Nguồn: Đề kiểm tra đội tuyển Tin học Hòa Bình

Sau khi phá tan lũ quái vật ở vùng biên giới, nhà vua quyết định mở cuộc tấn công tới tận hang ổ của bọn chúng. Hệ thống phòng thủ của lũ quái vật rất kiên cố và phức tạp. Bọn chúng xây dựng các lâu đài, và giữa một số cặp lâu đài, chúng đắp thành lũy liên kết với nhau, để bảo vệ cho các đội quân nằm bên trong, không có lâu đài nào không có thành lũy liên kết tới các lâu đài khác. Hang ổ của quân địch cứ tầng tầng lớp lớp.

Nhà vua đã vạch ra kế hoạch như sau:

+ Bước 1: Dùng máy bắn đá phá vỡ một số thành trì liên kết giữa các lâu đài của bọn chúng, sao cho không có đội quân nào của địch được bảo vệ kín bởi hệ thống thành trì.

+ Bước 2: Tiến công đánh giáp lá cà với quân địch. 

Trong các lâu đài, lũ quái vật chuẩn bị rất nhiều các máy bắn đá. Để đảm báo phá được một thành lũy, nhà vua yêu cầu cần sử dụng số máy bắn đá bằng với tổng số máy bắn đá mà hai lâu đài ở 2 đầu thành lũy của địch. Chẳng hạn nếu lâu đài A có 5 máy bắn đá, lâu đài B có 3 máy bắn đá, để phá được bức tường thành nối lâu đài A và lâu đài B, đội quân của nhà vua cần sử dụng ít nhất 5+3 = 8 máy bắn đá.

Hình vẽ minh họa cho một hệ thống lâu đài + thành lũy của quân địch. Khi phá bức tường thành liên kết giữa 2 cặp lâu đài có số lượng máy bắn đá là (1,1), sẽ sử dụng số máy bắn đá là ít nhất (4 cái). Khi đó, không còn đội quân nào được bao bọc kín bởi thành lũy nữa, quân đội của nhà vua sẽ sẵn sàng vào tấn công giáp lá cà.

Các bạn hãy giúp nhà vua tính toán xem, cần sử dụng ít nhất bao nhiêu máy bắn đá để thực hiện được bước 1 của chiến dịch.

Dữ liệu vào: Từ tệp văn bản ATTACK.INP

+ Dòng đầu tiên gồm 2 số nguyên N và M (2 <= N <= 10⁵, 1 <= M <= 10⁵) là số lâu đài của quân địch và số thành lũy liên kết một số lâu đài.

+ Dòng thứ hai chứa N số nguyên, số thứ i biểu diễn số lượng máy bắn đá của địch có trong lâu đài thứ i.

 +M dòng tiếp theo, mỗi dòng chứa 2 số nguyên (u,v) biểu diễn một thành lũy liên kết một cặp lâu đài của quân địch.

Dữ liệu ra: ghi vào tệp văn bản ATTACK.OUT

 + In ra tổng số số máy bắn đá ít nhất cần sử dụng để thực hiện bước 1 của chiến dịch.

 Ví dụ:

ATTACK.INP	ATTACK.OUT
7 8 1 1 1 2 2 3 3 1 2 2 3 1 7 2 6 6 7 2 4 4 5 3 5	4

TEST

DÃY SỐ

Cho một dãy gồm n số nguyên A = (a₁, a₂,…,a_n) và một số nguyên k. Hãy xác định xem trong dãy A có tồn tại hai phần tử a_p, a_q ở hai vị trí khác nhau p≠q mà a_p-a_q=k hay không?

Dữ liệu: Vào từ tệp văn bản SEQ.INP

+ Dòng 1 chứa 2 số nguyên n và k (2≤n≤10⁵, |k|≤2.10⁹)

+ Dòng  2 chứa n số nguyên a₁, a₂,…,a_n ("i: |a_i|≤2.10⁹)

Kết quả: Ghi ra file văn bản SEQ.OUT hai chỉ số p, 1 tìm được, nếu không tồn tại cặp số thỏa mãn yêu cầu thì ghi ra hai số 0

Các số trên một dòng của Input/Outpu files được/phải ghi các nhau ít nhất một dấu cách

Ví dụ:

SEQ.INP	SEQ.OUT
7 88 11 33 55 99 33 77 99	7 1

TEST - CODE - SOLUTION

TƯỚI NƯỚC ĐỒNG CỎ

Nguồn: spoj

Nông dân John quyết định mang nước tới cho N (1 <= N <= 300) đồng cỏ của mình, để thuận tiện ta đánh số các đồng cỏ từ 1 đến N. Để tưới nước cho 1 đồng cỏ John có thể chọn 2 cách, 1 là đào ở đồng cỏ đó 1 cái giếng hoặc lắp ống nối dẫn nước từ những đồng cỏ trước đó đã có nước tới.

Để đào một cái giếng ở đồng cỏ i cần 1 số tiền là W_i (1 <= W_i <= 100,000). Lắp ống dẫn nước nối 2 đồng cỏ i và j cần 1 số tiền là P_ij (1 <= P_ij <= 100,000; P_ij = P_ji; P_ii=0).

Tính xem nông dân John phải chi ít nhất bao nhiêu tiền để tất cả các đồng cỏ đều có nước.

Dữ liệu vào: trong file FWATER.INP

+ Dòng 1: Một số nguyên duy nhất: N

+ Các dòng 2..N + 1: Dòng i+1 chứa 1 số nguyên duy nhất: W_i

+ Các dòng N+2..2N+1: Dòng N+1+i chứa N số nguyên cách nhau bởi dấu cách; số thứ j là P_ij

Dữ liệu ra: trong file FWATER.OUT

 Một số nguyên duy nhất là chi phí tối thiểu để cung cấp nước cho tất cả các đồng cỏ.

Ví dụ:

FWATER.INP	FWATER.OUT
4 5 4 4 3 0 2 2 2 2 0 3 3 2 3 0 4 2 3 4 0	9

TEST - CODE - SOLUTION

XẾP SỐ

Giáo sư X dự định lát một hàng gạch vào chân tường phòng máy tính. Có n viên gạch đánh số từ 1 đến n, trên viên gạch thứ i ghi biểu diễn thập phân của một số nguyên dương a_i.

Mong muốn của giáo sư X là đặt n viên gạch thành một hàng theo chiều ngang (không được xoay hay lật viên gạch) sao cho dãy các chữ số ghi trên các viên gạch (tính từ trái qua phải) tọa thành một biểu diễn thập phân của một số nguyên lớn nhất có thể. Hãy giúp giáo sư X tìm cách lát, cho biết dãy chữ số tạo thành theo cách lát tìm được.

Dữ liệu: Vào từ  file văn bản MAXNUM.INP

+ Dòng 1 chứa số nguyên dương n ≤10⁵

+ Dòng 2 chứa n số nguyên dương a₁, a₂,…,a_n cách nhau bởi dấu cách ("i: a_i≤10⁹)

Kết quả: ghi ra file văn bản MAXNUM.OUT dãy chữ số từ trái qua phải theo cách lát tìm được (các chữ số phải ghi liền nhau).

Ví dụ:

MAXNUM.INP	MAXNUM.OUT
5 224 96 9 22 68	9966822422

TEST - CODE - SOLUTION

TÌM SỐ

Cho hai số nguyên d, k (1≤d≤k≤9). Hãy tìm số nguyên dương nhỏ nhất mà biểu diễn thập phân của nó có chữ số hàng đơn vị là d là nếu chuyển chữ số hàng đơn vị lên đầu thì ta được biểu diễn thập phân số mới gấp k lần số cũ.

Ví dụ với d=8 và k=4, số cần tìm là 205128 do 205128 x 4= 820512

Dữ liệu: Vào từ tệp văn bản NUMBER.INP gồm nhiều dòng, mỗi dòng chứa 2 số nguyên dương d, k cách nhau ít nhất một dấu cách.

Kết quả: ghi ra tệp văn bản NUMBER.OUT

Gồm nhiều dòng, mỗi dòng ghi một số nguyên tìm được ứng với d, k ở dòng tương ứng của file dữ liệu

Ghi -1 nếu không có số thỏa mãn.

Ví dụ:

NUMBER.INP	NUMBER.OUT
8 4	205128

GIÁ TRỊ LỚN NHẤT

Một số nguyên dương x gọi là con của số nguyên dương y nếu ta có thể xóa bớt một số chữ số của y để được x.

Cho hai số nguyên dương a và b hãy tìm số c là con của cả a và b sao cho giá trị của c là lớn nhất có thể.

Ràng buộc 1≤a,b≤10¹⁰⁰⁰. Dữ liệu vào luôn có nghiệm

Dữ liệu: Vào từ tệp văn bản NUMBER.INP

+ Dòng thứ nhất chứa số a

+ Dòng thứ hai chứa số b

Kết quả: Ghi ra tệp văn bản NUMBER.OUT số c trên 1 dòng

Ví dụ:

NUMBER.INP	NUMBER.OUT
123456781234 567812345678	56781234

TEST