Skip to content
Narrow screen resolution Wide screen resolution Auto adjust screen size Increase font size Decrease font size Default font size default color grey color
         
 | 
VNOI - Olympic tin học Việt Nam

Điểm tin VOJ

Số thành viên:6040
Số bài tập:1001
Số bài nộp:722923
Bài nộp hôm nay:0

Top 10 thành viên xuất sắc

HạngThành viênĐiểm
1mr_invincible587.9
2white_cobra418.6
3hieult403.4
4phaleq384.0
5vodanh9x368.2
6con_nha_ngheo352.0
7flash_mt350.2
8darksabers349.8
9yenthanh132345.3
10rockman9x_94343.1
2. Các cửa hàng In E-mail
(4 votes)
Người viết: Ngô Minh Đức   
27/03/2008
Chủ chung cư Sao Khuê cho thuê dãy N cửa hàng được đánh số từ 1 đến N từ trái qua phải. Năm đầu tiên giá thuê cửa hàng thứ i là ai đồng. Theo dòng thời gian, có cửa hàng làm ăn phát đạt, có cửa hàng làm ăn thua lỗ. Chủ các cửa hàng làm ăn phát đạt tìm cách thuê thêm diện tích của cửa hàng liền kề để mở rộng công việc kinh doanh. Như vậy có cửa hàng phải đóng cửa, có cửa hàng được mở rộng. Khi một cửa hàng i phát triển và thuê thêm diện tích của cửa hàng j liền kề nó (j=i−1 hoặc j=i+1), tiền thuê cửa hàng i sẽ được tính theo qui tắc sau:
  • Nếu ai mod 3 = 0, thì tiền thuê mới là ai + aj.
  • Nếu ai mod 3 = 1, thì tiền thuê mới là 2ai + (aj div 2).
  • Nếu ai mod 3 = 2, thì tiền thuê mới là 4ai + (aj div 4).

Theo luật của chủ chung cư Sao Khuê, mỗi một năm chỉ có không quá một cửa hàng được phép mở rộng và khi có cửa hàng mở rộng dãy các cửa hàng được đánh số lại bắt đầu từ 1 từ trái qua phải. Sau N−1 năm, chủ chung cư Sao Khuê giật mình khi phát hiện ra rằng chỉ còn lại duy nhất một cửa hàng ở chung cư. Để tìm hiểu quá trình phát triển của cửa hàng, chủ chung cư đã tìm đến sổ sách. Đáng tiếc là do sự bất cẩn của kế toán, sổ sách ghi nhận chi tiết đã bị thất lạc, chỉ còn lại giá thuê các cửa hàng trong năm đầu tiên và năm thứ N−1.

Yêu cầu: Hãy giúp chủ chung cư Sao Khuê khôi phục thông tin về quá trình phát triển của cửa hàng hiện nay.

Dữ liệu

  • Dòng đầu tiên ghi số N.
  • Dòng thứ hai chứa dãy số nguyên dương a1, a2, ..., aN.
  • Dòng thứ ba chứa số nguyên là số tiền thuê cửa hàng hiện nay.

Kết qủa

Ghi ra N−1 dòng, dòng thứ i chứa hai số nguyên theo thứ tự là chỉ số của cửa hàng mở rộng và cửa hàng đóng cửa trong năm thứ i, i=1, 2, ..., N−1. (Nếu có nhiều cách khôi phục, chỉ cần đưa ra một cách tùy ý).

Giới hạn

  • Dữ liệu luôn đảm bảo có ít nhất một cách khôi phục.
  • Trong tất cả các test: 1 ≤ N ≤ 30; ai ≤ 32000, i =1, 2, ..., N.
  • Có 50% số lượng test với N ≤ 15.

Ví dụ

<strong>Dữ liệu:</strong>
3
3 2 4
21
 
<strong>Kết qủa</strong>
1 2
1 2
 
< Trước   Tiếp >