Đến nội dung


Chú ý

Nếu các bạn đăng kí thành viên mà không nhận được email kích hoạt thì hãy kiểm tra thùng thư rác (spam). Nếu không biết cách truy cập vào thùng thư rác thì các bạn chịu khó Google hoặc đăng câu hỏi vào mục Hướng dẫn - Trợ giúp để thành viên khác có thể hỗ trợ.


Hình ảnh

Các bài Div 1 Codeforces


  • Please log in to reply
Chủ đề này có 5 trả lời

#1 tritanngo99

tritanngo99

    Đại úy

  • Thành viên
  • 1756 Bài viết
  • Giới tính:Nam
  • Đến từ:Đà Nẵng
  • Sở thích:$\href{https://www.youtube.com/watch?v=YNlEDsIQxWU}{Đây}$

Đã gửi 28-09-2019 - 06:34

Bài 1: [588-Div.1-F] Cho $n$ cái cân được xếp theo vòng tròn. Mỗi cái cân liền kề với chính xác hai cái cân khác, với $i\in \left\{1;2;3;...;n-1\right\}$, thì cái cân thứ $i$ và cái cân thứ $i+1$ thì liền kề với nhau. Cái cân thứ $n$ và cái cân thứ $1$ liền kề với nhau.

Cái cân thứ $i$ ban đầu có $a[i]$ đồng xu. Bạn có thể thực hiện các bước như sau - Tại mỗi bước, ta lấy 1 đồng xu từ một chiếc cân, và đặt đồng xu đó sang 1 chiếc cân kề bất kỳ với chiếc cân đó.

Bài toán được giải quyết, khi sau một vài bước di chuyển, số đồng xu tại chiếc cân thứ i thỏa mãn: không lớn hơn $r[i]$ đồng xu và không bé hơn $l[i]$ đồng xu. Bạn hãy in ra số bước ít nhất có thể để có thể giải quyết được bài toán.

Đầu vào:

+ Dòng đầu tiên chứa $N(3\le N\le 35000)$. Với $N$ là số cái cân.

+ $N$ dòng tiếp theo, dòng thứ $i$ chứa 3 số $a[i],l[i],r[i](0\le a[i]\le 35000, 0\le l[i]\le r[i]\le 35000)$.

Đẩu ra: Số bước ít nhất để có thể giải quyết được bài toán.

Ví dụ:

5
0 2 3
1 2 3
4 3 3
4 3 3
4 3 3

Kết quả: 4.


Bài viết đã được chỉnh sửa nội dung bởi tritanngo99: 28-09-2019 - 07:07

Yêu quê hương thương nhân loại núi sông cảm mến
Hiểu Thánh triết biết nghĩa nhân trời đất chở che

#2 tritanngo99

tritanngo99

    Đại úy

  • Thành viên
  • 1756 Bài viết
  • Giới tính:Nam
  • Đến từ:Đà Nẵng
  • Sở thích:$\href{https://www.youtube.com/watch?v=YNlEDsIQxWU}{Đây}$

Đã gửi 28-09-2019 - 07:07

Bài 2: [588-Div.1-E2]. Marek chọn một số nguyên $n$ và $n^2$ số nguyên $p_{ij}(1\le i\le n,1\le j\le n)$. Sau đó anh ta tạo ra ngẫu nhiên một đồ thị lưỡng phía với $2n$ đỉnh. Có $n$ đỉnh bên trái: $l_1,l_2,...,l_n$ và $n$ đỉnh bên phải $r_1,r_2,...,r_n$. Với mỗi $i$ và $j$, anh ta đặt vào một cạnh giữa hai đỉnh $l_i$ và $r_j$ với xác suất $p_{ij}$ phần trăm.

Đồ thị được gọi là "Strong" nếu có một sự kết nối hoàn hảo tồn tại trong đồ thị lưỡng phía được tạo ra. Hãy tìm xác suất mà điều này xảy ra.

Kết quả có thể được biểu diễn dưới dạng $\frac{P}{Q}$. Với $P$ và $Q$ là hai số nguyên tố cùng nhau và $Q\not\equiv 0 (\text{ mod }10^9+7)$. Đặt $Q^{-1}$ là một số nguyên thỏa mãn $Q.Q^{-1}\equiv 1(\text{ mod }10^9+7)$. In ra giá trị $P.Q^{-1}$ mod $10^9+7$.

Đầu vào:

+ Dòng đầu tiên chứa số nguyên $n(1\le n\le 7)$.

+ $n$ dòng tiếp theo, mỗi dòng mô tả xác suất xuất hiện của các cạnh trong đồ thị. Dòng thứ $i$ chứa $n$ số nguyên $p_{i1},p_{i2},...,p_{in}(0\le p_{ij}\le 100)$; $p_{ij}$ là xác suất (%) xuất hiện của cạnh giữa đỉnh $l_i$ và $r_j$.

Đầu ra:

In ra một số nguyên- Là xác suất để được một đồ thị "Strong".

Ví dụ:

2
50 50
50 50

Kết quả: 937500007

Chú ý:

Screenshot from 2019-09-28 07-06-32.png

Ps: Bài [588-Div.1-E1] tương tự bài E2. Chỉ khác $n\le 6$


Bài viết đã được chỉnh sửa nội dung bởi tritanngo99: 28-09-2019 - 07:24

Yêu quê hương thương nhân loại núi sông cảm mến
Hiểu Thánh triết biết nghĩa nhân trời đất chở che

#3 tritanngo99

tritanngo99

    Đại úy

  • Thành viên
  • 1756 Bài viết
  • Giới tính:Nam
  • Đến từ:Đà Nẵng
  • Sở thích:$\href{https://www.youtube.com/watch?v=YNlEDsIQxWU}{Đây}$

Đã gửi 29-09-2019 - 07:23

Bài 3: [588-Div.1-D]

Wojtek vừa giành chiến thắng trong một cuộc thi toán học ở Byteland !. Giải thưởng của anh ta là một cuốn sách mang tên :”Card Tricks for Everyone” (Những mẹo trong chơi bài cho tất cả mọi người).

Chương đầu tiên của cuốn sách là: “Làm thế nào để xáo trộn k lá bài theo thứ tự bất kì mà bạn muốn”. Ở trong chương này, nó liệt kê ra $n$ cách để xáo trộn bộ bài gồm $k$ lá bài. Đặc biệt, cách thứ i được biểu diễn bởi 1 hoán vị $(P_{i,1},P_{i,2}…,P_{i,k})$ của các số nguyên từ 1 đến k. Nếu liệt kê những lá bài trong bộ bài theo thứ tự từ trên xuống dưới, thì lá bài thứ j sẽ là $P(i,j)$.

Wojtek sẽ chọn hai số nguyên $l$ và $r(1\le l \le r\le n)$, và anh ta sẽ ghi nhớ tất cả các mẹo từ mẹo thứ l đến mẹo thứ r. Sau đó, anh ta sẽ lấy một bộ bài đã được sắp xếp sẵn và áp dụng những mẹo mình đã nhớ cho đến khi anh ấy chán. Và anh ấy tự nhủ rằng, liệu mình đã tạo ra được bao nhiêu bộ hoán vị khác nhau khi mình dừng việc xáo trộn ấy lại .

Anh ta định nghĩa rằng, f(l,r) là số bộ hoán vị khác nhau mình đã tạo ra khi áp dụng những mẹo từ l đến r để xáo trộn. Tìm giá trị của biểu thức : $\sum\limits_{l=1}^{n}\sum\limits_{r=l}^{n}f(l,r)$.

Đầu vào:

+ Dòng đầu tiên chứa hai số nguyên $n$ và $k(1\le n\le 200000,1\le k\le 5)$. 

+ n dòng tiếp theo, mỗi dòng chứa 1 bộ hoán vị $(P_{i,1},P_{i,2}…,P_{i,k})(1\le P_{i,j}\le k)$.

Đầu ra: Là giá trị tổng cần tìm.

Ví dụ:

3 3

2 1 3

3 1 2

1 3 2

Kết quả: 25.

Giải thích:

+ Ở mẹo đầu tiên: So với bộ $(1,2,3)$ ta đã đổi hai vị trí trên cùng . Nên mẹo là: "Đổi chỗ hai vị trí trên cùng"

+ Ở mẹo thứ hai:  So với bộ $(1,2,3)$ ta đã đưa phần tử ở dưới cùng lên trên cùng. Nên mẹo là: "Đưa phần tử ở dưới cùng lên trên cùng"

+ Ở mẹo thứ ba: So với bộ $(1,2,3)$ ta đã đổi hai vị trí dưới cùng. Nên mẹo là: "Đổi chỗ hai vị trí dưới cùng".

Do đó ta có: $f(1,1)=2$.Vì khi áp dụng mẹo 1: Ta chỉ có thể tạo ra tối đa hai hoán vị khác nhau là: (1,2,3) và (2,1,3).

Tương tự là ta có: $f(3,3)=2$. Vì khi đó ta cũng thu được tối đa hai hoán vị khác nhau là: (1,2,3),(1,3,2).

+f(2,2)=3. Vì lúc này ta áp dụng đến mẹo 2. Nên có thể tạo ra tối đa 3 hoán vị: (1,2,3),(3,1,2),(2,3,1).

+Tương tự f(1,2)=f(1,3)=f(2,3)=3!=6.

Vậy $\sum\limits_{l=1}^{3}\sum\limits_{r=l}^{3}=6+6+6+2+2+3=25$.


Bài viết đã được chỉnh sửa nội dung bởi tritanngo99: 29-09-2019 - 07:30

Yêu quê hương thương nhân loại núi sông cảm mến
Hiểu Thánh triết biết nghĩa nhân trời đất chở che

#4 tritanngo99

tritanngo99

    Đại úy

  • Thành viên
  • 1756 Bài viết
  • Giới tính:Nam
  • Đến từ:Đà Nẵng
  • Sở thích:$\href{https://www.youtube.com/watch?v=YNlEDsIQxWU}{Đây}$

Đã gửi 30-09-2019 - 22:09

Bài 4: [588-Div.1-C] Cứ mỗi q ngày, tiền lương sẽ bị thay đổi. Vào cuối mỗi ngày thứ i, nhân viên v(i) sẽ bắt đầu kiếm được n+i rúp mỗi ngày và sẽ trở nên là người được trả lương cao nhất trong công ty. Người nhân viên này sẽ giữ mức lương này cho đến khi mức lương b thay đổi.

Có một vài cặp nhân viên trong công ty họ không thích lẫn nhau. Điều này tạo ra một mối nguy hiểm tâm lý lớn trong công ty. Một cách chính thức, nếu hai người a và b không thích lẫn nhau và a kiếm nhiều tiền hơn b, nhân viên a sẽ khoe với nhân viên b. Một bộ ba gọi là nguy hiểm nếu một bộ ba gồm 3 nhân viên a,b và c, thỏa mãn a khoe với b, b khoe với c. Nếu a không thích b thì b không thích a.

Vào lúc bắt đầu mỗi ngày, Konrad cần ước tính số lượng bộ ba nguy hiểm trong công ty. Liệu bạn có thể giúp anh ta.
Đầu vào:
+ Dòng đầu tiên chứa hai số nguyên n và m (1<=n<=100000,0<=m<=100000) - số lượng nhân viên trong công ty và số cặp người không thích lẫn nhau trong công ty. Mỗi một dòng trong m dòng tiếp theo chứa hai số nguyên a và b.
+ q dòng tiếp theo (0<=q<=100000) - số lần thay đổi lương. Mỗi dòng thứ i của q dòng tiếp theo chứa 1 số nguyên v(i)(1<=v(i)<=n)
Đầu ra:
+ Gồm q+1 số nguyên. Mỗi dòng thứ i của q+1 dòng  chứa số lượng bộ ba nguy hiểm trong công ty vào cuối ngày thứ i.
Ví dụ:
4 5
1 2
2 4
1 3
3 4
2 3
2
2
3
Đầu ra:
4
3
2

Screenshot from 2019-09-30 22-08-05.png


Bài viết đã được chỉnh sửa nội dung bởi tritanngo99: 30-09-2019 - 22:09

Yêu quê hương thương nhân loại núi sông cảm mến
Hiểu Thánh triết biết nghĩa nhân trời đất chở che

#5 tritanngo99

tritanngo99

    Đại úy

  • Thành viên
  • 1756 Bài viết
  • Giới tính:Nam
  • Đến từ:Đà Nẵng
  • Sở thích:$\href{https://www.youtube.com/watch?v=YNlEDsIQxWU}{Đây}$

Đã gửi 02-10-2019 - 06:35

Bài 5: [588-Div.1-B]

Kamil thích phát những video trực tiếp về các cuộc thi lập trình. Kênh Metube của anh ấy đã đạt được mốc 100 triệu lượt đăng ký. Để tổ chức sự kiện trọng đại này, anh ấy đã đăng 1 video kèo theo một bài toán mà anh ấy không thể giải quyết. Bạn có thể giúp anh ấy ?

 

Bạn được cho 1 cái cây - Là một đồ thị vô hướng gồm n đỉnh được nối với nhau bởi n-1 cạnh. Cái cây ban đầu có gốc tại đỉnh 1. Một đỉnh u được gọi là tổ tiên của đỉnh v nếu nó nằm trên đường đi ngắn nhất giữa gốc và đỉnh v. Đặc biệt, 1 đỉnh là tổ tiên của chính nó.

 

Mỗi đỉnh v có một nét đẹp riêng và được ký hiệu là x(v) - đó là một số không âm không lớn hơn 10^(12). Điều này cho phép chúng tôi định nghĩa vẻ đẹp của 1 đường. Gọi u là tổ tiên của v. Thì chúng tôi định nghĩa vẻ đẹp của f(u,v) là ước chung lớn nhất của tất cả các vẻ đẹp của tất cả các đỉnh nằm trên đường ngắn nhất từ u đến v. Một cách chính thức hóa, nếu u=t(1)t(2)...t(k)=v là những đỉnh nằm trên đường ngắn nhất từ u đến v, thì f(u,v)=gcd(x(t1),x(t2),…,x(tk)). Nhiệm vụ của bạn là tìm tổng $\sum f(u,v)$

Vì kết quả có thể lớn, nên kết quả sẽ là nó modulo 1e9+7.

Chú ý rằng: Với mỗi y , gcd(0,y)=gcd(y,0)=y và gcd(0,0)=0.

Đầu vào:

+ Dòng đầu tiên chứa số nguyên n(2<=n<=100000) - là số đỉnh của cây.

+ n dòng tiếp theo gồm n số nguyên là vẻ đẹp của tất cả các đỉnh của cây(0<=x(i)<=10^(12)).

+n-1 dòng tiếp theo là các cạnh của cây. Mỗi dòng chứa 2 số nguyên a,b (1<=a,b<=n, a khác b)

Đầu ra:

Kết quả cần tìm (đã modulo 1e9+7).

Ví dụ:

5

4 5 6 0 8

1 2

1 3

1 4

4 5

Kết quả: 42.

Screenshot from 2019-10-02 06-33-42.png


Yêu quê hương thương nhân loại núi sông cảm mến
Hiểu Thánh triết biết nghĩa nhân trời đất chở che

#6 tritanngo99

tritanngo99

    Đại úy

  • Thành viên
  • 1756 Bài viết
  • Giới tính:Nam
  • Đến từ:Đà Nẵng
  • Sở thích:$\href{https://www.youtube.com/watch?v=YNlEDsIQxWU}{Đây}$

Đã gửi 02-10-2019 - 11:13

Bài 6: [588-Div.1-A]

Marcin là một huấn luyện viên trong trường của anh ta. Có n học sinh muốn tham dự trại hè. Marcin là một huấn luyện viên thông minh, vì vậy anh ta muốn chỉ muốn gửi những học sinh mà có khả năng làm việc một cách bình tĩnh với nhau.

 

Chúng ta hãy tập trung vào những học sinh này. Họ được đánh số từ 1 đến n. Mỗi một người trong số họ được mô tả bởi hai số nguyên là a(i) và b(i); b(i) = là mức độ kĩ năng của học sinh thứ i. Ngoài ra, có 60 thuật toán được biết đến, chúng được đánh số từ 0 đến 59. Nếu học sinh thứ i biết thuật toán thứ j, thì bit thứ j (2^j) sẽ thuộc tập nhị phân của đại diện a(i).

Học sinh x nghĩ rằng anh ta có thể giỏi hơn học sinh y khi và ch khi x biết một vài thuật toán mà y không biết. Chú ý rằng 2 học sinh có thể nghĩ rằng họ tốt hơn lẫn nhau. Một nhóm các học sinh có thể làm việc với nhau một cách bình tĩnh nếu không có học sinh nào trong nhóm nghĩ rằng anh ta giỏi hơn những người còn lại trong nhóm.

 

Marcin muốn gửi một nhóm gồm ít nhất hai học sinh làm việc với nhau một cách bình tĩnh và có tổng skill lớn nhất có thể. Tổng đó là bao nhiêu.

Đầu vào:

+ Dòng đầu tiên chứa số nguyên n(1<=n<=7000) - số học sinh hứng thú với trại hè.

+ Dòng thứ 2 chứa n số a(i). Với 0<=a(i)<2^(60).

+ Dòng thứ 3 chứa n số b(i). Với 1<=b(i)<=10^9.

Đầu ra: In ra kết quả cần tìm. Nếu tìm không được in ra 0.

Ví dụ:

4

3 2 3 6

2 8 5 10

Kết quả: 15.

Screenshot from 2019-10-02 11-11-56.png


Bài viết đã được chỉnh sửa nội dung bởi tritanngo99: 02-10-2019 - 11:31

Yêu quê hương thương nhân loại núi sông cảm mến
Hiểu Thánh triết biết nghĩa nhân trời đất chở che




1 người đang xem chủ đề

0 thành viên, 1 khách, 0 thành viên ẩn danh