Vào 23:30 tối nay 10/08/2015 Codeforces Round #315 sẽ diễn ra.

Thời gian kết thúc đăng ký: 23:25

Mọi người có thể cùng vào đây thảo luận sau khi cuộc thi kết thúc.

Ai giải thích cho em cái đề B div 1 với, đề khó hiểu quá, chỗ mấy cái định nghĩa ấy

 

Trả lời themastermind
  Hiện bài gốc

hieu chua ban, giai thich gium minh voi :'(

Trả lời anhhungcolao
  Hiện bài gốc

Nhung luc nhu the nay lai thay thanh BVD co ich  that :3

Trả lời anhhungcolao
  Hiện bài gốc

P/S: Quên mất round này có cả Div 1.

Bây giờ mới phát hiện ra C, D, E Div 1 bằng A, B, C Div 2

A. Số nguyên tố hay số palindrome

Rikhail Mubinchik cho rằng các định nghĩa hiện tại về số nguyên tố đã lỗi thời vì chúng quá phức tạp và khó lường. Số palindrome thì khác. Chúng có tính thẩm mỹ, và chúng cũng có những tính chất đặc biệt. Giúp Rikhail thuyết phục cộng đồng khoa học về vấn đề này.

Số nguyên tố là một số nguyên lớn hơn \(1\),  không chia hết cho một số nguyên dương nào khác ngoại trừ chính nó và \(1\).​

Rikhail gọi một số là palindrome nếu nó là số nguyên dương, và biểu diễn thập phân của nó không tính các số 0 ở đầu là một palindrome, nghĩa đọc từ trái sang phải cũng như đọc từ phải sang trái.

Một vấn đề với số nguyên tố là nó có quá nhiều. Ta giới thiệu các kí hiệu sau: \(\pi(n)\) - số lượng số nguyên tố không lớn hơn \(n\) và \(rub(n)\) - số lượng số palindrome không lớn hơn \(n\). Rikhail muốn chứng minh rằng số nguyên tố nhiều hơn rất nhiều số palindrome.

Anh nhờ bạn giải bài toán sau: Cho hệ số A bất kì hãy tìm số nguyên \(n\) lớn nhất để \(\pi(n)\leq A.rub(n)\).

Dữ liệu

Gồm hai số nguyên \(p,q\), tử số và mẫu số của hệ số \(A\). (\(A=\frac{p}{q}; p,q \leq 10^4; \frac{1}{42} \leq A \leq 42\)).

Kết quả

In ra số \(n\) lớn nhất, nếu không tồn tại số \(n\) nào thỏa mãn điều kiện thì in ra "Palindromic tree is better than splay tree" (không có dấu ngoặc kép)

B. Đối xứng và bắc cầu

Johnny gần đây đã được học về lí thuyết tập hợp. Bây giờ anh ấy đang nghiên cứu về các mối quan hệ nhị phân. Bạn đã có thể nghe tới thuật ngữ "quan hệ tương đương". Những mối quan hệ này rất quan trọng trong nhiều lĩnh vực toán học. Ví dụ, hai số bằng nhau là một mối quan hệ tương đương.

Một tập \(\rho\) gồm các cặp phần tử \((a,b)\) của một tập \(A\) được coi là có quan hệ nhị phân với \(A\). Với hai phần tử \(a,b\)  của tập \(A\) ta nói rằng chúng có quan hệ với \(\rho\), nếu cặp \((a,b) \in \rho\), ta kí hiệu quan hệ này là \(a \sim b\).

Quan hệ nhị phân là quan hệ tương đương nếu

1, Nó có tính phản xạ (với mọi \(a\)thì luôn có \(a \sim a\))

2, Nó có tính đối xứng (với mọi \(a,b\) và \(a \sim b\) thì \(b \sim a\))

3, Nó có tính bắc cầu (nếu \(a \sim b\) và \(b \sim c\) thì \(a \sim c\))

Johnny không hề ngốc và anh nhận thấy điều kiện thứ nhất không cần thiết! Sau đây là cách chứng minh của anh ta

Chọn hai phần tử bất kì, \(a\) và \(b\), nếu \(a \sim b\) thì \(b \sim a\) (theo điều kiện 2), nghĩa là \(a \sim a\) (theo điều kiện 3)

Thật là dễ, phải không? Tuy vậy, bạn thất rằng cách chứng minh của Johnny đã sai, và hãy chỉ ra thật nhiều ví dụ để chứng minh anh ấy sai.

Đây là nhiệm vụ của bạn: đếm số quan hệ nhị phân của một tập \(n\) phần tử mà nó đối xứng và bắc cầu, nhưng lại không tương đương, nghĩa là nó không phản xạ.

Vì số này có thể rất lớn (nhưng chắc chắn không bằng \(0\), theo Johnny), hãy in số dư của kết quả cho \(10^9+7\).

Dữ liệu

Một dòng duy nhất chứa số nguyên dương \(n\) (\(1 \leq n \leq 4000\))

Kết quả

Một dòng in số dư của kết quả sau khi chia cho \(10^9+7\)

Ví dụ

Input

1

Output

1

Input

2

Output

3

Input

3

Output

10

Giải thích

​Nếu \(n=1\) thì tập \(A=\{x\}\) thì tập chỉ có một mối quan hệ \(\rho = \varnothing\), nghĩa là với mọi \(x\) ta có \(x \nsim x\) (vì tập \(A\) làm gì có hai phần tử \(x\) đâu)

Nếu \(n=2\) thì tập \(A\) có thể là \(\{x,x\}; \{x,y\}\) với \(x \ne y\). Trường hợp 1 không có phản ví dụ, trường hợp 2 có 3 phản ví dụ  là \(\rho = \varnothing\); \(\rho = \{(x,x)\}\); \(\rho = \{(y,y)\}\)

Để hiểu kĩ bài này chắc cần đọc kĩ mấy bài đầu quyển "Giải thuật và lập trình" của thầy Lê Minh Hoàng

Mình cũng công nhận đề bài nhiều điểm không chặt chẽ, như không nói rõ \(n\) là độ lớn của tập nào.

P/S: Cho mình nghỉ một chút, bài B nhiều lỗi diễn đạt đau đầu quá

C. Ngôn ngữ mới

Cuộc sống ở Byteland vốn đã rất tốt, nhưng nhà vua muốn làm hài lòng mọi người dân của mình bằng cách tạo nên một ngôn ngữ quốc gia. Ông tập hợp tất cả những người đàn ông khôn ngoan lại để lập một đoàn thám hiểm đi tới những đất nước xa xôi, nhờ thế mà họ sẽ khám phá ra cách tạo nên một ngôn ngữ.

Sau một thời gian, những người đàn ông khôn ngoan trở về và thậm chí còn trở nên khôn ngoan hơn. Họ bị giam sáu tháng trong phòng ăn, sau khi nói với nhà vua: "Có rất nhiều ngôn ngữ khác nhau, nhưng hầu hết trong số chúng đều có bảng chữ cái được chia ra làm nguyên âm và phụ âm, trong một từ, nguyên âm và phụ âm phải được kết hợp với nhau một cách chính xác."

Có rất nhiều quy tắc, tất cả đều có ngoại lệ, nhưng ngôn ngữ mới của chúng ta sẽ không có ngoại lệ nào. Họ đề xuất một tập hợp các quy tắc chính thức để kết hợp nguyên âm và phụ âm để tạo ra những từ mà họ hài lòng.

Các quy tắc đó là:

- Các chữ được chia làm nguyên âm và phụ âm theo một nguyên tắc xác định.

- Tất cả các từ đều có độ dài \(n\)

- Có các \(m\) quy tắc theo mẫu \((pos_1,t_1,pos_2,t_2)\), nghĩa là: nếu vị trí \(pos_1\) có chữ thuộc loại \(t_1\) thì vị trí \(pos_2\) phải có chữ thuộc loại \(t_2\).

Bạn được cho một xâu \(s\) độ dài \(n\), không nhất thiết phải là một từ của ngôn ngữ mới. Tìm từ của ngôn ngữ mới có thứ tự từ điển nhỏ nhất nhưng phải lớn hơn thứ tự từ điển của xâu \(s\).​

Dữ liệu

​Dòng đầu gồm các chữ cái 'V' (nguyên âm) và 'C' (phụ âm), xác định những chữ cái nào là nguyên âm và những chữ cái nào là phụ âm. Độ dài \(l\) của xâu này cũng là số chữ cái của bảng chữ cái ngôn ngữ mới (\(1 \leq l \leq 26\)). \(l\) chữ cái đầu tiên của bảng chữ cái tiếng Anh được dùng như bảng chữ cái của ngôn ngữ mới. Nếu chữ cái thứ \(i\) của xâu là 'V', thì chữ cái tương ứng của bảng chữ cái là nguyên âm, ngược lại thì nó là phụ âm.

Dòng thứ hai gồm hai số \(n,m\) \((1\leq n \leq 200, 0 \leq m \leq 4n(n-1))\) - số lượng chữ cái trong một từ và số lượng quy tắc.

\(m\) dòng tiếp theo miêu tả \(m\) quy tắc của ngôn ngữ theo dạng \(pos_1,t_1,pos_2,t_2\) \((1 \leq pos_1,pos_2 \leq n; pos_1 \ne pos_2; t_1,t_2 \in \{'V','C'\})\)

Dòng cuối cùng ghi xâu \(s\) có độ dài \(n\), các chữ cái của xâu đều nằm trong bảng chữ cái của ngôn ngữ mới.

Kết quả

In ra từ của ngôn ngữ mới có thứ tự từ điển lớn hơn thứ tự từ điển của \(s\) và nhỏ nhất. Nếu không tồn tại từ phù hợp thì in ra "-1" (không có dấu ngoặc kép) 

Trả lời bvd
  Hiện bài gốc

Tập A là tập các cặp số (x, y) mà mỗi cặp (x, y) biểu thị x có quan hệ với y.

Theo đề bài thì nếu có cặp (x, y) thì phải có cặp (y, x), nếu có cặp (x, y) và (y, z) thì sẽ có cặp (x, z).

Do đó phải có một số phần tử không xuất hiện trong bất kì cặp số nào trong A và các phần tử còn lại chia thành một số nhóm mà các cặp phần tử trong mỗi nhóm phải xuất hiện trong A.

Trả lời chemthan
  Hiện bài gốc

Tập A theo mình là tập các số chứ không phải các cặp số

A set ρ of pairs (a, b) of elements of some set A is called a binary relation on set A. For two elements a and b of the set A we say that they are in relation ρ, if pair , in this case we use a notation .

Nếu nó là các mối quan hệ thì câu 1 nó phải như thế này

A set \(\rho\) of pairs \((a,b)\), which are elements of some set \(A\), is called a binary relation on set A.

​Câu 2 sẽ là

For each pair \((a,b)\) of set \(A\), we say that it's in relation ρ, if pair , in this case we use a notation .

Còn tập \(\rho\) chứa các mối quan hệ.

Ví dụ tập \(A=\{1,2,3\}\).

\(1 \sim 2\) thì \(2 \sim 1\) (không cần quan tâm đến thứ tự)

\(1 \sim 2\), \(2 \sim 3\) thì \(1 \sim 3\)

Nhưng \(1 \nsim 1\) (do không có hai số \(1\))