---
# System prepended metadata

title: Ngày 19/08

---

# Ngày 19/08

STUPIDBIRD - Con chim ngu ngốc của Khải
---

Các bạn có biết trò chơi gây nghiện **Flappy Bird** của **Nguyễn Hà Đông** không? Trong bài ngày hôm nay của chúng ta có một con chim ngu ngốc bay vào một cái hang với các chướng ngai vật là các măng đá (mọc lên từ đáy hang) và nhũ đã (nhô xuống từ trần hàng).

![](https://hackmd.io/_uploads/SJW85i6nn.png)


Con chim này của **Khải** không biết bay lên xuống để tránh các chướng ngại vật như con chim của **Nguyễn Hà Đông** mà thay vào đó, nó sẽ chọn một mức chiều cao bắt đầu rồi bay từ đầu đến cuối hang, phá hết tất cả các chướng ngại vật trên đường bay của nó.

![](https://hackmd.io/_uploads/B1zv9jp3n.png)


Nếu chọn bay ở những độ cao khác nhau thì số chướng ngại vật nó phải phá là khác nhau. Theo ví dụ trên, nếu chọn mức 4, con chim sẽ phá tất cả là 
 8 chướng ngại vật. Đây không phải là lựa chọn tốt nhất vì con chim sẽ ít mệt hơn nếu chọn mức 1 hoặc mức 5, lúc này nó chỉ cần phá 7 chướng ngại vật.

Bạn được cho biết số N là số chướng ngại vật, H là chiều cao của hang, thông tin về các chướng ngại vật. Hãy xác định số chướng ngại vật tối thiểu mà con chim cần phá để đi qua hang.

* Input
Dòng đầu chứa hai số nguyên dương N và H được ghi cách nhau một dấu cách.
Dòng thứ hai chứa N số nguyên l1,l2, l3 ...  khác 0, hai số liên tiếp được ghi cách nhau một dấu cách. Nếu li > 0 thì đó là măng đá mọc lên từ đáy hang với độ dài li, nếu li< 0 thì đó là nhũ đá nhô xuống từ trần hang với độ dài li

* Output
Ghi trên một dòng số nguyên là số chướng ngại vật tối thiểu cần xuyên phá.

Ex1:
```
Input: 
6 7
1 3 -5 -3 5 -1

Output: 2
```

Ex2:

```
Input:
14 5
1 -3 4 -2 2 -4 3 -4 3 -3 3 -2 3 -3

Output: 7
```


---


# FROG - Con ếch của Hiếu Thư Thái


---
**Hiếu thư thái** đã chế tạo 1 chú ếch máy có thể nhảy k bước với độ dài khác nhau (**b**1,**b**2,**b**3 ..., **b***k*) trên đoạn đường thẳng. Siro đặt ếch trên đoạn đường thắng tại vạch xuất phát 0.

Bạn hãy cho Siro biết số cách nhảy để con ếch đến được điểm N.

### Input
Dòng đầu tiên ghi 2 số nguyên dương N và k
Dòng thứ 2 ghi k  số nguyên dương (**b**1,**b**2,**b**3 ..., **b***k*)

### Output
Gồm 1 số nguyên dương duy nhất là số cách để con ếch đến được điểm N nói trên.

#### Ex

```
Input: 
8 2
2 3

Output: 4


Input: 
10 3
3  5  6

Output: 1


```

# Cột đèn của người nông dân Tùng Ấu


---
Nông dân **Tùng ấu** có một mảnh đất kích thức M x N, mảnh đất được chia thành các ô nhỏ có kích thước 1 x 1, do vừa trồng một loại cây đặc biệt chỉ phát triển dưới ánh điện huỳnh quang. Một bóng đèn huỳnh quang có thể chiếu sáng tối đa 4 ô vuông xung quanh nó. Vì không có nhiều tiền nên **Tùng ấu** muốn tìm số cột đèn ít nhất cần phải dùng để chiếu sáng cả mảnh đất.Vì không giỏi tính toán nên anh ấy muốn các bạn SD team giúp đỡ. Hãy giúp  **Tùng ấu**  nhé!

```
Input: 2 2

Output: 1


Input: 5 6

Output: 9
```
