Đèn led

Xem PDF

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

Để chuẩn bị cho cuộc thi sáng tạo KHKT cấp trường sắp tới, nhóm bạn Việt – Nam đã đăng ký tham gia đề tài bảng hiển thị số bằng đèn LED. Nội dung cơ bản của đề tài gồm: Mỗi chữ số được hiển thị trong một khung chữ nhật với 7 ống đèn LED. Bằng cách bật các ống đèn LED thích hợp, ta có thể hiển thị chữ số bất kỳ. Số đèn sáng càng nhiều thì việc hiển thị chữ số đó càng tốn năng lượng. Ví dụ, hiển thị chữ số 9 sẽ tốn năng lượng hơn hiển thị chữ số 7.

Sau khi sản phẩm hoàn tất, nhóm các bạn này còn dư khá nhiều các khung hiển thị số và một cục pin nguồn. Dung lượng pin cho phép bật sáng \(n\) ống đèn LED. Nhóm các bạn này nghĩ ra cách dùng những thứ còn dư này để đánh đố các bạn trong lớp nhằm trêu ghẹo các bạn. Yêu cầu mà nhóm bạn này đặt ra là: hãy dùng pin bật đúng \(n\) ống đèn để hiển thị một số sao cho số hiển thị được phải có tổng chữ số là lớn nhất.

Yêu cầu: Hãy xác định tổng lớn nhất của các chữ số của số có thể bật sáng.

Input

  • Gồm một dòng chứa số nguyên \(n\) \((2 \leq n \leq 10^{6})\).

Output

  • Ghi một số nguyên là tổng lớn nhất đạt được.

Scoring

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

Example

Test 1

Input
7 
Output
11

Bình luận


  • 0
    nguyendanghau2006 9:53 a.m. 14 Tháng 2, 2022 đã chỉnh sửa

    ai giải thích test mẫu dùm em với được ko ạ

    1 phản hồi

    • -3
      new4letuantu 3:11 p.m. 17 Tháng 11, 2021

      ai giải thích e test mẫu được không ạ :v


      • 6
        tien_noob 6:57 p.m. 17 Tháng 1, 2021

        bài này các bạn thử viết từng số ra và số ống đèn cần để tạo ra từng con số ấy, ta sẽ thấy rằng ta nên ưu tiên xuất hiện các số 7, rồi đến đây các bạn tự greedy mà chia trường hợp làm tiếp nè không cần quá cao siêu đâu :b


        • 6
          NgJaBach 3:14 p.m. 6 Tháng 9, 2020

          Về cơ bản thì bài này chẳng khác gì xếp N que tăm để tạo nên số tổng chữ số lớn nhất :v