Cần giúp đỡ về bài tập trên Timus

[08520001]

Bạn nào làm bài này rồi vậy. Giúp mình với do ngu nu
http://acm.timus.ru/problem.aspx?space=1&num=1209]

[09520540]

Bạn nào làm bài này rồi vậy. Giúp mình với
http://acm.timus.ru/problem.aspx?space=1&num=1209

Bài này mình chưa làm nhưng mà chuỗi số bắt đầu của của chuỗi đó là 110100100010000, tương ứng 10^0 ghép với 10^1, 10^2, 10^3, 10^4,...

[08520001]

Mình nghĩ là sẽ tạo 1 chuỗi độ dài khoảng 66000 kí tự. Nhưng vậy tốn bộ nhớ quá. Không biết có cách nào tốt hơn hok do ngu nam.

[09520540]

Uh mình nghĩ bài này chắc phải áp dụng 1 công thức toán nào đó. Chỉ cần xét xem số vị trí ở đầu vào có thỏa mãn 1 công thức nào đó không là được. Có quy luật là nếu số đó == tổng của x số nguyên đầu tiên + 1 thì nó sẽ trả về 1, ngược lại thì trả về 0.
Ví dụ:
- 1 = 1 + 0
- 2 = 1 + 0 + 1
- 4 = 1 + 0 + 1 +2
- 7 = 1 + 0 + 1 + 2 + 3
- 11 = 1 + 0 + 1 + 2 + 3 + 4
Nhưng vấn đề là x = ?
Rất tiếc mình không giỏi Toán cho lắm. Chắc phải chờ cao nhân thôi

[08520001]

Vậy nếu mình viết 1 hàm kiểm tra n có phải là tổng của x số tự nhiên đầu tiên ko thì sao nhỉ. Tổng x số tự nhiên đầu tiên là x * (x + 1) / 2. Mình duyệt x để kiểm tra. Không biết cách này có được ko. thoi trang nu thoi trang tre em.

[07520004]

Vậy nếu mình viết 1 hàm kiểm tra n có phải là tổng của x số tự nhiên đầu tiên ko thì sao nhỉ. Tổng x số tự nhiên đầu tiên là x * (x + 1) / 2. Mình duyệt x để kiểm tra. Không biết cách này có được ko.

Được. Cách này ít tốn bộ nhớ nhưng mà duyệt 65535 lần cho một số n có giá trị (2^31) - 1 trong vòng 1.0 giây như nó yêu cầu thì ko biết nổi hay không, thử phát đi

[iticlub]

Theo mình đã tính thì số 1 thứ i sẽ nằm tại vị trí i*(i-1)/2 + 1.
Khi có input (giả sử là t), mình tính toán ra giá trị i = sqrt((t-1) * 2) rồi sau đó tính tiếp i*(i-1)/2 + 1 để xem thử số này có bằng t hay không.
Tuy nhiên, khi submit thì bị sai ở test 3. Không biết là vì sao....

[09520540]

Theo mình đã tính thì số 1 thứ i sẽ nằm tại vị trí i*(i-1)/2 + 1.
Khi có input (giả sử là t), mình tính toán ra giá trị i = sqrt((t-1) * 2) rồi sau đó tính tiếp i*(i-1)/2 + 1 để xem thử số này có bằng t hay không.
Tuy nhiên, khi submit thì bị sai ở test 3. Không biết là vì sao....

Uh thì nó sai chứ sao?
Có vẻ test thứ 3 là 1 cái test rất kinh khủng, mình thì làm theo cách dùng vòng lặp tính tổng rồi kiểm tra lại. Vẫn bị kẹt ở test thứ 3, lỗi "Hết giờ" ==> Khó lòng mà dùng vòng lặp để tính kịp được. Giờ còn việc tìm ra cái công thức đúng thôi.
function check(A : real):boolean;
begin
if frac((1+sqrt(8*A-7))/2) = 0.0 then check := true else check:=false;
end;
Hàm này mình nhặt được trong cái đống discuss của nó nè, chạy đúng, vấn đề là đâu ra? (Pascal nhé)

[08520001]

Các bạn thử dùng mảng và tìm kiếm nhị phân xem. Mình đã AC bằng cách đó. do ngu.

[07520004]

Dùng dynamic arrays và hashtable (nói cho sang chứ thật ra là vector và map đó) và đã lố giờ ở test thứ 5 =))
Ôi lâu quá rồi mình ko đụng tới C

[08520522]

Uh thì nó sai chứ sao?
Có vẻ test thứ 3 là 1 cái test rất kinh khủng, mình thì làm theo cách dùng vòng lặp tính tổng rồi kiểm tra lại. Vẫn bị kẹt ở test thứ 3, lỗi "Hết giờ" ==> Khó lòng mà dùng vòng lặp để tính kịp được. Giờ còn việc tìm ra cái công thức đúng thôi.
function check(A : real):boolean;
begin
if frac((1+sqrt(8*A-7))/2) = 0.0 then check := true else check:=false;
end;
Hàm này mình nhặt được trong cái đống discuss của nó nè, chạy đúng, vấn đề là đâu ra? (Pascal nhé)

n*(n-1)/2 + 1 = A => n*n -n +2 - 2A = 0
Delta = 1 - 4(2-2A) = 8A - 7
Phương trình trên có nghiệm n = (1 + sqrt(Delta))/2. Để nghiệm này nguyên thì phần thập phân của nó phải bằng không (chính là hàm frac của Pascal)

[09520434]

em làm bằng tìm kiếm nhị phân, nhưng sai ở test 3. Anh An có biết test 3 như thế nào k ạ.

[07520004]

n*(n-1)/2 + 1 = A => n*n -n +2 - 2A = 0
Delta = 1 - 4(2-2A) = 8A - 7
Phương trình trên có nghiệm n = (1 + sqrt(Delta))/2. Để nghiệm này nguyên thì phần thập phân của nó phải bằng không (chính là hàm frac của Pascal)

Cái giải phương trình bậc hai này anh có thử, sai ở test 3 (wrong answered). Dự đoán là do A = 2^31-1 mà còn *8 lên xong căn ra chắc sai số nó lớn quá

[BiThuDoan]

Dùng dynamic arrays và hashtable (nói cho sang chứ thật ra là vector và map đó) và đã lố giờ ở test thứ 5 =))
Ôi lâu quá rồi mình ko đụng tới C

Ủa, nó cho mình sử dụng thư viện STL hả?

[08520001]

Các bạn cẩn thận ở test 3, nếu tạo mảng thì nên để kiểu dữ liệu long long quan ao nu.