Tô màu cây — TREECOL


Bài 6. Tô màu cây — TREECOL


.

Tìm tập độc lập cực đại trên cây — TMAXSET


Bài 5. Tìm tập độc lập cực đại trên cây — TMAXSET


.

HIST


Bài 4. Lỗ Ban - HIST


.

DIFFMAX


Bài 2. DIFFMAX


.

RICEATM

dophanthuan

Bài 1. RICEATM


.

Đoán số (THTB TQ 2017)

cuberlong

Bài 3

Hôm nay lớp Cam có một trò chơi trong giờ Toán. Cô giáo nghĩ trong đầu một số nguyên \(X\) trong khoảng \(1\) đến \(10^6\). Các bạn học sinh cần tìm được số bí mật X với ít nhất các câu hỏi có dạng: "Ước chung lớn nhất của một số \(X\) với một số \(Y\) là bao nhiêu?". Bạn nào dùng càng ít câu hỏi thì điểm càng cao.

Các bạn hãy giúp cam viết một chương trình, sử dụng các câu lệnh được cung cấp để tìm ra số bí mật \(X\) mà hết ít câu hỏi nhất.

Interaction

Để tương tác với máy chấm, hãy in mỗi lệnh trên từng dòng. Câu trả lời sẽ được máy chấm in ra trên một dòng khác, và bạn đọc vào. Lưu ý flush luồng ra chuẩn sau mỗi dòng được in ra bằng lệnh fflush(stdout) hoặc cout << endl;

Các câu lệnh:

  • ucln Y (Y là một số nguyên dương bất kì \(1 ≤ Y ≤ 10^{18}\)): máy sẽ in ra ước chung lớn nhất của X và Y.
  • traloi x (x là một số nguyên dương): là số bí mật X mà bạn đã xác định được. Chương trình bắt buộc phải in ra traloi một lần duy nhất, nếu không sẽ bị 0 điểm. Thủ tục này khi được gọi sẽ tự động thoát chương trình bằng câu lệnh exit.

Scoring

Với mỗi test, nếu chương trình của bạn trả lời với đáp án không chính xác, chạy quá thời gian quy định, sử dụng quá 1000000 câu hỏi hoặc gặp các lỗi dẫn tới dừng chương trình, bài làm sẽ nhận 0 điểm cho test đó. Số điểm cho mỗi test sẽ giảm dần khi số câu hỏi bạn sử dụng tăng lên.

Giả sử số bí mật \(X\) cần tìm là \(300000\), quá trình nhập xuất có thể diễn ra như sau:

>> ucln 100000
<< 100000
>> ucln 200000
<< 100000
>> ucln 500000
<< 100000
>> ucln 900000
<< 300000
>> traloi 300000

Hình chữ nhật (THTB TQ 2017)

cuberlong

Bài 2

Giờ học toán tiếp theo, Cam vẽ một trục tọa độ Oxy lên giấy và dùng 3 màu đen, xám, trăng để tô màu góc phần tư thứ nhất. Đầu tiên Cam tô hình vuông có tọa độ góc trái trên \((0,1)\) và tọa độ góc phải dưới \((1,0)\) là màu đen. Tiếp theo bé tô nhưng ô đen bằng màu xám, sau đó lại tô những ô kề đỉnh với ô xám mà chưa được tô màu trắng, sau đó lại tô những ô kề đỉnh với ô màu trắng mà chưa được tô bằng màu đen và cứ tiếp tục như vậy...

Sau đó Cam sẽ cắt tờ giấy và chỉ giữ lại 1 hình chữ nhật có tọa độ góc trái trên là \((x, y)\) và tọa độ góc phải dưới là \((u,v)\). Bé muốn biết trong hình chữ nhật được giữ lại có bao nhiêu ô màu trắng. Vì tọa độ có thể rất lớn nên các bạn hãy lập trình để tìm kết quả giúp bé nhé.

Hình bên dưới mô tả cho góc phần tư thứ nhất khi được tô và hình chữ nhật cắt ra có tọa độ góc trái trên là \((4,8)\) và tọa độ góc phải dưới là \((9,1)\). Khi đó bé Cam sẽ nhận được \(13\) ô trắng.

drawing

Input

  • Một dòng duy nhất là 4 số nguyên \(x, y, u, v (x ≤ u\) và \( y ≥ v)\) .

Output

  • Số ô vuông màu trắng trong hình chữ nhật có tọa độ góc trái trên là \((x, y)\) và tọa độ góc phải dưới là \((u,v)\).

Sample input

4 8 9 1

Sample output

13

Subtask

  • 30% test có \(1 ≤ x, y, u, v ≤ 1000\).
  • 70% test có \(1 ≤ x, y, u, v ≤ 10^6\).