Lượm nhặt 1 số bài test thuật toán mời ae vào giải cho vui :D - Page 2 - vozForums
vozForums
Go Back   vozForums > Học tập và công việc > Ngành CNTT > Phát triển Phần mềm
Reply
 
Thread Tools
  #11  
Old 25-10-2019, 20:10
INTP INTP is offline
Senior Member
 
Join Date: 06-2012
Posts: 2,508
Re: Lượm nhặt 1 số bài test thuật toán mời ae vào giải cho vui :D

sẵn tiện giải bài Josephus đi

cho vòng tròn n người, đánh số mỗi người từ 1 tới n. Đếm từ 1 tới k thì giết người thứ k, rồi lại đếm tiếp. Hỏi người cuối cùng số mấy. Ví dụ k=3, n=41 thì đáp án là 31. Giới hạn k <= 10^5, n <= 10^9.

---phần 2

với k cố định, n thay đổi m lần (m <= 10^5), tính tổng m người sống sót cuối cùng (mod 10^9 + 7). Để cho tiện khỏi phải input m lần, ta chỉ cho 1 cái seed và 1 số m, rồi dùng seed đó seed cho 1 hàm ngẫu nhiên nào đó mà tạo ra m số n (mod 1 tỷ, +1). Ở đây chắc xài hàm ngẫu nhiên đơn giản: a(i+1) = 48271*a(i) % 2147483647. Vd code C:
PHP Code:
void myrand(intx) {
    *
= (int64_t)*48271 2147483647;

vd seed=12345, 3 số ngẫu nhiên đầu tiên là 595905495 1558181227 1498755989. Từ 3 số ngẫu nhiên này ta lấy mod của 1 tỷ rồi +1 sẽ ra n:
(595905495 % 1 tỷ) + 1 = 595905496
(1558181227 % 1 tỷ) + 1 = 558181228
(1498755989 % 1 tỷ) + 1 = 498755990
vd k=3
f(3, 595905496) = 236124662
f(3, 558181228) = 122951858
f(3, 498755990) = 461873420
tổng 3 số mod 10^9+7 là 820949940

input k=3, seed=12345, m=3, output là 820949940
input k=10^5, seed=12345, m=10, output là 550320658
input k=10^5, seed=12345, m=100, output là 253438681
input k=10^5, seed=12345, m=10^5, output là 526721889


giới hạn 0.1s hoặc nhanh tới đâu thì hay tới đó vậy

Last edited by INTP; 25-10-2019 at 20:12.
Reply With Quote
  #12  
Old 01-11-2019, 15:06
vanfsn vanfsn is online now
Senior Member
 
Join Date: 11-2009
Posts: 122
Re: Lượm nhặt 1 số bài test thuật toán mời ae vào giải cho vui :D

tường mình cho dễ đọc, ngắn quá khó hiểu, già rồi 305212
Reply With Quote
  #13  
Old 16-11-2019, 13:43
VTV_l1l's Avatar
VTV_l1l VTV_l1l is offline
Member
 
Join Date: 01-2017
Posts: 51
Re: Lượm nhặt 1 số bài test thuật toán mời ae vào giải cho vui :D

Hay thật

Gửi từ Xiaomi MI 8 bằng vozFApp
Reply With Quote
  #14  
Old 16-11-2019, 23:10
.gears's Avatar
.gears .gears is online now
Senior Member
 
Join Date: 03-2014
Location: ++
Posts: 160
Re: Lượm nhặt 1 số bài test thuật toán mời ae vào giải cho vui :D

Quote:
Originally Posted by INTP View Post
sẵn tiện giải bài Josephus đi

cho vòng tròn n người, đánh số mỗi người từ 1 tới n. Đếm từ 1 tới k thì giết người thứ k, rồi lại đếm tiếp. Hỏi người cuối cùng số mấy. Ví dụ k=3, n=41 thì đáp án là 31. Giới hạn k <= 10^5, n <= 10^9.

---phần 2

với k cố định, n thay đổi m lần (m <= 10^5), tính tổng m người sống sót cuối cùng (mod 10^9 + 7). Để cho tiện khỏi phải input m lần, ta chỉ cho 1 cái seed và 1 số m, rồi dùng seed đó seed cho 1 hàm ngẫu nhiên nào đó mà tạo ra m số n (mod 1 tỷ, +1). Ở đây chắc xài hàm ngẫu nhiên đơn giản: a(i+1) = 48271*a(i) % 2147483647. Vd code C:
PHP Code:
void myrand(intx) {
    *
= (int64_t)*48271 2147483647;

vd seed=12345, 3 số ngẫu nhiên đầu tiên là 595905495 1558181227 1498755989. Từ 3 số ngẫu nhiên này ta lấy mod của 1 tỷ rồi +1 sẽ ra n:
(595905495 % 1 tỷ) + 1 = 595905496
(1558181227 % 1 tỷ) + 1 = 558181228
(1498755989 % 1 tỷ) + 1 = 498755990
vd k=3
f(3, 595905496) = 236124662
f(3, 558181228) = 122951858
f(3, 498755990) = 461873420
tổng 3 số mod 10^9+7 là 820949940

input k=3, seed=12345, m=3, output là 820949940
input k=10^5, seed=12345, m=10, output là 550320658
input k=10^5, seed=12345, m=100, output là 253438681
input k=10^5, seed=12345, m=10^5, output là 526721889


giới hạn 0.1s hoặc nhanh tới đâu thì hay tới đó vậy
bài 1 giải được trong O(k) còn bài 2 thế nào vậy bác nghĩ mãi không ra 1417824
Reply With Quote
  #15  
Old 16-11-2019, 23:38
INTP INTP is offline
Senior Member
 
Join Date: 06-2012
Posts: 2,508
Re: Lượm nhặt 1 số bài test thuật toán mời ae vào giải cho vui :D

https://en.wikipedia.org/wiki/Joseph...e_general_case

bài 1 O(k logn) chứ đâu ra O(k)

bài 2 là lưu các "reset points" từ bài 1, cũng tốn O(k logn), rồi binary search tính lẹ m lần mỗi lần chỉ cần O(logk + loglogn), tổng cộng đpt là O(k logn + m logk + m loglogn)

ví dụ với k=3, lập bảng g(n,3):
Code:
 n  g(n,3)
 1     1*
 2     2*
 3     2*
 4     1*
 5     4
 6     1*
 7     4
 8     7
 9     1*
10     4
11     7
12    10
13    13
14     2*
15     5
16     8
17    11
18    14
19    17
20    20
21     2*
22     5
23     8
24    11
25    14
các reset points là cặp (n, g(n,3)) sao cho g(n,3) < 3. Có thể chứng minh số các reset points này là O(k logn). Nếu tìm được các điểm này thì có thể g(n,3) nhanh bằng cách tìm nhị phân n* lớn nhất trong danh sách các điểm reset mà bé hơn n, rồi trả về g(n,3) = g(n*,3) + 3(n - n*). Vd g(24,3) = g(21,3) + 3(24-21) = 2 + 9 = 11.
vấn đề là tìm k logn cặp (n, g(n,3)) theo công thức O(1)

Last edited by INTP; 17-11-2019 at 00:03.
Reply With Quote
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off

Forum Jump

All times are GMT +7. The time now is 12:58.
Chịu trách nhiệm nội dung: Bạch Thành Trung © 2019 Công ty TNHH Thật Vi Diệu
ĐC tầng 4, số 6-8 Đường D2, Bình Thạnh, Hồ Chí Minh, Việt Nam - SĐT 0981323799 - MST 0313906593
Giấy phép thiết lập MXH số 334/GP-BTTTT, Ký ngày: 19/08/2019