Bạn có thể giải bài này trong độ phức tạp bao nhiêu?

907pqv · August 6, 2024, 3:31am

Hi mn, đây là 1 câu trong đề thi Olympic tin học (khối chuyên) trường mình khoảng năm 2019 hay 2018 gì đó. Mình không thể nghĩ ra trong phòng thi nhưng 2 ngày sau đó thì nghĩ ra được giải pháp tối ưu khi đang chạy xe ngoài đường. Ae thử sức cho vui:

Bài 3 – QUYỂN SÁCH CỔ

Một nhóm nhà khảo cổ học trẻ tuổi làm việc trong tòa nhà một thư viện cổ. Mùa hè, họ tìm thấy phần còn lại của quyển sách cổ và có các kết luận sau qua quá trình nghiên cứu. Quyển sách có một vài trang, mỗi trang chứa hoặc là chữ, hoặc là chữ và hình minh họa. Ở k trang đầu tiên có hình minh họa. Tất cả trang sách đều được đánh số, nhưng chỉ các trang chứa chữ mới được đánh số. Tổng các số được đánh ở các trang chứa chữ bằng s. Rất tiếc, tổng số trang trong quyển sách cũng như số lượng trang của các hình minh họa thì không biết được. Tuy nhiên, các nhà khảo cổ quan tâm tới con số lượng nhỏ nhất các trang hình minh họa có thể là bao nhiêu ở trong quyển sách.

Chẳng hạn, nếu k = 1 và s = 8 thì các trang sách có thể có như sau (kí tự T kí hiệu trang sách chứa chữ, còn kí tự I kí hiệu trang sách chứa hình minh họa):

I T I I I T, đánh số các trang 2 và 6, 4 trang hình minh họa.
I I T I T, đánh số các trang 3 và 5, 3 trang hình minh họa.
I I I I I I I T, đánh số trang 8, 7 trang hình minh họa.

Số lượng nhỏ nhất các trang hình minh họa là 3.

Yêu cầu: Cho 2 số nguyên k và s. Hãy xác định số lượng nhỏ nhất các trang hình minh họa có thể có trong quyển sách.

Dữ liệu: Vào từ file văn bản BOOKPAGES.INP

Dòng đầu tiên chứa số nguyên k \ (0 \leq k \leq 10^9)
Dòng thứ hai chứa số nguyên s \ (k + 1 \leq s \leq 10^{12})

Kết quả: Ghi ra file văn bản BOOKPAGES.OUT một số nguyên là số lượng nhỏ nhất các trang hình minh họa trong quyển sách.

tntxtnt · August 6, 2024, 3:36am

sách gì tới 1 tỷ trang hoang đường

toy tìm ra được quy luật rồi:

f(23, 40) = 39 (1 40)
f(23, 41) = 40 (1 41)
f(23, 42) = 41 (1 42)
f(23, 43) = 42 (1 43)
f(23, 44) = 43 (1 44)
f(23, 45) = 44 (1 45)
f(23, 46) = 45 (1 46)
f(23, 47) = 46 (1 47)
f(23, 48) = 47 (1 48)
f(23, 49) = 23 (2 25)
f(23, 50) = 24 (2 26)
f(23, 51) = 24 (2 26)
f(23, 52) = 25 (2 27)
f(23, 53) = 25 (2 27)
f(23, 54) = 26 (2 28)
f(23, 55) = 26 (2 28)
f(23, 56) = 27 (2 29)
f(23, 57) = 27 (2 29)
f(23, 58) = 28 (2 30)
f(23, 59) = 28 (2 30)
f(23, 60) = 29 (2 31)
f(23, 61) = 29 (2 31)
f(23, 62) = 30 (2 32)
f(23, 63) = 30 (2 32)
f(23, 64) = 31 (2 33)
f(23, 65) = 31 (2 33)
f(23, 66) = 32 (2 34)
f(23, 67) = 32 (2 34)
f(23, 68) = 33 (2 35)
f(23, 69) = 33 (2 35)
f(23, 70) = 34 (2 36)
f(23, 71) = 34 (2 36)
f(23, 72) = 35 (2 37)
f(23, 73) = 35 (2 37)
f(23, 74) = 36 (2 38)
f(23, 75) = 23 (3 26)
f(23, 76) = 24 (3 27)
f(23, 77) = 24 (3 27)
f(23, 78) = 24 (3 27)
f(23, 79) = 25 (3 28)
f(23, 80) = 25 (3 28)
f(23, 81) = 25 (3 28)
f(23, 82) = 26 (3 29)
f(23, 83) = 26 (3 29)
f(23, 84) = 26 (3 29)
f(23, 85) = 27 (3 30)
f(23, 86) = 27 (3 30)
f(23, 87) = 27 (3 30)
f(23, 88) = 28 (3 31)
f(23, 89) = 28 (3 31)
f(23, 90) = 28 (3 31)
f(23, 91) = 29 (3 32)
f(23, 92) = 29 (3 32)
f(23, 93) = 29 (3 32)
f(23, 94) = 30 (3 33)
f(23, 95) = 30 (3 33)
f(23, 96) = 30 (3 33)
f(23, 97) = 31 (3 34)
f(23, 98) = 31 (3 34)
f(23, 99) = 31 (3 34)
f(23, 100) = 32 (3 35)
f(23, 101) = 32 (3 35)
f(23, 102) = 23 (4 27)
f(23, 103) = 24 (4 28)
f(23, 104) = 24 (4 28)
f(23, 105) = 24 (4 28)
f(23, 106) = 24 (4 28)
f(23, 107) = 25 (4 29)
f(23, 108) = 25 (4 29)
f(23, 109) = 25 (4 29)
f(23, 110) = 25 (4 29)
f(23, 111) = 26 (4 30)
f(23, 112) = 26 (4 30)
f(23, 113) = 26 (4 30)
f(23, 114) = 26 (4 30)
f(23, 115) = 27 (4 31)
f(23, 116) = 27 (4 31)
f(23, 117) = 27 (4 31)
f(23, 118) = 27 (4 31)
f(23, 119) = 28 (4 32)
f(23, 120) = 28 (4 32)
f(23, 121) = 28 (4 32)
f(23, 122) = 28 (4 32)
f(23, 123) = 29 (4 33)
f(23, 124) = 29 (4 33)
f(23, 125) = 29 (4 33)
f(23, 126) = 29 (4 33)
f(23, 127) = 30 (4 34)
f(23, 128) = 30 (4 34)
f(23, 129) = 30 (4 34)
f(23, 130) = 23 (5 28)
f(23, 131) = 24 (5 29)
f(23, 132) = 24 (5 29)
f(23, 133) = 24 (5 29)
f(23, 134) = 24 (5 29)
f(23, 135) = 24 (5 29)
f(23, 136) = 25 (5 30)
f(23, 137) = 25 (5 30)
f(23, 138) = 25 (5 30)
f(23, 139) = 25 (5 30)
f(23, 140) = 25 (5 30)
f(23, 141) = 26 (5 31)
f(23, 142) = 26 (5 31)
f(23, 143) = 26 (5 31)
f(23, 144) = 26 (5 31)
f(23, 145) = 26 (5 31)
f(23, 146) = 27 (5 32)
f(23, 147) = 27 (5 32)
f(23, 148) = 27 (5 32)
f(23, 149) = 27 (5 32)
f(23, 150) = 27 (5 32)
f(23, 151) = 28 (5 33)
f(23, 152) = 28 (5 33)
f(23, 153) = 28 (5 33)
f(23, 154) = 28 (5 33)
f(23, 155) = 28 (5 33)
f(23, 156) = 29 (5 34)
f(23, 157) = 29 (5 34)
f(23, 158) = 29 (5 34)
f(23, 159) = 23 (6 29)
f(23, 160) = 24 (6 30)
f(23, 161) = 24 (6 30)
f(23, 162) = 24 (6 30)
f(23, 163) = 24 (6 30)
f(23, 164) = 24 (6 30)
f(23, 165) = 24 (6 30)
f(23, 166) = 25 (6 31)
f(23, 167) = 25 (6 31)
f(23, 168) = 25 (6 31)
f(23, 169) = 25 (6 31)
f(23, 170) = 25 (6 31)
f(23, 171) = 25 (6 31)
f(23, 172) = 26 (6 32)
f(23, 173) = 26 (6 32)
f(23, 174) = 26 (6 32)
f(23, 175) = 26 (6 32)
f(23, 176) = 26 (6 32)
f(23, 177) = 26 (6 32)
f(23, 178) = 27 (6 33)
f(23, 179) = 27 (6 33)
f(23, 180) = 27 (6 33)
f(23, 181) = 27 (6 33)
f(23, 182) = 27 (6 33)
f(23, 183) = 27 (6 33)
f(23, 184) = 28 (6 34)
f(23, 185) = 28 (6 34)
f(23, 186) = 28 (6 34)
f(23, 187) = 28 (6 34)
f(23, 188) = 28 (6 34)
f(23, 189) = 23 (7 30)
f(23, 190) = 24 (7 31)
f(23, 191) = 24 (7 31)
f(23, 192) = 24 (7 31)
f(23, 193) = 24 (7 31)
f(23, 194) = 24 (7 31)
f(23, 195) = 24 (7 31)
f(23, 196) = 24 (7 31)
f(23, 197) = 25 (7 32)
f(23, 198) = 25 (7 32)
f(23, 199) = 25 (7 32)
f(23, 200) = 25 (7 32)
f(23, 201) = 25 (7 32)
f(23, 202) = 25 (7 32)
f(23, 203) = 25 (7 32)
f(23, 204) = 26 (7 33)
f(23, 205) = 26 (7 33)
f(23, 206) = 26 (7 33)
f(23, 207) = 26 (7 33)
f(23, 208) = 26 (7 33)
f(23, 209) = 26 (7 33)
f(23, 210) = 26 (7 33)
f(23, 211) = 27 (7 34)
f(23, 212) = 27 (7 34)
f(23, 213) = 27 (7 34)
f(23, 214) = 27 (7 34)
f(23, 215) = 27 (7 34)
f(23, 216) = 27 (7 34)
f(23, 217) = 27 (7 34)
f(23, 218) = 28 (7 35)
f(23, 219) = 28 (7 35)
f(23, 220) = 23 (8 31)
f(23, 221) = 24 (8 32)
f(23, 222) = 24 (8 32)
f(23, 223) = 24 (8 32)
f(23, 224) = 24 (8 32)
f(23, 225) = 24 (8 32)
f(23, 226) = 24 (8 32)
f(23, 227) = 24 (8 32)
f(23, 228) = 24 (8 32)
f(23, 229) = 25 (8 33)
f(23, 230) = 25 (8 33)
f(23, 231) = 25 (8 33)
f(23, 232) = 25 (8 33)
f(23, 233) = 25 (8 33)
f(23, 234) = 25 (8 33)
f(23, 235) = 25 (8 33)
f(23, 236) = 25 (8 33)
f(23, 237) = 26 (8 34)
f(23, 238) = 26 (8 34)
f(23, 239) = 26 (8 34)
f(23, 240) = 26 (8 34)
f(23, 241) = 26 (8 34)
f(23, 242) = 26 (8 34)
f(23, 243) = 26 (8 34)
f(23, 244) = 26 (8 34)
f(23, 245) = 27 (8 35)
f(23, 246) = 27 (8 35)
f(23, 247) = 27 (8 35)
f(23, 248) = 27 (8 35)
f(23, 249) = 27 (8 35)
f(23, 250) = 27 (8 35)
f(23, 251) = 27 (8 35)
f(23, 252) = 23 (9 32)
f(23, 253) = 24 (9 33)
f(23, 254) = 24 (9 33)
f(23, 255) = 24 (9 33)
f(23, 256) = 24 (9 33)
f(23, 257) = 24 (9 33)
f(23, 258) = 24 (9 33)
f(23, 259) = 24 (9 33)
f(23, 260) = 24 (9 33)
f(23, 261) = 24 (9 33)
f(23, 262) = 25 (9 34)
f(23, 263) = 25 (9 34)
f(23, 264) = 25 (9 34)
f(23, 265) = 25 (9 34)
f(23, 266) = 25 (9 34)
f(23, 267) = 25 (9 34)
f(23, 268) = 25 (9 34)
f(23, 269) = 25 (9 34)
f(23, 270) = 25 (9 34)
f(23, 271) = 26 (9 35)
f(23, 272) = 26 (9 35)
f(23, 273) = 26 (9 35)
f(23, 274) = 26 (9 35)
f(23, 275) = 26 (9 35)
f(23, 276) = 26 (9 35)
f(23, 277) = 26 (9 35)
f(23, 278) = 26 (9 35)
f(23, 279) = 26 (9 35)
f(23, 280) = 27 (9 36)
f(23, 281) = 27 (9 36)
f(23, 282) = 27 (9 36)
f(23, 283) = 27 (9 36)
f(23, 284) = 27 (9 36)
f(23, 285) = 23 (10 33)
f(23, 286) = 24 (10 34)
f(23, 287) = 24 (10 34)
f(23, 288) = 24 (10 34)
f(23, 289) = 24 (10 34)
f(23, 290) = 24 (10 34)
f(23, 291) = 24 (10 34)
f(23, 292) = 24 (10 34)
f(23, 293) = 24 (10 34)
f(23, 294) = 24 (10 34)
f(23, 295) = 24 (10 34)
f(23, 296) = 25 (10 35)
f(23, 297) = 25 (10 35)
f(23, 298) = 25 (10 35)
f(23, 299) = 25 (10 35)
f(23, 300) = 25 (10 35)
f(23, 301) = 25 (10 35)
f(23, 302) = 25 (10 35)
f(23, 303) = 25 (10 35)
f(23, 304) = 25 (10 35)
f(23, 305) = 25 (10 35)
f(23, 306) = 26 (10 36)
f(23, 307) = 26 (10 36)
f(23, 308) = 26 (10 36)
f(23, 309) = 26 (10 36)
f(23, 310) = 26 (10 36)
f(23, 311) = 26 (10 36)
f(23, 312) = 26 (10 36)
f(23, 313) = 26 (10 36)
f(23, 314) = 26 (10 36)
f(23, 315) = 26 (10 36)
f(23, 316) = 27 (10 37)
f(23, 317) = 27 (10 37)
f(23, 318) = 27 (10 37)
f(23, 319) = 23 (11 34)
f(23, 320) = 24 (11 35)
f(23, 321) = 24 (11 35)
f(23, 322) = 24 (11 35)
f(23, 323) = 24 (11 35)
f(23, 324) = 24 (11 35)
f(23, 325) = 24 (11 35)
f(23, 326) = 24 (11 35)
f(23, 327) = 24 (11 35)
f(23, 328) = 24 (11 35)
f(23, 329) = 24 (11 35)
f(23, 330) = 24 (11 35)
f(23, 331) = 25 (11 36)
f(23, 332) = 25 (11 36)
f(23, 333) = 25 (11 36)
f(23, 334) = 25 (11 36)
f(23, 335) = 25 (11 36)
f(23, 336) = 25 (11 36)
f(23, 337) = 25 (11 36)
f(23, 338) = 25 (11 36)
f(23, 339) = 25 (11 36)
f(23, 340) = 25 (11 36)
f(23, 341) = 25 (11 36)
f(23, 342) = 26 (11 37)
f(23, 343) = 26 (11 37)
f(23, 344) = 26 (11 37)
f(23, 345) = 26 (11 37)
f(23, 346) = 26 (11 37)
f(23, 347) = 26 (11 37)
f(23, 348) = 26 (11 37)
f(23, 349) = 26 (11 37)
f(23, 350) = 26 (11 37)
f(23, 351) = 26 (11 37)
f(23, 352) = 26 (11 37)
f(23, 353) = 27 (11 38)
f(23, 354) = 23 (12 35)
f(23, 355) = 24 (12 36)
f(23, 356) = 24 (12 36)
f(23, 357) = 24 (12 36)
f(23, 358) = 24 (12 36)
f(23, 359) = 24 (12 36)
f(23, 360) = 24 (12 36)
f(23, 361) = 24 (12 36)
f(23, 362) = 24 (12 36)
f(23, 363) = 24 (12 36)
f(23, 364) = 24 (12 36)
f(23, 365) = 24 (12 36)
f(23, 366) = 24 (12 36)
f(23, 367) = 25 (12 37)
f(23, 368) = 25 (12 37)
f(23, 369) = 25 (12 37)
f(23, 370) = 25 (12 37)
f(23, 371) = 25 (12 37)
f(23, 372) = 25 (12 37)
f(23, 373) = 25 (12 37)
f(23, 374) = 25 (12 37)
f(23, 375) = 25 (12 37)
f(23, 376) = 25 (12 37)
f(23, 377) = 25 (12 37)
f(23, 378) = 25 (12 37)
f(23, 379) = 26 (12 38)
f(23, 380) = 26 (12 38)
f(23, 381) = 26 (12 38)
f(23, 382) = 26 (12 38)
f(23, 383) = 26 (12 38)
f(23, 384) = 26 (12 38)
f(23, 385) = 26 (12 38)
f(23, 386) = 26 (12 38)
f(23, 387) = 26 (12 38)
f(23, 388) = 26 (12 38)
f(23, 389) = 26 (12 38)
f(23, 390) = 23 (13 36)
f(23, 391) = 24 (13 37)
f(23, 392) = 24 (13 37)
f(23, 393) = 24 (13 37)
f(23, 394) = 24 (13 37)
f(23, 395) = 24 (13 37)
f(23, 396) = 24 (13 37)
f(23, 397) = 24 (13 37)
f(23, 398) = 24 (13 37)
f(23, 399) = 24 (13 37)

thấy quy luật chưa

ví dụ f(23, 50) = 24 (2 26) nghĩa là cuốn sách có 26 trang, và có 2 trang có chữ, ở đây có thể thấy là trang 24 và 26.

số các cuốn sách có 2 trang có chữ:

f(23, 49) = 23 (2 25)
f(23, 50) = 24 (2 26)
f(23, 51) = 24 (2 26)
f(23, 52) = 25 (2 27)
f(23, 53) = 25 (2 27)
f(23, 54) = 26 (2 28)
f(23, 55) = 26 (2 28)
f(23, 56) = 27 (2 29)
f(23, 57) = 27 (2 29)
f(23, 58) = 28 (2 30)
f(23, 59) = 28 (2 30)
f(23, 60) = 29 (2 31)
f(23, 61) = 29 (2 31)
f(23, 62) = 30 (2 32)
f(23, 63) = 30 (2 32)
f(23, 64) = 31 (2 33)
f(23, 65) = 31 (2 33)
f(23, 66) = 32 (2 34)
f(23, 67) = 32 (2 34)
f(23, 68) = 33 (2 35)
f(23, 69) = 33 (2 35)
f(23, 70) = 34 (2 36)
f(23, 71) = 34 (2 36)
f(23, 72) = 35 (2 37)
f(23, 73) = 35 (2 37)
f(23, 74) = 36 (2 38)

thì ta thấy kết quả lập lại 2 lần: f(23, 50) = f(23, 51) = 24, f(23, 52) = f(23, 53) = 25, v.v… trừ đoạn đầu và đuôi

với sách có 3 trang có chữ thì

f(23, 75) = 23 (3 26)
f(23, 76) = 24 (3 27)
f(23, 77) = 24 (3 27)
f(23, 78) = 24 (3 27)
f(23, 79) = 25 (3 28)
f(23, 80) = 25 (3 28)
f(23, 81) = 25 (3 28)
f(23, 82) = 26 (3 29)
f(23, 83) = 26 (3 29)
f(23, 84) = 26 (3 29)
f(23, 85) = 27 (3 30)
f(23, 86) = 27 (3 30)
f(23, 87) = 27 (3 30)
f(23, 88) = 28 (3 31)
f(23, 89) = 28 (3 31)
f(23, 90) = 28 (3 31)
f(23, 91) = 29 (3 32)
f(23, 92) = 29 (3 32)
f(23, 93) = 29 (3 32)
f(23, 94) = 30 (3 33)
f(23, 95) = 30 (3 33)
f(23, 96) = 30 (3 33)
f(23, 97) = 31 (3 34)
f(23, 98) = 31 (3 34)
f(23, 99) = 31 (3 34)
f(23, 100) = 32 (3 35)
f(23, 101) = 32 (3 35)

f lập lại 3 lần

vậy nếu biết được điểm đầu và đuôi và số trang chữ thì ta có thể tính ra kết quả dễ dàng. Điểm đầu và của sách có 2 trang chữ là 24+25=f(23, 49), điểm đầu của sách có 3 trang chữ là 24+25+26=f(23, 75) vậy điểm đầu của trang có x trang chữ là f(k, k+1 + k+2 + \dots + k+x) từ đó tính ra lẹ điểm đầu sao cho kx + \frac{x(x+1)}{2} \leq s và điểm cuối sao cho s \leq k(x+1) + \frac{(x+1)(x+2)}{2} rồi tìm điểm s chắc trong vòng O(1)

tntxtnt · August 12, 2024, 11:02am

int fast(int k, int64_t s) {
    const int b = 2*k + 1;
    if (s <= b + 1) return (int)s - 1;
    const double sqrtDelta = std::sqrt((int64_t)b*b + 8*s);
    const int t = (int)std::floor((-b + sqrtDelta) / 2);
    auto sumFromK = [k](int x) -> int64_t { return (int64_t)k*x + (int64_t)x*(x+1)/2; };
    const auto s0 = sumFromK(t);
    const auto s1 = sumFromK(t + 1);
    if (s == s0) return k;
    // const auto segmentLen = s1 - s0 - 1;
    const auto sDist = s - (s0 + 1);
    const auto addedLen = sDist / t + 1;
    return k + addedLen;
}

edit: ủa đâu cần tính cái segmentLen đâu 1 dòng code thừa