game box tin - Chém code như chém gió

T

thienvamai

N nhỏ thì đếm trâu được
còn N lớn phải cài IT (hay BIT gì đấy không nhớ vì t chưa cài đc )
 
T

thienvamai

mời mọi người chém

Sửa tường : ma trận kích thước M hàng, N cột biểu diễn tường, 1-tường tốt,
0-tường hỏng.

1110000111
1100001111
1000000011
1111101111
1110000111


Sửa = cách đặt các khối thẳng đứng vào các vùng hỏng. Các khối có thể sử dụng
có độ rộng 1 và chiều cao có thể là {1,2, ..., M}.

Cần xác định số khối từng loại sao cho số lượng khối là ít nhất.


Input
Dòng đầu là hai số M và N (1 <= M, N <= 200). M dòng sau đó gồm N kí tự
1 hoặc 0.

Sample Input
5 10
1110000111
1100001111
1000000011
1111101111
1110000111


Output

Xác định số khối cần sử dụng đối với từng chiều cao
k Ck

với k ∈ {1,2, ..., M} là chiều cao của khối và Ck là số khối cần sử dụng.
Không in ra các dòng có Ck = 0 và in ra theo thứ tự tăng dần của k.

Sample output
1 7
2 1
3 2
5 1
 
E

englandhuynh

@Sửa tường : bài này cho xét từng phần tử, nếu a[i,j]=0 và a[i-1,j]=1 thì đếm các phần tử = 0 bên dưới a[i,j]
 
T

thienvamai

mời mọi người chém tiếp
Cho 1 dãy số gồm N phần tử (N ≤ 10000), mỗi phần tử có 1 giá trị nằm trong khoảng [-1000, 1000]. Ban đầu, bạn sẽ ở vị trí ô số 0 với tổng điểm là 0. Mỗi nước đi, người chơi có thể di chuyển sang phải tối thiểu là 1 bước và tối đa là K bước (K ≤ 10) . Khi dừng lại ở 1 ô nào đó thì giá trị của ô đó sẽ được cộng vào tổng điểm. Bạn có thể dừng cuộc chơi bất cứ lúc nào. Hãy tìm cách chơi sao cho tổng điểm nhận được là nhiều nhất.
Dữ liệu vào

Dòng đầu tiên chứa 2 số N, K.

Dòng thứ 2 chứa N số của dãy, mỗi số cách nhau 1 dấu cách. Mỗi số nằm trong khoảng [-1000, 1000]

Dữ liệu ra

Số điểm lớn nhất có thể đạt được.

Giới hạn:

N ≤ 10000.
K ≤ 10.
Trong 20% số test có N ≤ 10

Ví dụ

Input:
5 2
-2 3 -6 -4 5

Output:
4

Giải thích:
- Ta có thể đi theo thứ tự 0 -> 2 -> 4 -> 5. Số điểm đạt được là 0 + 3 - 4 + 5 = 4.
Bấm để xem đầy đủ nội dung ...
 
M

mikelhpdatke

Đang ôn thi THT thấy bài này tạm tạm post lên





ĐỀ:
Khi đào hầm Thủ Thiêm người ta dùng một Robot để đào, ban đầu người ta đào đường hầm 1 đơn vị độ dài sau đó đặt Robot xuống. Robot này được điều khiển bởi 2 lệnh là: C1 v N2.
- Lệnh C1 là đào thêm 1 đơn vị độ dài thì tốn 2 đơn vị năng lượng.
- Lệnh N2 là đào thêm một đoạn đường hầm bằng độ dài đang có thì tốn 4 đơn vị năng lượng.
Hãy viết chương trình ra lệnh cho Robot đào một đường hầm có độ dài k đơn vị độ dài với các lệnh là ít nhất và sự tiêu tốn năng lượng là thấp nhất. Biết ban đầu đường hầm dài 1 đơn vị độ dài.
Yêu cầu:
- Dữ liệu vào gồm một số k là độ dài đường hầm cần đào.
- Dữ liệu ra gồm hai dòng:
+ Dòng đầu là số năng lượng ít nhất đã tiêu tốn cho Robot đào hầm.
+ Dòng tiếp theo chứa các lệnh C1 hoặc N2, mỗi lệnh cách nhau 1 khoảng trắng.
 
T

thienvamai

mikelhpdatke said:
Đang ôn thi THT thấy bài này tạm tạm post lên





ĐỀ:
Khi đào hầm Thủ Thiêm người ta dùng một Robot để đào, ban đầu người ta đào đường hầm 1 đơn vị độ dài sau đó đặt Robot xuống. Robot này được điều khiển bởi 2 lệnh là: C1 v N2.
- Lệnh C1 là đào thêm 1 đơn vị độ dài thì tốn 2 đơn vị năng lượng.
- Lệnh N2 là đào thêm một đoạn đường hầm bằng độ dài đang có thì tốn 4 đơn vị năng lượng.
Hãy viết chương trình ra lệnh cho Robot đào một đường hầm có độ dài k đơn vị độ dài với các lệnh là ít nhất và sự tiêu tốn năng lượng là thấp nhất. Biết ban đầu đường hầm dài 1 đơn vị độ dài.
Yêu cầu:
- Dữ liệu vào gồm một số k là độ dài đường hầm cần đào.
- Dữ liệu ra gồm hai dòng:
+ Dòng đầu là số năng lượng ít nhất đã tiêu tốn cho Robot đào hầm.
+ Dòng tiếp theo chứa các lệnh C1 hoặc N2, mỗi lệnh cách nhau 1 khoảng trắng.
Bấm để xem đầy đủ nội dung ...

F là số năng lượng tiêu tốn ít nhất
F=min(F[i-1]+2,F[i/2]+4)
 
T

thienvamai

Cho một dãy số nguyên gồm N phần tử A[1], A[2], ... A[N].
Biết rằng dãy con tăng đơn điệu là 1 dãy A[i1],... A[ik] thỏa mãn
i1 < i2 < ... < ik và A[i1] < A[i2] < .. < A[ik]. Hãy cho biết dãy con tăng đơn điệu dài nhất của dãy này có bao nhiêu phần tử?
Input

Dòng 1 gồm 1 số nguyên là số N (1 ≤ N ≤ 1000).
Dòng thứ 2 ghi N số nguyên A[1], A[2], .. A[N] (1 ≤ A ≤ 10000).

Output

Ghi ra độ dài của dãy con tăng đơn điệu dài nhất.
Ví dụ

Input:
6
1 2 5 4 6 2

Output:
4
 
M

mikelhpdatke

thienvamai said:
Cho một dãy số nguyên gồm N phần tử A[1], A[2], ... A[N].
Biết rằng dãy con tăng đơn điệu là 1 dãy A[i1],... A[ik] thỏa mãn
i1 < i2 < ... < ik và A[i1] < A[i2] < .. < A[ik]. Hãy cho biết dãy con tăng đơn điệu dài nhất của dãy này có bao nhiêu phần tử?
Input

Dòng 1 gồm 1 số nguyên là số N (1 ≤ N ≤ 1000).
Dòng thứ 2 ghi N số nguyên A[1], A[2], .. A[N] (1 ≤ A ≤ 10000).

Output

Ghi ra độ dài của dãy con tăng đơn điệu dài nhất.
Ví dụ

Input:
6
1 2 5 4 6 2

Output:
4
Bấm để xem đầy đủ nội dung ...


F là độ dài dãy con đơn điệu dài nhất kết thúc tại i
F:=Max(F[j])+1, A[j]<A với j:=1->i-1
KQ bài toán là maxF với i:1->n
 
T

thienvamai

không chỉ vậy tang biến lên tương đương với việc tang thời gian chạy 1, thuật toán mà phải tính toán ~10^12 phép tính thì quả là ko tối ưu
 
T

thienvamai

Nhà trường có một phòng hội trường. Có những yêu cầu muốn sử dụng phòng hội trường này, mỗi yêu cầu cho biết thời điểm bắt đầu và thời điểm kết thúc. Nhà trường có thể chấp nhận hoặc từ chối đối với một yêu cầu.

Yêu cầu: hãy giúp nhà trường chọn các yêu cầu sử dụng hội trường sao cho tổng thời gian hội trường được sử dụng là lớn nhất.
Dữ liệu

Dòng đầu tiên chứa một số nguyên dương n (n ≤ 10000), số yêu cầu.

Mỗi dòng trong số n dòng tiếp theo chứa 2 số nguyên dương p và k (0 ≤ p < k ≤ 30000), mô tả một yêu cầu bắt đầu tại thời điểm p và kết thúc tại thời điểm k.
Kết qủa

Gồm một dòng duy nhất là tổng thời gian lớn nhất mà hội trường được sử dụng
Ví dụ

Dữ liệu:
12
1 2
3 5
0 4
6 8
7 13
4 6
9 10
9 12
11 14
15 19
14 16
18 20

Kết qủa
16
 
You must log in or register to reply here.
Top Bottom