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

LỊCH SỬA CHỮA Ô TÔ

Một cơ sở sửa chữa ô tô có nhận n chiếc xe để sửa. Do các nhân viên làm việc quá lười nhác nên đã đến hạn trả cho khách hàng mà vẫn chưa tiến hành sửa được chiếc xe nào. Theo hợp đồng đã ký kết thừ trước, nếu bàn giao xe i quá hạn ngày nào thì sẽ phải trả thêm một khoản tiền phạt là a_i.

Ông chủ cơ sở sữa chữa quyết định sa thải toàn bộ công nhân và thuê công nhân mới. Với lực lưỡng mới này, ông ta dự định tằng để sửa chiếc xe i cần b_i ngày. Vấn đề đặt ra đối với ông là phải lập lịch sửa tuần tự các chiếc xe sao cho tổng số tiền bị phạt là ít nhất

Yêu cầu: Hãy lập lịch sửa xe giúp cho ông chủ cơ sở sửa chữa ô tô sao cho tổng số tiền bị phạt là ít nhất.

Dữ liệu: Vào từ tệp văn bản SCHEDULE.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, 1≤a_i≤1000, "i:1≤i≤n

+ Dòng 3: Chứa n số nguyên dương b₁, b₂,…,b_n, 1≤b_i≤1000, "i:1≤i≤n

Kết quả: Ghi ra file văn bản SCHEDULE.OUT một số nguyên duy nhất là  số tiền phạt tối thiểu theo phương án tìm được.

Ví dụ:

SCHEDULE.INP	SCHEDULE.OUT
4 1 3 4 2 3 2 3 1	44

 

Tiền phạt:

Xe 4: muôn 1 (ngày) x 2 = 2

Xe 2: Muộn 3 (ngày) x 3 = 9

Xe 3: Muộn 6 (ngày) x 4 = 24

Xe 1: Muộn 9 (ngày) x 1 = 9

------------------------------------

Tổng cộng:                        = 44

Nếu sửa theo thứ tự 1, 2, 3, 4 thì

Xe 2: muôn 3 (ngày) x 1 = 3

Xe 2: Muộn 5 (ngày) x 3 = 15

Xe 3: Muộn 8 (ngày) x 4 = 32

Xe 4: Muộn 9 (ngày) x 2 = 9

------------------------------------

Tổng cộng:                        = 68

TEST  -  CODE - SOLUTION

Đề thi HSG lớp 11 môn Tin học khu vực Bắc Bộ năm 2013

Tin11 2013 HSG-khuvuc-BacBo de Thi

Đề thi HSG lớp 10 môn Tin học khu vực Bắc Bộ năm 2013

Tin10 2013 HSG-khuvuc-BacBo de Thi

Lời giải Tin học lớp 10 - HSG Bắc Bộ năm 2012

Tin10 2012 HSG-khuvuc-BacBo Loi Giai

Đề thi HSG lớp 10 môn Tin học khu vực Bắc Bộ năm 2012

Tin10 2012 HSG-khuvuc-BacBo de Thi

Đề thi HSG môn Tin học tỉnh Khánh Hòa - Bậc THCS - năm học 2015-2106

Đề thi học sinh giỏi Tỉnh THCS môn Tin học 2015-2016

CHỤP ẢNH

Lễ khai mạc thế vận hội năm 2112 có n vận động viên đánh số từ 1 tới n đứng xếp hàng ngang để chụp ảnh, ban tổ chức đã sắp xếp họ theo một thứ tự mà họ cho là đẹp nhất gọi là thứ tự chuẩn.

Tuy nhiên khi người thợ chụp ảnh quay lại để bấm máy, một số vận động viên đã tự ý rời khỏi hàng để bắt tay khán giả (những vận động viên khác giữ nguyên vị trí). Trọng tài cảnh cáo những vận động viên tự ý rời khỏi hàng và yêu cầu quay lại hàng ngũ, tuy nhiên những vận động viên vừa bị cảnh cáo khi quay lại hàng có thể chèn vào những vị trí mới làm mất đi thứ tự chuẩn, tấm ảnh chụp được không được như ý.

Ban tổ chức sắp xếp lại các vận động viên theo thứ tự chuẩn nhưng mọi việc diễn ra tương tự như trên. Sau 5 lần và thu được 5 tấm ảnh, ban tổ chức đành bỏ cuộc và gửi 5 tấm ảnh cho chuyên gia photoshop cắn dán lại theo thứ tự chuẩn.

Vấn đề đặt ra là Ban tổ chức đã quên mất thứ tự chuẩn, bạn cần dựa vào thứ tự của 5 bức ảnh để xác định thứ tự chuẩn của ban tổ chức. Biết rằng không có vận động viên nào bị cảnh cáo nhiều hơn 1 lần.

Ví dụ ví n=9, thứ tự chuẩn là (1,3,5,7,9,2,4,6,8)

Lần 1 vận động viên 3 và 8 rời khỏi vị trí: (1,3,5,7,9,2,4,6,8) -> (1,5,7,8,9,2,4,3,6)

Lần 2 vận động viên 2,4 và 6: rời khỏi vị trí: (1,3,5,7,9,2,4,6,8)->(2,4,6,1,3,5,7,9,8)

Lần 3 vận động viên 1 rời khỏi vị trí: (1,3,5,7,9,2,4,6,8) -> (3,5,7,9,2,4,6,8,1)

Lần 4 vận động viên 5 rời  khỏi vị trí: (1,3,5,7,9,2,4,6,8) -> (1,3,7,5,9,2,4,6,8)

Lần 5 vận động viên 7 rời khỏi vị trí: (1,3,5,7,9,2,4,6,8) -> (1,7,3,5,9,2,4,6,8)

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

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

+ 5 dòng tiếp theo, dòng thứ i chứa n số nguyên là số hiệu các vận động viên trong bức ảnh thứ i theo đúng thứ tự trong ảnh.

Kết quả: ghi ra file văn bản PHOTO.OUT n số nguyên là số hiệu các vận động viên theo đúng thứ tự chuẩn muốn chụp.

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

Ví dụ:

PHOTO.INP	PHOTO.OUT
9 1 5 7 8 9 2 4 3 6 2 4 6 1 3 5 7 9 8 3 5 7 9 2 4 6 8 1 1 3 5 7 9 2 4 6 8 1 7 3 5 9 2 4 6 8	1 3 5 7 9 2 4 6 8

 TEST - CODE - SOLUTION