Ôn thi 2

Bài 1: Thi đấu giao hữu

Sau nhiều năm tu luyện Bờm đã đạt được chỉ số sức mạnh là s. Xuống núi lần này Bờm đến làng Thượng Võ để thi đấu giao hữu. Trong làng có tất cả n võ sĩ, các võ sĩ được đánh số thứ tự từ 1 đến n, võ sĩ thứ i sẽ có chỉ số sức mạnh là a_i. Bờm chỉ muốn thi đấu giao hữu với những đối thủ có chỉ số sức mạnh gần với chỉ số sức mạnh của mình nhất. Hãy viết chương trình giúp Bờm chọn được đối thủ để giao hữu

Input: file thidau.inp gồm

-dòng 1 : Hai số nguyên n và S. Lần lượt là số võ sĩ ở làng, chỉ số sức mạnh của Bờm. (0<n<10⁷, 0<s<=10⁹)

-dòng 2: ghi n số nguyên a_i. (0<a_i<=10⁹):

Output: file thidau.out gồm 1 dòng

-in chỉ số sức mạnh của đối thủ mà Bờm sẽ thi đấu giao hữu. Nếu có nhiều hơn một trường hợp thì chọn trường hợp có sức mạnh nhỏ hơn

Ví dụ:

Input	output
8 90 1 9 2 100 70 120 79	100
9 90 1 9 2 100 70 120 79 80	80

Bài 2: số lớn nhất trong đoạn

Cho dãy A gồm n số nguyên. Các số được đánh thứ tự từ 1 đến n. Số thứ i có giá trị là a_i. Hãy viết chương trình xác định số lớn nhất nằm trong đoạn có thứ tự từ x đến y

Input: file maxdoan.inp gồm

-dòng 1: 3 số nguyên n, x, y. (0<x<y<n<=10⁴)

-dòng 2: ghi n số nguyên a_i

Output: file maxdoan.out gồm

-ghi giá trị lớn nhất nằm trong đoạn có thứ tự từ x đến y

Ví dụ:

Input	output
8 2 5 1 9 2 100 70 120 79	100
9 1 3 1 9 2 100 70 120 79 80	9

Bài 3: Cho dãy n số nguyên

Hãy đưa ra số lần xuất hiện của giá trị xuất hiện nhiều nhất trong dãy

Dữ liệu được nhập vào từ file dayso.inp gồm 2 dòng:

-dòng 1 ghi số nguyên n (0<n<=10⁹)

-dòng 2 ghi các số nguyên trong dãy

Dữ liệu xuất ghi ra file dayso.out gồm 1 dòng ghi ra số lần xuất hiện của giá trị xuất hiện nhiều nhất trong dãy

dayso.inp	dayso.out
8 2       7  19 -2 13 19 13 1	2

 

Bài 4: Khóa số

Cho một khóa số có n đĩa quay. Mỗi đĩa quay có các số từ 0 đến 9 được ghi trên đó. Trên ổ khóa có một vạch màu trắng cho biết số hiện hành của ổ khóa. Muốn mở được khóa ta phải xoay các đĩa của ổ khóa (có thể xoay lên hoặc xoay xuống) để thay đổi số hiện hành cho đến khi trùng với mật khẩu của ổ khóa. Hãy viết một chương trình tính tổng số lần xoay tối thiểu để mở được ổ khóa?

Input: file khoaso.inp

Dòng đầu tiên chứa một số nguyên n ( 1 ≤  n  ≤ 18 ) - số lượng đĩa trên khóa số.

Dòng thứ hai chứa một số nguyên n chữ số - số hiện hành của ổ khóa.

Dòng thứ ba chứa một số nguyên n chữ số - mật khẩu của ổ khóa.

Output: file khoaso.out

In một số nguyên duy nhất – tổng số lần xoay tối thiểu để để mở khóa.

ví dụ:

Input	Output	Giải thích
5 85284 08941	15	Đĩa 1: 8è9è0=2 Đĩa 2: 5è6è7è8=3 Đĩa 3:2è1è0è9=3 Đĩa 4: 8è7è6è5è4=4 Đĩa 5: 4è3è2è1=3

Bài 5: Số fibonacci thứ n

Dãy số Fibonacci là dãy số mà các số của dãy được tính như sau:

F ₀  = 0 , F ₁  = 1 và tất cả các số tiếp theo là F _i  =  F _{i  - 2}  +  F _{i  - 1} .

Vì vậy, các số Fibonacci đầu tiên là: 0 , 1 , 1 , 2 , 3 , 5 , 8 , 13 , ...

Cho số nguyên n. Hãy viết chương trình in ra số Fibonacci thứ n

Input: file fibo.inp gồm

-một dòng ghi số nguyên n (0<=n<=1000)

Output: file fibo.out gồm

-một dòng in số fibonacci thứ n

ví dụ:

Input	Output
6	5

Bài 6: Mua bóng

Minh cần một số quả bóng để chuẩn bị cho mùa bóng mới của câu lạc bộ. Anh ta đến cửa hàng và chọn quả bóng thích hợp. Quả bóng mà Minh muốn mua có giá k đồng. 

Giả sử trong túi Minh có vô số "tiền xu mệnh giá 10 đồng" và chỉ duy nhất một đồng xu mệnh giá x đồng ( 1 ≤  x  ≤ 9 ).

Do chủ cửa hàng không có tiền trả lại tiền thừa cho Minh nên cậu phải tính số lượng bóng tối thiểu cần mua để ông chủ cửa hàng không phải trả lại tiền thừa. Cần lưu ý rằng Minh cần mua ít nhất một quả bóng và có thể chỉ dùng đồng xu có mệnh giá 10 đồng để trả tiền.

Input: muabong.inp

Một dòng đầu vào chứa hai số nguyên k và x ( 1 ≤  k  1000 , 1 ≤  x  ≤ 9 ) - giá của một quả bóng và mệnh giá x của đồng xu trong túi của Minh

Output: muabong.out

In số lượng tối thiểu quả bóng mua để Minh có thể trả tiền mà chủ cửa hàng không phải trả lại tiền thừa.uew

Ví dụ:

Ví dụ:

Input	output
117 3	9
120 5	1

Bài 7: Số chính phương

Cho số nguyên dương n. Hãy viết chương trình in ra số chính phương nhỏ nhất lớn hơn N

input: file socphuong.inp gồm 1 dòng 

-in số nguyên n (0<n<100000000)

output: file socphuong.out gồm 1 dòng

-in số chính phương nhỏ nhất lớn hơn n

ví dụ: n=1 ==>số chính phương nhỏ nhất lớn hơn n là 4
Bài số 8: giúp việc nhà

Mỵ làm nghề giúp việc nhà cho các gia đình bận mải. Gần đây Mỵ đã nhận giúp việc theo giờ cho m gia đình sống trong cùng một tuyến phố với mình. Tuyến phố có n gia đình mỗi gia đình có một ngôi nhà được xây dọc theo đường vòng tròn. Những ngôi nhà đánh số từ 1 đến n theo thứ tự chiều kim đồng hồ. Giao thông đường vòng tròn là một chiều và cũng theo chiều kim đồng hồ.

Để giúp việc cho nhà thứ i, cô ấy cần phải ở trong nhà số a_i và hoàn thành công việc ở nhà đó. Việc di chuyển từ nhà này sang nhà bên cạnh hết 1 phút. Ngôi nhà mà Mỵ ở là nhà số 1. Hãy viết chương trình tính tổng thời gian di chuyển tối thiểu để Mỵ hoàn thành công việc cho m gia đình.

Input: vào từ file giupviec.inp gồm 2 dòng

-Dòng đầu tiên chứa hai số nguyên n và m (2≤ n ≤ 10⁵, 1 ≤ m ≤10⁵).

-Dòng thứ hai chứa m số nguyên a₁, a₂, ..., a_m (1 ≤ a_i ≤ n). Lưu ý rằng Mỵ có thể có nhiều việc liên tiếp trong một gia đình và giúp việc cho chính gia đình của mình.

Output: ghi ra file giupviec.out gồm 1 dòng
In một số nguyên duy nhất -  tổng thời gian di chuyển tối thiểu để Mỵ thành tất cả các nhiệm vụ.eeo*

Ví dụ:

Input	output	Giải thích
4 3 3 2 3	6	Mỵ sẽ di dọc theo đường vòng tròn như sau: 1 → 2 → 3 → 4 → 1 → 2 → 3. Vì vậy, cô ấy cần 6 phút

Bài 9: Tính tổng

Cho dãy N số nguyên. Các số nguyên được đánh thứ tự từ 1 đến N, số thứ i có giá trị là a_i Cho m truy vấn, mỗi truy vấn cung cấp 2 số x, y. Hãy viết chương trình tính tổng đoạn con liên tiếp từ x đến y

Input: tinhtong.inp gồm

·       Dòng đầu là số nguyên N (0 < n < 10⁶)

·       Dòng sau gồm n số nguyên a₁, a₂, ..., a_n. (|a_i|<1000)

·       Dòng tiếp theo là số nguyên dương m (0 < m < 10⁶)

·       M dòng tiếp theo, mỗi dòng ghi 2 số x, y (1 ≤ x ≤ y ≤ n)

Output: tinhtong.out gồm

Xuất m dòng, dòng thứ i là kết quả của truy vấn thứ i

Ví dụ:

Input	Output
5 9 2 10 -6 8 3 1 2 2 4 3 5	11 6 12

Bài 10: Hợp số

Hợp số là số lớn hơn 1 có nhiều hơn 2 ước. Một định nghĩa khác: hợp số là số chia hết cho các số khác ngoài 1 và chính nó.

Có một phỏng đoán rằng: Mọi số nguyên lớn hơn 11 đều có thể biểu diễn dưới dạng tổng của hai hợp số. Hãy viết chương trình thể hiện phỏng đoán này

Input: file hopso.inp
Dòng duy nhất chứa một số nguyên n (12 ≤ n ≤10⁶).

output:file hopso.out
Xuất hai số nguyên x và y là hợp số (1 <x, y <n) sao cho x + y = n. Nếu có nhiều trường hợp em có thể xuất bất kỳ trường hợp nào

Ví dụ:

Input	Output
12	4 8
15	9 6