ÔN THI 4

Bài: 1 Từ chối nhập học

Trường Đại Học XYZ tổ chức thi tuyển sinh năm học 2018-2019. Có 1000 thí sinh dự thi. Chỉ tiêu tuyển sinh của trường là N. Vì vậy những thí sinh trúng tuyển là những thí sinh có thứ hạng xếp loại điểm thi từ 1 đến n. Nhà trường đã gửi giấy thông nhập học cho n thí sinh có điểm thi cao nhất. Tuy nhiên có một số thí sinh trong số n ngưới trúng tuyển không nhập học vì một lý do nào đó. Vậy nên trường đã gọi bổ sung theo nguyên tắc: Bất cứ khi nào có một thí sinh từ chối thì thí sinh xếp hạng cao nhất chưa được gọi nhập học sẽ được mời thay thế. Điều này sẽ tiếp tục cho đến khi đủ chỉ tiêu. Ví dụ: thí sinh đứng thứ 2 không nhập học thì sẽ gọi bổ sinh thí sinh đứng thứ n+1.

Kì tuyển sinh hoàn tất, bây giờ nhà trường cần biết những thí sinh nào đã không nhập học

Input: tuchoi.inp gồm

Dòng đầu tiên chứa n ( 1 ≤ n  ≤50 ) Chỉ tiêu tuyển sinh.

Dòng hai chứa a ₁ ,  a ₂ , ...,  a_n ( 1 ≤  a _i  ≤ 10³ ) là thứ hạng của các thí sinh đã nhập học, a_i là thứ hạng điểm thi của thí sinh thứ i. Tất cả các thứ hạng là khác nhau

Output:tuchuoi.out gồm

In ra thứ hạng của những thí sinh đã không nhập học. Danh sách in theo thứ tự tăng. Nếu không có thí sinh nào thì in -1

Ví dụ:

Input	Output
5 9 3 2 7 5	1 4 6 8
8 1 2 3 4 5 6 7 8	-1
5 1 4 5 6 3	2

Bài 2: Tìm số nguyên a

Cho 2 số nguyên dương m và n. Tìm số nguyên a thỏa mãn 2 điều kiện

     @ m ≤ a ≤ n

     @ Tất cả các chữ số của a là khác nhau

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

-ghi hai số nguyên m và n (0< m≤ n ≤10⁵)

Output: ghi ra file tima.out gồm một dòng

-ghi số nguyên a nhỏ nhất thỏa mãn điều kiện đầu bài. Nếu không có ghi -1

Ví dụ:

input	output	Giải thích
110   125	120	Trong phạm vi này có 4 số là 120, 123, 124, 125
110  119	-1

Bài 3: Bộ số Pitago

Ba số nguyên a, b, c (a<b<c) được gọi là bộ pitago nếu c²=a²+b²

Cho số nguyên dương x. Hỏi x có thể phân tích thành tổng của ba số trong bộ pitago như trên không?

Input: Vào từ file pitago.inp gồm một dòng ghi số nguyên x (0<x<10⁹)

Output: Ghi ra file pitago.out gồm một dòng ghi

- Nếu x có thể phân tích được thành tổng của ba số thuộc bộ pitago thì ghi lần lượt ba số nguyên a, b, c. Ngược lại ghi -1

Ví dụ:

Input	Output	Giải thích
12	3 4 5	12=3+4+5 52=32+42
9	-1

Read More

ÔN THI 3

Bài 1: Số nguyên tố nhỏ nhất

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

Input: nhập từ file ngtomin.inp gồm 2 dòng

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

-dòng 2 ghi n số nguyên a_i. Mối số có giá trị tuyệt đối không lớn hơn 10⁷

Output: ghi ra file ngtomin.out gồm 1 dòng

-ghi số nguyên tố cần tìm

Ví dụ:

Input	Output
5 10 7 8 2 13	17

Bài 2: Số chính phương lớn nhất

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

Input: nhập từ file cphuong.inp gồm 2 dòng

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

-dòng 2 ghi n số nguyên a_i. Mối số có giá trị tuyệt đối không lớn hơn 10⁷

Output: ghi ra file cphuong.out gồm 1 dòng

-ghi số chính phương  cần tìm

Ví dụ:

Input	Output
8 10 16 8 2 13 -9 4 9	16

Bài 3: Số 2^k

Cho dãy a gồm n số nguyên. Các số nguyên được đánh số thứ tự từ 1 đến n. Số thứ i có giá trị là a_i. Hãy viết chương trình tìm những số có dạng 2^k  (k>=0) trong dãy a.

Input: nhập từ file somuk.inp gồm 2 dòng

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

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

Output: ghi ra file somuk.out gồm 1 dòng

-ghi số lượng số có dạng 2^k  trong dãy

Ví dụ:

Input	Output	Giải thích
8 10 16 8 2 13 27 4 9	4	Các số dạng 2k trong dãy: 16, 8, 2,4

Bài 4: Số cuối cùng

Trong lúc rảnh rỗi Bờm đã nghĩ ra một trò chơi như sau:

Từ dãy số a ban đầu. Bờm lấy 2 số ở cạnh nhau cộng lại với nhau để được dãy số mới, sau bước này dãy a giảm đi một số. Bờm lặp lại quá trình này cho đến khi dãy a chỉ còn một số

Hãy viết chương trình in ra số cuối cùng của dãy a theo cách chơi của Bờm.

Input: nhập từ file socuoi.inp gồm 2 dòng

-dòng 1: số nguyên n (0<n<=100)

-dòng 2 ghi n số nguyên trong dãy a. Mối số có giá trị tuyệt đối không lớn hơn 100 và cách nhau 1 kí tự trắng.

Output: ghi ra file socuoi.out gồm 1 dòng

-ghi số cuối cùng cần tìm

Ví dụ:

input	output	Giải thích
5 60 3 4 2 6	110	Lần 1: 63 7 6 8 Lần 2: 70 13 14 Lần 3: 83 27 Lần 4:110

Bài 5: Đoạn con có tổng bằng s
Cho dãy a gồm n số nguyên. Các số nguyên được đánh số thứ tự từ 1 đến n. Số thứ i có giá trị là a_i. Hãy viết chương trình tìm kiểm tra trong dãy a có tồn tại đoạn con gồm các phần tử liên tiếp có tổng bằng s hay không?

Input: nhập từ file doancon.inp gồm 2 dòng

-dòng 1: số nguyên n và s (0<n<=10⁶)

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

Output: ghi ra file doancon.out gồm 1 dòng

-ghi số lượng các đoạn con trong dãy có tổng bằng 10

Ví dụ:

Input	Output	Giải thích
8 10 10 16 8 2 13 27 4 9	2	trong dãy có 2 đoạn con có tổng bằng 10 đoạn 1: 10 đoạn 2: 8 2

Bài 6: Chia kẹo

Bờm có n viên kẹo và anh ấy muốn chia chúng thành k phần để tặng cho k em bé. Bờm không thể chia một viên kẹo thành nhiều phần. Số kẹo ở mỗi phần có thể là a hoặc b

Bờm sẽ hài lòng, nếu cả ba điều kiện được đáp ứng cùng một lúc:

* b = a hoặc b = a + 1;

* Số phần có kẹo bằng (a+ 1) phải nhỏ hơn hoặc bằng (k div 2) (chú ý rằng a + 1 không nhất thiết phải bằng b)

* Tổng số kẹo để tặng càng nhiều, càng tốt

Nhiệm vụ của bạn là tìm ra tổng số kẹo đã sử dụng theo cách chia của Bờm

Input: file chiakeo.inp gồm 1 dòng

-chứa 2 số nguyên n và k (0<n,k<=10⁹)

Output: file chiakeo.inp gồm 1 dòng

-in ra tổng số kẹo mà Bờm đã sử dụng để tặng

Ví dụ:

Input	Output	Giải thích
5 2	5	Bờm chia thành 2 phần là 2 viên và 3 viên. Như vậy Bờm dùng hết cả 5 viên kẹo
19 4	18	Bờm chia thành 4 phần là 4, 4, 5, 5. Không thể chia thành 4, 5, 5, 5 vì vi phạm quy tắc thứ 2. Như vậy Bờm dùng hết 18 viên kẹo asdl.

Bài 7: Trộn mảng

Cho hai mảng số nguyên dương A và B lần lượt có N và M số. Các phần tử trong cả hai mảng A và B đều được sắp theo thứ tự tăng dần.

Yêu cầu: hãy tạo mảng C gồm N+M phần tử từ tất cả các phần tử của A và B sao cho các phần tử của C cũng có thứ tự tăng dần.

Input: file tronmang.inp gồm

·       Dòng đầu chứa 2 số N, M (0 < N, M <50 000)

·       N dòng sau, mỗi dòng chứa một số nguyên của mảng A.

·       M dòng tiếp theo chứa 1 số nguyên dương ứng với các phần tử của mảng B.

output: file tronmang.out gồm

 gồm N+M dòng, lần lượt chứa các phần tử của mảng C.

Input	Output
3 2 1 2 5 2 4	1 2 2 4 5

Bài 8: Chia nhóm

Bờm có một dãy n số nguyên a₁, a₂,…, a_n. Bờm cần bạn giúp cậu ấy phân nhóm cho dãy số theo quy tắc sau:

-Các số trong cùng nhóm phải chia hết cho số nhỏ nhất của nhóm

-Số lượng nhóm được chia phải là ít nhất.

-Các số cùng nhóm có thể không ở cạnh nhau.

Input: file chianhom.inp gồm

-Dòng 1: chứa số nguyên n (1≤n≤10²)

-Dòng thứ hai chứa n số nguyên a₁, a₂, …, a_n (1≤a_i≤10²). Các số cách nhau một kí tự trắng aspo

Output: file chianhom.out gồm một dòng

 -Ghi số lượng nhóm theo quy tắc của Bờm.

Ví dụ:

input	output	Giải thích
3 20 10 30	1	Chia thành 1 nhóm vì tất cả chúng đều chia hết cho 10
5 12 4 15 8 3	2	Nhóm 1: 12, 4, 8 đều chia hết cho 4 Nhóm 2: 15, 3 đều chia hết cho 3
2 9 7	2

Bài 9: Trò chơi chẵn lẻ

Tý và Sửu nghĩ ra trò chơi chẵn lẻ như sau: Cho một dãy số nguyên A có giá trị từ 1 đến n. Hai người chơi thay phiên nhau chọn một số bất kỳ trong dãy A, sau mỗi lượt thì số được chọn bị xóa khỏi dãy. Tý thích chọn những số chẵn, Sửu thì thích chọn những số lẻ.

Nếu đến lượt mình mà người chơi không thể chọn bất kỳ số nào theo ý thích thì người đó sẽ thua. Hãy viết chương trình xác định người chiến thắng. Biết Tý là người chơi lượt đầu tiên.

input: file chanle.inp gồm

Dòng duy nhất chứa một số nguyên n (1  ≤n  ≤10⁹)

output: file chanle.out gồm

Dòng duy nhất in ra tên của người dành chiến thắng

Ví dụ:

Input	output
1	Ty
2	Suu

Bài 10: bán hàng đồng giá

Bờm tham gia bán hàng tại hội chợ kích cầu tiêu dùng huyện Cẩm Mỹ tại công viên văn hóa Sông Ray. Bờm có n mặt hàng. Các mặt hàng được đánh số từ 1 đến n. Mặt hàng thứ i có giá bán là a_i .Để kích thích nhiều người mua hàng của mình, Bờm muốn tất cả các mặt hàng đều có đồng chung một giá.

Bờm không muốn thua lỗ vì vậy Bờm muốn chọn giá theo cách sao cho tổng giá mới không thấp hơn tổng giá ban đầu. Điều đó có nghĩa là nếu Bờm bán tất cả n hàng hóa với giá mới, Bờm sẽ nhận được  tổng số tiền tương đương (hoặc lớn hơn) so với giá ban đầu. Mặt khác, Bờm không muốn khách hàng chê đắt nên trong số tất cả các mức giá có thể chọn, Bờm cần chọn mức giá tối thiểu.

Input: file donggia.inp gồm 2 dòng

-dòng 1: số nguyên n (0<n<10⁷)

-dòng 2: ghi n số nguyên a_i. (0<a_i<=10³). Mỗi số cách nhau 1 khoảng trắng

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

-ghi một số nguyên là giá bán mới của n mặt hàng

Input	output
5 1 2 3 4 5	3
3 2 2 2	2

Read More

Ô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

Read More