Reply
 
Thread Tools
  #11  
Old 25-10-2019, 20:10
INTP INTP is offline
Senior Member
Join Date: 06-2012
Posts: 1,585
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 offline
Senior Member
Join Date: 11-2009
Posts: 151
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: 74
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
__________________
Sinh viên húp mì tôm bán Netflix premium chỉ từ 30k/tháng(trial) và 60k(đã gia hạn) - quan tâm zalo em nha 0941245294
Reply With Quote
  #14  
Old 16-11-2019, 23:10
.gears's Avatar
.gears .gears is offline
Senior Member
Join Date: 03-2014
Location: ++
Posts: 192
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
__________________
Through action, a man becomes a hero.
Through death, a hero becomes a legend.
Through time, a legend becomes a myth.
Through hearing a myth, a man takes action.
Reply With Quote
  #15  
Old 16-11-2019, 23:38
INTP INTP is offline
Senior Member
Join Date: 06-2012
Posts: 1,585
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

« Previous Thread | Next Thread »
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


All times are GMT +7. The time now is 13:34.