TÍNH SAI - mã: WCALC - SPOJ

LINK: http://vn.spoj.com/problems/WCALC/

Khi còn bé, các bạn học sinh học được cách trừ phân số bằng cách quy đồng mẫu số, rồi mới thực hiện phép trừ.

Nhưng một lần, An tính thử hiệu hai phân số bằng cách lấy hiệu hai tử số và hiệu hai mẫu số và thấy thật ngạc nhiên là kết quả vẫn đúng.

An thấy tính chất này thật kỳ diệu và An muốn biết, với phân số  cho trước, có bao nhiêu cặp giá trị  a>=0 và m>=0 sao cho

Input

Một dòng chứa hai số nguyên dương b và n cách nhau ít nhất một dấu cách (1 <= b, n <= 10^6; trong 50% số test b, n <= 1000).

Output

Một số nguyên duy nhất là số lượng cặp (a,m) tính được.

Example

Input:

9 12

Output:

5

Code tham khảo: WCALC

Hướng làm: WCALC

Continue Reading

SÀNG NGUYÊN TỐ ERATOSTHENES

Trích: Sáng tạo trong thuật toán và lập trình (Quyển 2)

Từ thời cổ xưa, Eratosthenes đã dạy các học trò của mình như sau:

Muốn liệt kê toàn bộ số nguyên tố từ 1..N, hãy làm như sau:

Trước tiên, viết dãy số từ 1..N

Xóa số 1, vì đó là số đặc biệt, không phải số nguyên tố cũng không phải hợp số

Duyệt từ 2 tới Căn(N). Nếu gặp số nào chưa bị xóa đi thì đólà số nguyên tố và lần lượt xóa các bội số của số này kể từ bình phương của nó trở đi.

Khi kết thúc, nhưng số chưa bị xóa chính là số nguyên tố

thủ tục Sàng nguyên tố:

1. Fillchar(P, sizeof(P), 0);
2. For i:=2 to round(SQRT(N)) do
3. If P[i]=0 then
4. For j:=i to (n div i) do P[i*j]:=1;

Continue Reading

TÌM SỐ - FINDNUM - SPOJ

LINK: http://vn.spoj.com/problems/FINDNUM/

=========================================

Cho trước số n. Tìm số nguyên dương nhỏ nhất có đúng n ước số.

Giới hạn: 1 <=  n <=  1000.

Dữ liệu vào: Số n

Dữ liệu ra: Giá trị cần tìm (không quá 10^18)

Ví dụ:

Input: 8
Output: 24

Solution: FINDNUM

Code tham khảo: FINDNUM

Continue Reading

CÁC ĐOẠN NGUYÊN - mã: PBCSEQ - SPOJ

Link: http://vn.spoj.com/problems/PBCSEQ/
==================================

Mirko có một tập hợp các đoạn nguyên. Đầu tiên, anh ấy lấy ra 1 đoạn bất kì. Sau đó thực hiện lấy các đoạn khác, sao cho: đoạn lấy ra nằm trong đoạn vừa được lấy trước nó. Mirko tiếp tục cho đến khi không tìm được đoạn thoả mãn nữa.

Yêu cầu

Tìm số đoạn lớn nhất có thể lấy ra.

Dữ liệu

Dòng đầu tiên chứa số nguyên N, là số đoạn nguyên trong tập hợp.

Dòng thứ i trong số N dòng sau, chứa 2 số nguyên A,B biểu thị cho đoạn i.

Kết quả

Một số duy nhất là kết quả của bài toán.

Giới hạn

1 <= N <= 100000

1 <= A < B <= 1000000

Ví dụ

Dữ liệu

3



1 6



2 5



3 4
 
Kết quả



3

Dữ liệu

6


1 4


1 5

1 6


1 7 


2 5 


3 5
 
Kết quả

5



===========================

Thuật:

- Ta sắp xếp giảm theo A, nếu A bằng thì xếp tăng theo B

- Tìm dãy con không giảm dài nhất trên B => độ dài dãy con không giảm dài nhất chính là kết quả bài toán này

==========================


Code: PBCSEQ.PAS

Continue Reading

HÀNG CÂY - mã: FIRS - SPOJ

Link: http://vn.spoj.com/problems/FIRS/
================================

Biên giới giữa hai nước Ngược và Xuôi có dạng một đoạn thẳng với độ dài N-1 mét.

Vua nước Ngược vì muốn che giấu bí mật quốc gia đã trồng trên đường biên giới N cây tán lá xum xuê (các cây cách đều nhau với khoảng cách một mét). Vua nghĩ rằng nhờ hàng cây này mà các điệp viên của vua nước Xuôi không thể do thám nước mình được. Để chăm sóc các cây này, vua sai một người làm vườn mỗi buổi sáng chọn cây thưa lá nhất (có số lá ít nhất) và tưới một loại phân bón đặc biệt (nếu có nhiều cây thưa lá nhất thì người làm vườn sẽ chọn cây đầu tiên). Phân bón có bán kính tác dụng là 1 mét (nghĩa là sẽ tác dụng lên từ 1 đến 3 cây).

Tuy nhiên, vua nước Xuôi quyết định chống lại chiến lược này và thuê một người làm vườn khác. Mỗi buổi chiều, người làm vườn này tưới phân bón lên cùng cái cây đã được người làm vườn nước Ngược tưới vào buổi sáng, nhưng bằng một loại phân bón khác. Loại phân bón này làm chết tất cả các cây trong bán kính 1 mét!

Bạn được bộ trưởng tài chính của vua nước Xuôi thuê để giúp tính xem sau bao nhiêu ngày thì tất cả các cây đều bị chết. Hãy lập trình tính giá trị này.

Dữ liệu

Dòng đầu tiên chứa số lượng cây N (1 ≤ N ≤ 10⁵). Dòng thứ hai chứa N số nguyên a_i (1 ≤ a_i ≤ 10⁵) - số lượng lá trên các cây (theo thứ tự chúng được trồng từ trái sang phải).

Kết quả

In ra số ngày mà sau đó tất cả các cây đều bị chết.

Ví dụ

Dữ liệu

3

3 2 2

Kết quả

1

Dữ liệu

3

2 2 3

Kết quả

2

=============================================

Sắp xếp thôi là chưa đủ, chúng ta còn xử lí những cây có cùng số lá!

Code: http://ideone.com/GEwRcb

Continue Reading

PHÉP CHIA HẾT - mã: PBCDIV - SPOJ

Link: http://vn.spoj.com/problems/PBCDIV/
===========================================

Cho 2 số A và B. Tính xem có bao nhiêu số trong [A,B] chỉ chia hết cho đúng 2 trong 3 số 4, 6 và 15.

Input

-Dòng đầu là số test T (T<=10^5)

-T dòng tiếp theo mỗi dòng là 2 số nguyên A,B. (0<A<=B<=10^18)

Output

-T dòng,mỗi dòng là một kết quả của bài toán.

Example

Input:

2
1 20
2 30
Output:

1
3
================================================
Ta có: 
+ Bội chung nhỏ nhất của 4,6 là 12  ====> chia hết cho 4,6 thì chia hết cho 12
+ Bội chung nhỏ nhất của 6,15 là 30 ====> chia hết cho 6,15 thì chia hết cho 30
+ Bội chung nhỏ nhất của 4,15 là 60 ====> chia hết cho 4,15 thì chia hết cho 60

Ta có công thức sau: Số lượng số chia hết cho K trong [A,B] là: B/K - (A-1)/K...
Dễ thấy số lượng số thuộc [A,B] chia hết 2 trong 3 số 4,6,15 bằng: Số lượng số chia hết cho 12 + số lượng số chia hết cho 30 - 2 lần số lượng số chia hết cho 60.....

Chúc các bác AC ^^!

Continue Reading

BỘ SƯU TẬP CÁC ĐỒNG XU - mã: LEM1 - SPOJ

Link: http://vn.spoj.com/problems/LEM1/

=======================================

Cho N đồng xu có bán kính lần lượt là các số thực dương r₁.. r_N. Được đặt xung quanh một vòng tròn sao cho:

Mỗi đồng xu tiếp xúc với 2 đồng xu đặt cạnh nó và tiếp xúc với vòng tròn.

Biết được bán kính của từng đồng xu. Yêu cầu: Tìm bán kính vòng tròn

Input

Dòng đầu ghi số nguyên dương N

Dòng tiếp theo ghi N số r_i ( 1 ≤ i ≤ N )

Output

Gồm 1 dòng duy nhất ghi bán kính hình tròn ( độ chính xác đến 3 chữ số sau dấu phẩy )

Example

Input:

4

2 2 2 2

Output:

0.828

Giới hạn

1 ≤ N ≤ 10000

1 ≤ r_i ≤ 100000

====================================================
Code: LEM1.PAS
Ý tưởng chom chỉa trong quyển KC-BOOK 

Gọi đồng xu là vòng tròn đi cho dễ heng :)))))

-Cho O là tâm cái vòng tròn nhỏ ở trong....R là bán kính của nó (cái chúng ta cần tìm)

-O1,O2,..On lần lượt là tâm của mấy cái vòng tròn xung quanh

R1,R2,....,Rn lần lượt là bán kính của các vòng tròn xung quanh....ok, ta đi phân tích cách giải:

vậy nhé: rõ ràng ta thấy:

gócO1OO2+gócO2OO3+gócO3OO4+gócO4OO5+góc O5OO6+gócO6OO1 =360 độ

** Mấu chốt vấn đề nằm ở cái biểu thức đấy:

Việc tính các góc khá dễ dàng thông qua định lí COSIN (góc trong tam giác thường, không phải tam giác đặc biệt nên phải sử dụng định lí COSIN hoy)

quên lí thuyết coi chỗ này nhé: định lí cosin

Ví dụ một cái coi chơi: chúng ta đi tính gócO1OO2, rõ ràng góc này thuộc tam giác O1OO2 có các cạnh như sau:

    + O1O2 = R1+R2 (2 cái số này có hết rồi)

    + OO1   = R1+R (ẩn R => đang tìm)

    + OO2   = R2+R (ẩn R => đang tìm)

rồi áp dụng định lí Cosin vô: (code tin học) == R thay bằng k rồi đó

v:=(sqr(r[1]+k)+sqr(r[2]+k)-sqr(r[1]+r[2]))/(2*(r[1]+k)*(r[2]+k)); (1)

v:=arccos(v); (2)

-------------

vậy nè:  cái v trong (1) thật ra là cos của góc O1OO2 đó

         cái v trong (2) chuyển cos thành radian

các góc còn lại tính tương tự như góc tính bên trên, ta còn lại ẩn R (biến k trên code)

Ta sử dụng chặt nhị phân tìm R thay vào cái biểu thức trên đầu hết coi có đúng không, nếu đúng thì in ra

xong rồi, có nhiêu đó đó, chúc các bác AC, em AC gòi

========================

Continue Reading