CHIA ĐOẠN SỐ NGUYÊN

Steve có nhiệm vụ chuẩn bị một đề đơn giản cho kỳ thi lập trình. Steve có ý định sẽ ra một đề không những rất dễ mà còn nhàm chán nữa: Cho danh sách các số nguyên không âm, yêu cầu tính tổng của chúng.

Đúng là không nên đùa với lửa. Sự nhàm chán của đề tác động vào ngay chính Steve khi anh chuẩn bị dữ liệu. Anh phạm một sai lầm thô thiển – quên đưa các dấu cách giữa các số. Steve nhanh chóng nhận ra sai lầm khi xem lại dữ liệu vào. Thay vì danh sách có các số nguyên trong file thì chỉ chứa một xâu các ký tự số.

Steve nảy ra ý nghĩa sửa lại đề thành một bài có nội dung hấp dẫn hơn và không tầm thường: Tổng lớn nhất có thể nhận được là bao nhiêu nếu ta chia xâu này thành các số không chứa các số 0 không có nghĩa và mỗi số có thể biểu diễn ở dạng  32 bít có dấu.

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

+ Dòng đầu tiên chứa số nguyên T – số test (1≤T≤500)

+ Mỗi dòng trong T dòng tiếp theo chứa một xâu các ký tự số độ dài không quá 200.

Kết quả: Đưa ra tệp văn bản PART.OUT kết quả mỗi test đưa ra trên một dòng dưới dạng số nguyên.

Ví dụ:

PART.INP	PART.OUT
8 6 123 2345346457567421363564564 6356413244123153456574254563325236 2353576857 235235 357588978089089 2456876895436346568	6 123 2671002524 2739216082 353576859 235235 978446677 978932301

ROUTE

Cho lưới ô vuông A kích thước m´n, các hàng được đánh số từ 1 đến m từ trên xuống dưới, các cột được đánh số từ trái sang phải, từ 1 đến n. Mỗi ô của lưới chứa một số nguyên có giá trị tuyệt đối không vượt quá 10⁹.

Từ một ô có thể đi sang ô kề cạnh bên phải hoặc xuống dưới. Xét các đường đi theo quy tắc trên từ ô trên trái xuống ô dưới phải. Tổng các số trên những ô đã đi qua là giá trị của đường đi.

Hãy xác định giá trị lớn nhất có thể đạt được.

Dữ liệu: Vào từ file route.inp, dòng đầu tiên chứa 2 số nguyên m và n (2 £ m, n £ 1000), mỗi dòng trong m dòng sau chứa n số nguyên xác định một dòng của bảng.

Kết quả: Đưa ra file route.out một số nguyên – giá trị max tìm được.

Ví dụ:

ROUTE.INP	ROUTE.OUT
5 6 2 6 8 1 – 5 9 9 1 7 3 6 4 -2 0 5 1 8 -6 1 4 0 3 0 4 9 -2 4 5 -4 2	46

LÁT GẠCH

Nguồn: spoj

Cho một hình chữ nhật kích thước 2xN (1<=N<=100). Hãy đếm số cách lát các viên gạch nhỏ kích thước 1x2 và 2x1 vào hình trên sao cho không có phần nào của các viên gạch nhỏ thừa ra ngoài, cũng không có vùng diện tích nào của hình chữ nhật không được lát.

Dữ liệu vào:

Gồm nhiều test, dòng đầu ghi số lượng test T ( T<=100 ).
T dòng sau mỗi dòng ghi một số N.

Dữ liệu ra:

Ghi ra T dòng là số cách lát tương ứng.

Example

Input:

3

1

2

3

Output:

1

2

3

Tính ngày

Hôm nay là ngày d1 tháng m1 năm y. Phần mềm thử nghiệm mà bạn tải từ mạng về chỉ được sử dụng đến hết ngày d2 tháng m2 của năm nay.

Hãy xác định số lượng ngày còn lại bạn có thể sử dụng phần mềm này, biết rằng 2012 £ y £ 2099 (trong khoảng thời gian này những năn chia hết cho 4 đều là năm nhuận).

Dữ liệu: Vào từ file rem_d.inp:

+ Dòng đầu tiên chứa số nguyên y,

+ Dòng thứ 2 chứa 2 số nguyên d1 và m1,

+ Dòng thứ 3chứa 2 số nguyên d2 và m2.

Dữ liệu hợp lệ, không cần kiểm tra.

Kết quả: Đưa ra file rem_d.out một số nguyên – số ngày còn lại bạn có thể sử dụng phần mềm.

REM_D.INP	REM_D.OUT
2012 25 1 26 3	61

LỌC SỐ

Lập trình đọc số nguyên n và dãy số nguyên A=(a₁, a₂, . . ., a_n).

Người ta lọc dãy số dãy số A bằng cách sau: với các số giống nhau chỉ giữ lại một số làm đại diện.

Hãy xác định dãy A sau khi lọc.

Dữ liệu: Vào từ file NUMFILTER.INP:

  Dòng đầu tiên chứa số nguyên n (1£ n £ 10⁵),

  Dòng thứ 2 chứa n số nguyên a₁, a₂, . . ., a_n, các số ghi cách nhau một dấu cách, |a_i| £ 10⁹, i = 1 ¸ n.

Kết quả: đưa ra file NUMFILTER.OUT:

Dòng đầu tiên là số nguyên m – số phần tử của dãy A mới,

Dòng thứ 2 chứa các phần tử của A sau khi lọc.

NUMFILTER.INP	NUMFILTER.OUT
8 2 1 4 2 6 4 2 3	5 1 2 3 4 6

BEAR AND DISPLAYED FRIENDS

Nguồn http://codeforces.com/contest/639/problem/A

Limak là một chú gấu Bắc cực, nó kết nối với bạn bè thông qua mạng xã hội. Nó có n bạn bè và mối quan hệ của nó với người bạn thứ i được mô tả bằng 1 số nguyên t_i . Số t_i càng lớn thể hiện tình bạn càng lớn. Không có hai người bạn nào có cùng t_i.

Mùa xuân đến báo hiệu kỳ ngủ đông đã kết thúc. Limak vừa thức dậy đã đăng nhập vào mạng xã hội. Tất cả bạn bè của nó vẫn còn ngủ do đó không ai trong số họ trực tuyến. Một số hoặc tất cả bạn bè của nó sẽ trực tuyến trong thời gian tiếp theo.

Hệ thống hiện thị những người bạn đang trực tuyến. Trên màn hình chỉ hiện thị được k bạn bè, đó là những người bạn đang trực tuyến và có t_i lớn nhất.

Nhiệm vụ của bạn là xử lý các truy vấn gồm 2 loại:

“1 id” – id của người bạn mới trực tuyến, trước đó người bạn này chưa trực tuyến.

“2 id” – Kiểm tra xem id được hiện thị trên hệ thống hay không? In “YES” hoặc “NO” trong 1 dòng tương ứng là đang trực tuyến hoặc không trực tuyến.

Bạn có thể giúp Limak và trả lời tất cả các truy vân của loại thứ hai?

Dữ liệu vào:

+ Dòng đầu tiên chứa ba số nguyên n, k và q (1 ≤ n, q ≤ 150 000, 1 ≤ k ≤ min (6, n)) - số lượng bạn bè, số lượng tối đa của bạn bè trực tuyến hiển thị và số lượng các truy vấn.

+ Dòng thứ hai chứa n số nguyên t₁, t₂, ..., t_n (1 ≤ t_i ≤ 10⁹), nơi ti mô tả như thế nào tốt là mối quan hệ Limak với người bạn thứ i.

+ Dòng thứ i của q dòng tiếp theo chứa 2 số nguyên type_i và Id_i (1<=type_i<=2; Id_i<=n)  thể hiện truy vấn thứ i. Nếu Type_i=1 thì người bạn Id_i trực tuyến, nếu Id_i =2 thì bạn cần kiểm tra xem bạn Id_i được hiện thị hay không?

Dữ liệu đảm bảo một người chỉ trực tuyến nhiều nhất 1 lần và có ít nhất 1 truy vấn dạng “2 type_i”

Kết quả: Đối với mỗi truy vấn của loại thứ hai in một dòng với câu trả lời - "YES" (không có dấu ngoặc kép), nếu các bạn sẽ được hiển thị và "NO" (không có dấu ngoặc kép) trong trường hợp ngược lại.

Input	Output		Input	Output
4 2 8 300 950 500 200 1 3 2 4 2 3 1 1 1 2 2 1 2 2 2 3	NO YES NO YES YES		6 3 9 50 20 51 17 99 24 1 3 1 4 1 5 1 2 2 4 2 2 1 1 2 4 2 3	NO YES NO YES

Giải thích: Trong ví dụ 1

1.  "1 3" — bạn có Id=3 trực tuyến.

2.  "2 4" — Kiểm tra bạn có Id=4 trực tuyến chưa. Vẫn chưa trực tuyến nên ghi  "NO".

3.  "2 3" — Kiểm tra bạn có Id=3 trực tuyến chưa. Đang trực tuyến và được hiện thị. Ghi kết quả "YES".

4.  "1 1" — Bạn có Id=1 trực tuyến. Hệ thống hiện thị cả bạn 1 và 3.

5.  "1 2" — Bạn có Id=2 trực tuyến. Bây giờ có 3 bạn trực tuyến nhưng chỉ hiện thị được 2 (k=2). Limak có mối quan hệ tình bạn với người bạn thứ 2 và 3 tốt hơn (t₁ < t₂, t₃) do vậy ngươi bạn 1 không hiện thị

6.  "2 1" — ghi "NO".

7.  "2 2" — ghi "YES".

8.  "2 3" — ghi "YES".

Lớp 11 - Năm 2016 - Đề thi

Tin 11-Olympic30-4-2016_Đề thi by Hải Phong

Để lại Mail ở phần Comment đề nhận đề (file Word)

CHÚ TIỂU CHÙA HƯƠNG

Nguồn: Olympic 30/4 năm 2016 Lớp 10

Chùa Hương là một quần thể di tích thuộc địa phận xã Hương Sơn, huyện Mỹ Đức, thành phố  Hà Nội. Chùa Hương gồm nhiều chùa chiền (đáng chú ý nhất là chùa Thiên Trù) cùng với động Hương Tích rất nổi tiếng (được mệnh danh là Nam thiên đệ nhất động)

Chùa Thiên Trù									Động Hương Tích
	M=4							N=5
				Lưng chừng núi Lão

Vào mùa lễ hội (tháng Giếng đến tháng Ba âm lịch hàng năm), chú tiểu Bờm phải làm việc khá vất vả. Hằng ngày, Bờm phải từ chùa Thiên Trù xuống lưng chừng núi Lão rồi từ đố leo tiếp lên gần đỉnh nói đến động Hương Tích. Sau đó, từ động Hương Tích, Bờm quay lại chùa Thiên Trù theo con đường ban đầu. Con đường bao gồm 2 đoạn dãy bậc thang lát đá với số bạc lần lượt là  M và N (xem hình minh họa). Hành trình của Bờm như sau:

+ Từ chùa Thiên Trù đi xuống lưng chừng núi Lão cũng như từ đây đi lên động Hương Tích, vì đi người không nên Bờm có thể bước qua 1, 2 hoặc 3 bậc tùy thích.

+ Khi đi từ động Hương Tích xuống lưng chừng núi Lão, di phải gánh đồ nên Bờm chỉ có thể bước qua 1 hoặc 2 bậc đồng thời sử dụng đúng 1 làn bước qua 3 bậc tại vị trí tùy thích. Tuy nhiên, khi leo tiếp lên chùa Thiên Trù, Bờm chỉ có thể bước qua 1 hoặc 2 bậc mà thôi.

Yêu cầu: Hãy tính xem có thể có bao nhiêu cách để Bờm thực hiện một chuyến đi–về trong một ngày như vậy.

Dữ liệu vào: Từ tệp văn bản CHUTIEU.INP gồm nhiều dòng, mỗi dòng là một cặp giá trị của M và N (3≤M, N≤500).

Các số ghi trên cùng một dòng ghi cách nhau ít nhất là một ký tự trắng.

Kết quả: Ghi ra tệp văn bản CHUTIEU.OUT gồm nhiều dòng, mỗi dòng là kết quả tìm được ứng với cặp giá trị của M, N thuộc dòng tương ứng tệp dữ liệu vào.

Ví dụ:

CHUTIEU.INP	CHUTIEU.OUT
3 4 4 5 10 15 22 19	168 2275 321404553680 15760806775373345664

Ràng buộc: 50% số test ứng với 50% số điểm của bài có M≤20, N≤20.

TẢI TRỌNG TUYẾN ĐƯỜNG

Nguồn: Olympic 30/4 Lớp 10 năm 2016

Một hệ thống giao thông gồm n thành phố được đánh số từ 1 đến n. Hệ thống giao thông có m đoạn đường hai chiều nối giữa các thành phố (giữa hai thành phố bất kỳ luôn có đường đi). Mỗi đoạn đường có một tải trọng tối đa là z, cho biết các xe với tải trọng không lớn hơn z mới lưu thông được trên con đường đó.

Yêu cầu: Cho trước tải trọng của các đoạn đường trong hệ thống giao thông. Hãy tìm một hành trình từ thành phố s đến thành phố t sao cho tải trọng cho phép của xe lưu thông trên hành trình đó là lớn nhất có thể.

Dữ liệu vào: Cho từ tệp văn bản TAITRONG.INP gồm:

+ Dòng thứ nhất ghi 4 số nguyên n, m, s, t (2≤n≤10³; 1≤m≤10⁴; 1≤s, t≤n; s≠t)

+ Tiếp theo là m dòng, mỗi dòng ghi 3 số nguyên x, y, z với ý nghĩa có đoạn đường giữa thành phố x và thành phố y với tải trọng tối đa cho phép là z (1≤z≤10⁴)

Các số trên một dòng ghi cách nhau ít nhất 1 ký tự trắng

Kết quả: Ghi vào tệp văn bản TAITRONG.OUT gồm một dòng ghi số nguyên là tải trọng lớn nhất cần tìm.

Ví dụ:

TAITRONG.INP	TAITRONG.OUT
4 5 1 4 1 2 10 2 4 1 1 3 5 3 4 3 1 4 2	3

Ràng buộc: 50% số test tương ứng với 50% số điểm của bài có 2≤n≤100

QUÂN MÃ

Nguồn: Olympic 30/4 Lớp 10 năm 2016

Trong luật cờ vua, mỗi nước đi của quân mã được quy định như sau: quân mã đang ở vị trí X như hình vẽ bên dưới có thể di chuyển đến một trong các ô mà mũi tên chỉ đến (theo đường chéo của hình chữ nhật 2x3)

Yêu cầu: Cho trước bàn cờ kích thước n x m ô. Hãy đếm số nước đi ít nhất để quân mã di chuyển từ ô có tọa độ (x₁, y₁) đến ô có tọa độ (x₂, y₂). Trong trường hợp không đến được thì xuất giá trị -1.

Dữ liệu vào: Cho từ tệp văn bản QUANMA.INP gồm

+ Dòng 1 ghi 2 số nguyên dương n, m (2≤n, m ≤1000).

+ Dòng 2 ghi 2 số nguyên x₁, y₁ (1≤x₁≤n; 1≤y₁≤m)

+ Dòng 3 ghi 2 số nguyên x₂, y₂ (1≤x₂ ≤n; 1≤y₂≤m)

Các số trên cùng một dòng cách nhau ít nhất một ký tự trắng.

Kết quả: Ghi ra tệp văn bản QUANMA.OUT một số nguyên duy nhất cho biết số nước đi ít nhất để quân mã di chuyển từ ô (x₁, y₁) đến ô (x₂, y₂). Nếu không đến được thì ghi số -1.

Ví dụ:

QUANMA.INP	QUANMA.OUT
4 6 1 1 2 4	2