JOI 2005/2006 - Kỳ thi thử 2

Bộ đề bài

Trở lại kỳ thi
# Bài tập Điểm Thời gian: Giới hạn bộ nhớ
1 JOI 2006 - Tunnel Traffic 100 (p) 1.0s 256M
2 JOI 2006 - Sequential Calculator 100 (p) 1.0s 256M
3 JOI 2006 - Product Orders 100 (p) 1.0s 256M
4 JOI 2006 - Apartment Areas 100 (p) 1.0s 256M
5 JOI 2006 - Necklace Color Combinations 100 (p) 1.0s 256M

1. JOI 2006 - Tunnel Traffic

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

Yêu cầu

Trong \(n\) phút, số xe đi vào và ra khỏi một đường hầm được ghi lại theo từng phút. Biết số xe ban đầu, hãy tìm số xe lớn nhất từng có trong hầm. Nếu số xe tính được âm tại bất kỳ thời điểm nào, dữ liệu lỗi.

Dữ liệu vào

Dòng đầu chứa \(n\). Dòng thứ hai chứa số xe ban đầu \(m\). Mỗi dòng trong \(n\) dòng tiếp theo chứa số xe vào và số xe ra trong một phút.

Dữ liệu ra

In số xe lớn nhất trong hầm, hoặc 0 nếu số xe từng trở thành âm.

Ràng buộc

  • \(n\le10000\).
  • Mỗi số xe vào hoặc ra trong một phút không vượt quá \(100\).

Ví dụ

Ví dụ 1

Input 
100
100
17 15
11 13
14 10
13 15
19 15
12 11
10 15
15 19
17 15
15 16
10 14
12 17
10 17
11 12
19 14
16 12
14 10
18 11
16 17
12 17
12 15
14 12
13 19
16 19
19 16
10 19
17 18
17 14
14 13
16 18
11 19
18 17
15 12
10 11
19 10
16 11
16 12
19 15
18 16
13 12
17 11
18 12
12 12
17 10
19 14
13 18
17 11
13 18
11 16
10 11
17 14
16 16
17 17
19 10
12 19
10 16
16 12
13 18
16 19
17 10
13 19
14 12
10 17
16 11
16 18
19 13
15 19
17 14
12 13
17 10
18 10
18 15
17 17
17 15
19 10
17 19
15 12
18 15
11 17
13 13
13 15
13 18
18 19
17 11
19 16
15 17
18 17
10 18
13 19
18 12
16 10
12 12
18 11
13 13
15 18
15 11
11 10
19 16
18 19
15 11
Output 
153

2. JOI 2006 - Sequential Calculator

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

Yêu cầu

Thực hiện một biểu thức gồm số và các toán tử +, -, *, / theo đúng thứ tự xuất hiện, không áp dụng độ ưu tiên toán tử. Phép chia số nguyên làm tròn xuống như quy ước của đề; ví dụ 100 / 3 * 3 cho kết quả \(99\).

Dữ liệu vào

Mỗi dòng lần lượt chứa một số hoặc một ký hiệu. Dòng đầu là số; sau đó số và toán tử xen kẽ. Ký hiệu = kết thúc biểu thức.

Dữ liệu ra

In kết quả tính toán.

Ràng buộc

  • Mỗi số đầu vào là số nguyên dương không vượt quá \(10^8\).
  • Mọi giá trị trung gian và kết quả thuộc \([-10^8,10^8]\).

Ví dụ

Ví dụ 1

Input 
1
+
123
+
12345
+
1234567
=
Output 
1247036

3. JOI 2006 - Product Orders

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

Yêu cầu

Một nhà máy nhận nhiều đơn đặt hàng. Hãy cộng tổng số lượng theo từng tên sản phẩm, rồi sắp sản phẩm theo độ dài tên tăng dần; nếu cùng độ dài, sắp theo thứ tự từ điển.

Dữ liệu vào

Dòng đầu chứa số đơn \(n\). Mỗi dòng tiếp theo chứa tên sản phẩm và số lượng. Tên gồm tối đa \(5\) chữ cái Latin hoa.

Dữ liệu ra

Với mỗi sản phẩm, in tên và tổng số lượng trên một dòng theo thứ tự yêu cầu.

Ràng buộc

  • Số đơn, mỗi số lượng và mỗi tổng đều không vượt quá \(10^8\).

Ví dụ

Ví dụ 1

Input 
30
A 813
B 25
C 202
D 422
E 94
A 607
B 522
C 750
D 806
E 11
A 490
B 83
C 495
D 646
E 9
A 426
B 466
C 658
D 808
E 102
A 82
B 311
C 513
D 535
E 411
A 118
B 98
C 185
D 798
E 575
Output 
A 2536
B 1505
C 2803
D 4015
E 1202

4. JOI 2006 - Apartment Areas

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

Yêu cầu

Các phòng hộ có diện tích dạng \(2xy+x+y\) với \(x,y\) là số nguyên dương. Một danh mục đã sắp diện tích tăng dần nhưng có thể chứa giá trị không thể có. Hãy đếm các giá trị sai.

Dữ liệu vào

Dòng đầu chứa \(N\). \(N\) dòng tiếp theo chứa các diện tích theo thứ tự tăng dần.

Dữ liệu ra

In số diện tích không biểu diễn được dưới dạng \(2xy+x+y\) với \(x,y>0\).

Ràng buộc

  • \(N\le100000\).
  • Diện tích không vượt quá \(2^{31}-1\).
  • Ba trong năm bộ dữ liệu có \(N\le1000\) và diện tích không vượt quá \(30000\).

Ví dụ

Ví dụ 1

Input 
100
4
7
10
12
13
16
17
18
19
22
24
25
26
27
28
30
31
32
34
37
38
40
42
43
45
46
47
49
52
55
57
58
59
60
61
62
64
66
67
70
71
72
73
76
77
79
80
82
83
84
85
87
88
91
92
93
94
97
98
100
101
102
103
104
106
107
108
109
110
112
115
117
118
120
121
122
123
124
126
127
129
130
132
133
136
137
139
142
143
144
145
147
148
149
150
151
152
154
155
157
Output 
7

5. JOI 2006 - Necklace Color Combinations

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

Yêu cầu

Có \(n\) màu hạt. Một vòng cổ gồm đúng \(r\) hạt và phải dùng ít nhất \(m\) hạt của mỗi màu. Hai vòng cổ chỉ được phân biệt bởi số hạt của từng màu. Hãy đếm số tổ hợp màu cần chuẩn bị.

Dữ liệu vào

Một dòng chứa \(n,m,r\).

Dữ liệu ra

In số tổ hợp hợp lệ.

Ràng buộc

  • \(0\le m<n\le r\le10000\).
  • Ba trong năm bộ dữ liệu có \(n\le10\).

Ví dụ

Ví dụ 1

Input 
5 0 10
Output 
1001