trang chủ / đề bài / icpc21_nat_i

Chọn đề ICPC

Đề bài

Mô tả

Khi tổ chức một kỳ thi ICPC, một trong những công việc khó khăn nhất của ban khoa học là xây dựng một bộ đề tốt. May mắn thay, năm nay ban khoa học nhận được n đề xuất bài thi. Mỗi đề xuất được gắn ít nhất một trong các nhãn sau: quy hoạch động (dp), lý thuyết đồ thị (graph), toán và hình học (mathgeo), cấu trúc dữ liệu (ds) và ad hoc (adhoc).

Ban khoa học muốn có một bộ đề cân bằng, vì vậy đặt ra các quy tắc chọn đề sau:

  • Số bài có nhãn quy hoạch động phải nằm trong đoạn [dpmin,dpmax].
  • Số bài có nhãn lý thuyết đồ thị phải nằm trong đoạn [graphmin,graphmax].
  • Số bài có nhãn toán và hình học phải nằm trong đoạn [mathgeomin,mathgeomax].
  • Số bài có nhãn cấu trúc dữ liệu phải nằm trong đoạn [dsmin,dsmax].
  • Số bài có nhãn ad hoc phải nằm trong đoạn [adhocmin,adhocmax].

Cho số đề xuất n, các nhãn của từng đề xuất và các số dpmin, dpmax, graphmin, graphmax, mathgeomin, mathgeomax, dsmin, dsmax, adhocmin, adhocmax, hãy đếm số bộ đề khác rỗng thỏa mãn tất cả các quy tắc trên. Mỗi bộ đề là một tập con của n đề xuất. Hai bộ đề A và B được coi là khác nhau khi và chỉ khi có ít nhất một đề xuất thuộc A nhưng không thuộc B, hoặc ngược lại.

Dữ liệu vào

  • Dòng đầu tiên chứa số nguyên n, số đề xuất.
  • n dòng tiếp theo, dòng thứ i mô tả đề xuất thứ i: bắt đầu bằng số nguyên ti (1≤ti≤5) là số nhãn của đề xuất, tiếp theo là ti xâu đôi một phân biệt mô tả các nhãn. Mỗi xâu là một trong các nhãn dp, graph, mathgeo, ds, adhoc.
  • Dòng tiếp theo chứa hai số nguyên dpmin và dpmax.
  • Dòng tiếp theo chứa hai số nguyên graphmin và graphmax.
  • Dòng tiếp theo chứa hai số nguyên mathgeomin và mathgeomax.
  • Dòng tiếp theo chứa hai số nguyên dsmin và dsmax.
  • Dòng cuối cùng chứa hai số nguyên adhocmin và adhocmax.

Dữ liệu ra

In ra một số nguyên là số bộ đề khác nhau thỏa mãn các quy tắc chọn đề.

Ràng buộc

  • 1≤n≤50.
  • 0≤dpmin≤dpmax≤15, 0≤graphmin≤graphmax≤15, 0≤mathgeomin≤mathgeomax≤15.
  • 0≤dsmin≤dsmax≤15, 0≤adhocmin≤adhocmax≤15.

Ví dụ

Input Output Giải thích
6
1 dp
1 graph
1 mathgeo
1 ds
1 adhoc
2 dp graph
1 2
1 2
1 2
1 2
1 2
5 Phải dùng cả ba đề xuất 3, 4, 5. Với các đề xuất 1, 2, 6, có 5 cách chọn: {1,2}, {1,6}, {2,6}, {1,2,6} và {6}.
2
2 dp adhoc
2 ds graph
1 2
1 2
1 2
1 2
1 2
0 Không có đề xuất nào mang nhãn mathgeo nên không có bộ đề nào thỏa mãn.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0