Chia kem cho những đứa trẻ

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Xem hướng dẫn
Tác giả:
algorit , bin9638
Dạng bài
Điểm: 300 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Sau khi xem xong MV "Ice Cream" của Blackpink, bin9638 và algorit liền đặt ngay vé máy bay sang Hàn Quốc để có thể ăn kem tại quán và nói chuyện với các idol của mình. Lúc bin9638 và algorit tới quán kem "Blackpink" thì đúng lúc quán kem này đang có chương trình phát kem cho các em nhỏ. Cụ thể, có \(n\) đứa trẻ lần lượt có độ tuổi là \(A_1 , A_2 , ... , A_n\) đang đứng trước quán chờ nhận kem, đứa trẻ thứ \(i\) có độ tuổi là \(A_i\) . Chương trình phát kem của Blackpink cũng rất đặc biệt, mỗi đứa trẻ phải có ít nhất \(1\) que kem , khi có \(2\) đứa trẻ đứng gần nhau , đứa trẻ lớn hơn sẽ được phát nhiều kem hơn, nếu \(2\) đứa trẻ cùng tuổi đứng cạnh nhau thì phát tùy ý. Tuy nhiên vì còn phải đi phát kem ở nhiều nơi nữa nên Blackpink muốn số kem được phát là tối thiểu.

Lisa, quản lí của quán kem này biết bin9638 và algorit là những người rất thông minh nên muốn nhờ họ tính giúp số kem tối thiểu cần phát. Nếu tính được thì bin9638 và algorit sẽ được tặng \(2\) que kem, hơn nữa họ còn sẽ được chụp ảnh chung và có được chữ kí của Blackpink nữa đấy. Hãy giúp họ nhé !

Yêu cầu:

  • Hãy tìm số lượng kem tối thiểu đề chia cho \(n\) đứa trẻ.

Input:

  • Dòng đầu tiên gồm \(1\) số nguyên dương \(n\) . \((n \le 10^6)\)
  • Dòng thứ \(2\) là dãy số \(A_1 , A_2 , ... , A_n\) là độ tuổi của nhứng đứa trẻ . \((A_i \le 10^9)\)

Output:

  • Dòng đầu tiên gồm một số nguyên dương duy nhất là số lượng kem tối thiểu.
  • Dòng thứ \(2\) là dãy \(C_i\) tương ứng với số kem phát cho đứa trẻ thứ \(i\).

Scoring:

  • Subtask \(1\) (\(40\%\) số điểm): \(n \le 10^3\)
  • Subtask \(2\) (\(60\%\) số điểm): không có ràng buộc gì thêm.

Example

Test 1

Input 
5
1 2 1000000000 2 1
Output 
9
1 2 3 2 1

Test 2

Input 
3
1 2 2
Output 
4
1 2 1

Bình luận


  • 3
    Lê_Gia_Khánh    7:25 p.m. 14 Tháng 9, 2020

    Dòng thứ 2 là dãy số 𝐴1,𝐴2,...,𝐴𝑛 là độ tuổi của nhứng đứa trẻ . (𝐴𝑖≤10e9)
    Có mấy đứa bé dưới 1 triệu tuổi luôn :))


    • -5
      daicaduc    10:43 p.m. 6 Tháng 4, 2021

      Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.


      • 4
        N7hoatt    10:36 p.m. 16 Tháng 9, 2020

        dưới triệu tuổi là sao bro


        • 4
          Toilaaibanbietko7A4    8:21 a.m. 11 Tháng 11, 2020 ← chỉnh sửa 4

          Dưới 1 tỉ tuổi chứ! (10^\(9\)= 1.000.000.000 là 1 tỉ)


        • 6
          bin9638    9:10 p.m. 14 Tháng 9, 2020

          bất tử

          2 bình luận nữa