Olympic viết thư về lập trình

26

Olympic viết thư về lập trình

Vào ngày 17 tháng 2 năm 1985, Trung tâm Giáo dục và Sản xuất Khoa học Máy tính ở Quận Oktyabrsky của Moscow và Viện Máy điều khiển Điện tử của Liên Xô Minipibor và Các vấn đề Thông tin (thứ sáu) Olympic Thành phố Moscow về Lập trình dành cho học sinh, trong đó có khoảng 200 người tham gia.

Tạp chí «Kvant» cung cấp cho tất cả học sinh và học sinh trường dạy nghề biết lập trình (trừ Moscow) bài toán của Kỳ thi Olympic này như một bài tập cho Kỳ thi Olympic Lập trình Tương ứng. Lời giải gửi chậm nhất vào ngày 1 tháng 8 (qua bưu điện ITEM PEL) đến địa chỉ «Kvant», trên phong bì ghi: “Lập trình Olympic”. Đã gửi lời giải sẽ được đánh giá bởi ban giám khảo do Tiến sĩ Vật lý và Toán học A. L. Brudno chủ trì. Tất cả những người tham gia sẽ được gửi phản hồi về công việc của họ. Những người chiến thắng sẽ nhận được Chứng chỉ tạp chí «Kvant».

Xin lưu ý rằng lỗi chính tả sẽ làm giảm điểm lời giải. Các thuật toán có số lượng hành động hoặc mảng quá mức có thể được loại bỏ cũng bị giảm khả năng đánh giá. Các thuật toán tốt và chương trình được viết tiết kiệm sẽ nâng cao điểm số của bạn. Trong mỗi tác phẩm, chỉ có 3 bài toán có giải pháp tốt hơn được đọc.

Các nhiệm vụ được liệt kê theo thứ tự độ khó giảm dần. lời giải bằng mọi ngôn ngữ lập trình đều được chấp nhận. Di chuyển lời giải cần đưa ra mô tả phức tạp về thuật toán.

Bài toán

1. Phân hủy thành các điều khoản. In tất cả các cách biểu diễn số tự nhiên $n$ bằng tổng các số tự nhiên. Sắp xếp lại các từ theo cách mới không được tính.

2. Các phần tử bằng nhau. Một dãy số $P[1:m, 1:n]$ được đưa ra. Mỗi hàng của mảng được sắp xếp theo thứ tự tăng dần. Tìm và in số xuất hiện ở tất cả các dòng và dòng chữ NET nếu không có số đó.

3. Số không ghép được. Cho trước một mảng số tự nhiên $M[1:n]$. Tìm và in số tự nhiên tối thiểu không thể biểu thị bằng tổng các phần tử mảng $M$. Tổng có thể bao gồm một số hạng, nhưng mỗi phần tử của mảng chỉ có thể xuất hiện trong đó một lần.

4. Tetraedae. Trên các mặt của hai khối tứ diện vuông góc bằng nhau $M$ và $N$, các số $M1, M2, M3, M4$ được viết trên một mặt và $N1, N2, N3, N4$ trên mặt kia (theo cùng thứ tự). Có thể kết hợp các khối tứ diện để các số giống nhau được viết trên các mặt giống nhau không? Gõ DA hoặc NET.

5. Số phổ biến nhất. Trong mảng số $M[1:n]$ tìm số lặp lại nhiều lần nhất. Nếu có nhiều thì một trong số đó.

6. Hệ thống số. Mảng số nguyên $M[1:9]$ chứa các chữ số (chữ số) của một số tự nhiên trong hệ thống số $i$-ary ($M[1]$ là chữ số hàng đơn vị, v.v.). In chữ số của số này trong hệ thống số $j$-ary. Các số $i$ và $j$ không lớn hơn số mười.

7. Chảo chéo. Tìm tổng các phần tử $A[i, j]$ của mảng $A[1:m, 1:n]$ có chênh lệch chỉ số cho trước $i-j=k$. Số $k$ là số nguyên nhưng không nhất thiết phải dương.

---

Giải thích. Ở đây mảng $P[1:m, 1:n]$ biểu thị mảng số $P_{ij}$ cho $i=1, 2, ..., m$ và $j=1, 2, ..., n$, còn ký hiệu $P[i, j]$ biểu thị phần tử $P_{ij}$. Nếu nói mảng $P[1:m, 1:n]$ đã cho thì sẽ cho các số $m, n$ và giá trị của các phần tử mảng. Nhiệm vụ của các mảng khác có ý nghĩa tương tự.

Trong các chương trình (lời giải), học sinh nhập các giá trị được trích xuất và nhập chúng. Một số định dạng lời giải dưới dạng chương trình con (trong thuật toán - thủ tục, trong Forter - chương trình con, v.v.). Trong những ngôn ngữ mà kích thước của mảng phải được chỉ định bằng số (như trong Forter), học sinh có thể chọn chúng một cách tùy ý.

“Tốt lời giải” phải xếp chồng (tối đa một hệ số nhân không đổi) theo số lượng sau: $m \cdot n$ (bài toán 2), $n^2$ hoặc $n \cdot \log n$ (bài toán 3 và 5), tối thiểu {$m, n$} (bài toán 7), tính $n$ và $m$ trong số lượng lớn.