CẮT HÌNH

Nguồn: Bắc bộ 2015

Một mảnh giấy hình chữ nhật được cắt bởi những nhát kéo. Cho biết toạ độ của mảnh giấy cũng như các nhát cắt, hãy xác định số mảnh được cắt rời.

Giả thiết mảnh giấy được đặt trong một hệ toạ độ sao cho các mép giấy song song với các trục toạ độ, góc dưới trái của nó trùng với điểm (0; 0) và góc trên phải của nó trùng với điểm (m; n). Mỗi nhát cắt được xác định bởi hai đầu mút trên biên của mảnh giấy sao cho đảm bảo đoạn thẳng nối hai đầu mút này thực sự cắt mảnh giấy.

Dữ liệu vào cho trong file văn bản CAT.INP gồm:

·         dòng đầu ghi hai giá trị m và n (m, n nguyên dương, m,n < 10³)

·         dòng tiếp theo ghi số nhát cắt.

·         các dòng tiếp theo, mỗi dòng ghi toạ độ của một nhát cắt gồm 4 số: 2 số đầu là hoành độ và tung độ của một đầu mút và 2 số sau là hoành độ và tung độ của đầu mút còn lạ.

Các toạ độ trong file dữ liệu đều là những số nguyên và được ghi cách nhau ít nhất một dấu trắng nếu trên cùng một dòng. Giới hạn số nhát cắt không quá 300.

Kết quả ghi ra file văn bản CAT.OUT số mảnh bị cắt rời.

Ví dụ hình vẽ trên mô tả một mảnh giấy bị cắt bởi 6 nhát kéo thành 13 mảnh, tương ứng với các file vào, ra dưới đây:

CAT.INP		CAT.OUT
10 10 6 3    10   0     9 8    0     3     10 0    0     10   2 0    8     10   6 9    10    4     0 10   6    0      1		13

 Test - Solution - Đề (word)

CHAT ONLINE

http://codeforces.com/contest/469/problem/B

time limit per test: 1 second

memory limit per test: 256 megabytes

input: standard input

output: standard output

Little X and Little Z are good friends. They always chat online. But both of them have schedules.

Little Z has fixed schedule. He always online at any moment of time between a₁ and b₁, between a₂ and b₂, ..., between a_p and b_p (all borders inclusive). But the schedule of Little X is quite strange, it depends on the time when he gets up. If he gets up at time 0, he will be online at any moment of time between c₁ and d₁, between c₂ and d₂, ..., between c_q and d_q (all borders inclusive). But if he gets up at time t, these segments will be shifted by t. They become [c_i + t, d_i + t] (for all i).

If at a moment of time, both Little X and Little Z are online simultaneosly, they can chat online happily. You know that Little X can get up at an integer moment of time between l and r (both borders inclusive). Also you know that Little X wants to get up at the moment of time, that is suitable for chatting with Little Z (they must have at least one common moment of time in schedules). How many integer moments of time from the segment [l, r] suit for that?

Input

The first line contains four space-separated integers p, q, l, r (1 ≤  p, q ≤ 50; 0 ≤ l ≤ r ≤ 1000).

Each of the next p lines contains two space-separated integers a_i, b_i (0 ≤ a_i < b_i ≤ 1000). Each of the next q lines contains two space-separated integers c_j, d_j (0 ≤ c_j < d_j ≤ 1000).

It's guaranteed that b_i < a_i + 1 and d_j < c_j + 1 for all valid i and j.

Output

Output a single integer — the number of moments of time from the segment [l, r] which suit for online conversation.

Examples

input

1 1 0 4
2 3
0 1

output

3

input

2 3 0 20
15 17
23 26
1 4
7 11
15 17

output

20

Test - code (FP) - code (C++) - đề (English - Việt)

GIẢ THUYẾT GOLDBACH

Nguồn: Bắc bộ 2015

Giả thuyết Goldbach cho rằng: Tất cả các số tự nhiên chẵn lớn hơn 2 đều có thể được biểu diễn     dưới dạng tổng của 2 số nguyên  tố. Gọi G(N) là số các cách biểu diễn  khác nhau số 2N dưới   dạng tổng 2 số nguyên tố. Cho N (3 ≤ N ≤ 500,000), hãy tính F(N) = G(2) + G(3) + … + G(N).

Input: gồm không quá 30 bộ tests, mỗi bộ test được ghi trên một dòng: số nguyên N.

Output:  Ứng với mỗi bộ test, ghi ra trên một dòng giá trị F(N) tương ứng.

Ví dụ:

GOLDBACH.INP	GOLDBACH.OUT
7 4 9	8 3 12

 Test - code - solution -đề (word)

POWER

Nguồn: Bắc Bộ 2015

Số nguyên x được gọi là số lũy thừa đúng nếu tồn tại hai số nguyên a và b (b > 1), sao cho x=a^b. Ví dụ, 16 là một số lũy thừa đúng vì 16 = 2⁴. 

Việc biểu diễn x dưới dạng lũy thừa có thể không duy nhất. Ví dụ 16 = 2⁴ = 4². Như vậy, với x=16 tồn tại 2 cặp số (a, b) biễu diễn nó.

Yêu cầu: Cho số nguyên x (1 ≤ x ≤ 10¹⁸). Hãy tìm tất cả các cặp số nguyên (a, b) thỏa mãn x=a^b.

Input:  POWER.INP

-         Dòng 1: Số nguyên x (1 ≤ x ≤ 10¹⁸)

Output: POWER.OUT

-         Số nguyên k – số cặp (a, b) tìm được

-         Nếu k>0, mỗi dòng trong k dòng sau chứa 2 số nguyên a và b

POWER.INP	POWER.OUT
16	2 2 4 4 2

 Test - code (pascal) - code (C++) - solution - đề (word)

SỐ NGUYÊN TỐ

Nguồn: Chuyên Hoàng Văn Thụ - Hòa Bình

Cho dãy số nguyên x₁, x₂, …, x_N và hàm f(p) là số lượng các phần tử thuộc dãy x chia hết cho p.

Cho M truy vấn, mỗi truy vấn cho hai số nguyên l_i, r_i. Bạn phải trả lời câu hỏi: Tính tổng:

 , ở đây S(l_i, r_i) là tập các số nguyên tố thuộc đoạn [l_i,r_i].

INPUT:

·         Dòng đầu tiên chứa giá trị N (1 ≤ N ≤ 10⁶)

·         Dòng hai chứa N số nguyên x₁, x₂, …, x_N (2 ≤ x_i ≤ 10⁵)

·         Dòng ba chứa giá trị M (1 ≤ M ≤ 5*10⁴)

·         M dòng tiếp theo, mỗi dòng chứa hai số l_i, r_i (2 ≤ l_i ≤ r_i ≤ 2*10⁹)

OUTPUT:

·         Gồm M dòng, mỗi dòng là câu trả lời của truy vấn tương ứng của INPUT.

Ví dụ:

PRIME.INP	PRIME.OUT
6 5 5 7 10 14 15 3 2 11 3 12 4 4	9 7 0

Giải thích:

·         Tại truy vấn 1: l = 2, r = 11:

Ta cần tính f(2) + f(3) + f(5) + f(7) + f(11) = 2 + 1 + 4 + 2 + 0 = 9.

·         Tại truy vấn 2: l = 3, r = 12:

Ta cần tính f(3) + f(5) + f(7) + f(11) = 1 + 4 + 2 + 0 = 7

·         Tại truy vấn 3: l = 4, r = 4: không có số nguyên tố nào thuộc đoạn [l,r], nên kết quả truy vấn bằng 0

* Chú ý:

·         40% test 1 ≤ N, M ≤ 100; 1 ≤ l_i ≤ r_i ≤ 1000

·         40% test tiếp theo 1 ≤ N, M ≤ 1000; 1 ≤ l_i ≤ r_i ≤ 1000

·         20% test còn lại 1 ≤ N ≤ 10⁶, 2 ≤ x_i ≤ 10⁵, 1 ≤ M ≤ 5*10⁴, 2 ≤ l_i ≤ r_i ≤ 2*10⁹

 Test - Code - Solution - đề (word)

Tạo test cho các bài tập đồ thị

Chào mọi người!
     Mình là một người thường xuyên tạo test cho các bài tập trong Tin học, phần lớn các bài tập trên blog này mình đều tạo test. Nếu như việc tạo test cho những bài có dãy số tương đối đơn giản thì những bài đồ thị lại tương đối khó khăn vì có nhiều yêu cầu kèm theo như: đồ thị có các cạnh không được trùng nhau, số đỉnh lớn, số cạnh nhỏ (đồ thị thưa), đồ thị phải đảm bảo liên thông
   Tất nhiên để viết chương trình tạo test đáp ứng những yêu cầu trên không phải là vấn đề lớn nhưng thời gian chạy quá lâu.
    Do vậy mình có viết một chương trình tạo test để đáp ứng tất cả những yêu cầu trên với thời gian chạy ít (tạo đồ thị có 10^5 đỉnh và 10^6 cạnh trong thời gian 2 giây)
   Chương trình của mình có khả năng tạo được tối đa 500 test
   Các bạn có thể tải chương trình tại đây
   Lưu ý:
       + Trước khi chạy tệp Create_Graph.cpp các bạn phải thiết lập trong tệp test.txt. Trong tệp test.txt có nhiều dòng, mỗi dòng gồm 2 số tương ứng là số cạnh và số đỉnh của đồ thị. Số dòng trong tệp cũng chính là số test của đồ thị
       + Các bạn cũng có thể thay đổi những thông số trong chương trình cho phù hợp với từng bài toán
              - Dòng 3: số đỉnh tối đa trong đồ thị
              - Dòng 4: Giá trị tối đa của trọng số trong đồ thị
              - Dòng 5: Số lượng test tối đa muốn tạo

Dữ liệu ra: Gồm nhiều test, mỗi test nằm trong một thư mục, mỗi thư mục có 1 tệp tên là graph.inp có cấu trúc: 

+ Dòng đầu là hai số nguyên dương n và m cho biết số đỉnh và số cạnh của đồ thị, 

+ m dòng tiếp theo mỗi dòng ghi 3 số u, v, c trong đó c là trọng số của cạnh (u,v)

Thanks!

Otsu Thresholding Explained

Link: https://en.wikipedia.org/wiki/Otsu's_method

Chương trình cho Otsu Thresholding Explaind
+ Dữ liệu vào: tệp outs.txt gồm m dòng và m cột chứa ma trận số của ảnh
+ Dữ liệu ra: ex4.txt có cấu trúc gồm nhiều nhóm dòng, mỗi nhóm dòng có cấu trúc tương tự:
           T= 55
                  Weight 1 =4
                    Mean 1 =54.25000
                Variance1 =1.68750
             ------------------------
                  Weight 2 =60
                    Mean 2 =77.48333
                Variance2 =400.61639
           ----Within Class Variance: 9629620.85341
Chương trình: Pascal (Free Pascal)
   Download: here