Luyện Tập #21

Bộ đề bài

Trở lại kỳ thi

1. Nhà máy

Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Nhà máy

Một nhà máy có \(n\) máy có thể được sử dụng để sản xuất sản phẩm. Mục tiêu của bạn là sản xuất tổng cộng \(t\) sản phẩm.

Với mỗi máy, bạn biết số giây mà máy đó cần để sản xuất một sản phẩm. Các máy có thể hoạt động đồng thời và bạn có thể tự do quyết định lịch hoạt động của chúng.

Hãy xác định thời gian ngắn nhất cần thiết để sản xuất đủ \(t\) sản phẩm.

Input

Dòng đầu tiên chứa hai số nguyên \(n\) và \(t\): số lượng máy và số lượng sản phẩm cần sản xuất.

Dòng tiếp theo chứa \(n\) số nguyên:

\[ k_1, k_2, \ldots, k_n \]

Trong đó \(k_i\) là thời gian cần thiết để máy thứ \(i\) sản xuất một sản phẩm.

Output

In ra một số nguyên duy nhất: thời gian nhỏ nhất cần thiết để sản xuất đủ \(t\) sản phẩm.

Giới hạn

  • \(1 \le n \le 2 \cdot 10^5\)
  • \(1 \le t \le 10^9\)
  • \(1 \le k_i \le 10^9\)

Sample Input

3 7
3 2 5

Sample Output

8

Giải thích

Trong \(8\) giây:

  • Máy thứ nhất sản xuất được \(2\) sản phẩm.
  • Máy thứ hai sản xuất được \(4\) sản phẩm.
  • Máy thứ ba sản xuất được \(1\) sản phẩm.

Tổng cộng, ba máy sản xuất được \(7\) sản phẩm.

2. Chia mảng

Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Chia mảng

Bạn được cho một mảng gồm \(n\) số nguyên dương.

Nhiệm vụ của bạn là chia mảng thành \(k\) đoạn con liên tiếp sao cho tổng lớn nhất trong một đoạn con là nhỏ nhất có thể.

Input

Dòng đầu tiên chứa hai số nguyên \(n\) và \(k\): kích thước của mảng và số lượng đoạn con cần chia.

Dòng tiếp theo chứa \(n\) số nguyên:

\[ x_1, x_2, \ldots, x_n \]

Đây là các phần tử của mảng.

Output

In ra một số nguyên duy nhất: tổng lớn nhất của một đoạn con trong cách chia tối ưu.

Giới hạn

  • \(1 \le n \le 2 \cdot 10^5\)
  • \(1 \le k \le n\)
  • \(1 \le x_i \le 10^9\)

Sample Input

5 3
2 4 7 3 5

Sample Output

8

Giải thích

Một cách chia tối ưu là:

\[ [2,4],\ [7],\ [3,5] \]

Tổng của các đoạn con lần lượt là:

\[ 6,\ 7,\ 8 \]

Tổng lớn nhất là \(8\).

3. Chia phòng khách sạn

Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Chia phòng khách sạn

Có một khách sạn lớn và \(n\) khách hàng sắp đến. Mỗi khách hàng muốn ở trong một phòng riêng.

Bạn biết ngày đến và ngày rời đi của từng khách hàng. Hai khách hàng có thể sử dụng cùng một phòng nếu ngày rời đi của khách hàng thứ nhất sớm hơn ngày đến của khách hàng thứ hai.

Hãy xác định số lượng phòng ít nhất cần thiết để phục vụ tất cả khách hàng và cách phân phòng cho từng người.

Input

Dòng đầu tiên chứa số nguyên \(n\): số lượng khách hàng.

Trong \(n\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(a\) và \(b\): ngày đến và ngày rời đi của một khách hàng.

Output

Dòng đầu tiên in ra số nguyên \(k\): số lượng phòng ít nhất cần sử dụng.

Dòng thứ hai in ra \(n\) số nguyên. Số thứ \(i\) là số phòng được phân cho khách hàng thứ \(i\) theo đúng thứ tự xuất hiện trong dữ liệu vào.

Các phòng được đánh số:

\[ 1, 2, \ldots, k \]

Bạn có thể in ra bất kỳ cách phân phòng hợp lệ nào.

Giới hạn

  • \(1 \le n \le 2 \cdot 10^5\)
  • \(1 \le a \le b \le 10^9\)

Sample Input

3
1 2
2 4
4 4

Sample Output

2
1 2 1

4. FROG

Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 0B Input: bàn phím Output: màn hình

FROG

Có \(N\) hòn đá được đánh số từ \(1\) đến \(N\). Hòn đá thứ \(i\) có độ cao là \(h_i\).

Một chú ếch ban đầu đứng ở hòn đá số \(1\). Chú ếch sẽ thực hiện một số lần các hành động sau để đến được hòn đá số \(N\):

  • Nếu đang đứng ở hòn đá \(i\), chú ếch có thể nhảy đến hòn đá \(i+1\) hoặc hòn đá \(i+2\).
  • Khi nhảy từ hòn đá \(i\) đến hòn đá \(j\), chi phí của bước nhảy là:
\[ |h_i-h_j| \]

Hãy tìm tổng chi phí nhỏ nhất để chú ếch đi đến hòn đá số \(N\).

Input

Dữ liệu vào được cho theo định dạng:

N
h1 h2 ... hN

Output

In ra một số nguyên duy nhất: tổng chi phí nhỏ nhất để chú ếch đến được hòn đá số \(N\).

Giới hạn

  • Tất cả các giá trị trong dữ liệu vào đều là số nguyên.
  • \(2 \le N \le 10^5\)
  • \(1 \le h_i \le 10^4\)

Sample Input

4
10 30 40 20

Sample Output

30

Giải thích

Nếu chú ếch đi theo đường:

\[ 1 \rightarrow 2 \rightarrow 4 \]

thì tổng chi phí là:

\[ |10-30|+|30-20|=30 \]

5. Mảng tăng dần

Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Mảng tăng dần

Bạn được cho một mảng gồm \(n\) số nguyên. Bạn muốn thay đổi mảng sao cho mảng trở thành không giảm, nghĩa là mỗi phần tử phải lớn hơn hoặc bằng phần tử đứng ngay trước nó.

Trong mỗi thao tác, bạn có thể tăng giá trị của một phần tử lên \(1\).

Hãy xác định số thao tác ít nhất cần thực hiện.

Input

Dòng đầu tiên chứa số nguyên \(n\): kích thước của mảng.

Dòng thứ hai chứa \(n\) số nguyên:

\[ x_1, x_2, \ldots, x_n \]

Đây là các phần tử của mảng.

Output

In ra một số nguyên duy nhất: số thao tác ít nhất cần thực hiện.

Giới hạn

  • \(1 \le n \le 2 \cdot 10^5\)
  • \(1 \le x_i \le 10^9\)

Sample Input

5
3 2 5 1 7

Sample Output

5

6. Số bị thiếu

Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Số bị thiếu

Bạn được cho tất cả các số nguyên từ \(1\) đến \(n\), ngoại trừ một số bị thiếu.

Nhiệm vụ của bạn là tìm số bị thiếu đó.

Input

Dòng đầu tiên chứa số nguyên \(n\).

Dòng thứ hai chứa \(n-1\) số nguyên phân biệt. Mỗi số đều nằm trong đoạn từ \(1\) đến \(n\).

Output

In ra số nguyên bị thiếu.

Giới hạn

  • \(2 \le n \le 2 \cdot 10^5\)

Sample Input

5
2 3 1 5

Sample Output

4