[Chôm từ reddit] Số nguyên phức tạp #2

anon10709737 · March 20, 2018, 5:19am

Haizz! Cả 1 ngày trời đi học mệt quá giờ mới có thời gian đăng tiếp challenge Số nguyên phức tạp #2 cho mọi người. Lần này câu đó khó hơn đó nha.

Giải challenge #1 thì vào đây: [Chôm từ reddit] Số nguyên phức tạp #1

Đề như sau:

###BACKGROUND

Biểu diễn 1 số nguyên dương bằng cách sử dụng số nguyên dương, phép cộng, phép nhân và dấu ngoặc. Với số 5678 thì có 1 vài cách như sau:

5678 = 2*17*167
5678 = 5678
5678 = 23*59+29*149
5678 = (1+4*4)*(1+3*3*(1+3*3*4))
5678 = 2*(1+2*(1+2*(1+2*2*(1+2*2*2*2*(1+2*(1+2*2))))))

Sau đó cho từng cặp các số được biểu diễn trên thành chỉ thành 1 tổng:

2*17*167 => 2+17+167 = 186
5678 => 5678 = 5678
23*59+29*149 => 23+59+29+149 = 260
(1+4*4)*(1+3 * 3 *(1+3*3*4)) => 1+4+4+1+3+3+1+3+3+4 = 27
2*(1+2*(1+2*(1+2*2*(1+2*2*2*2*(1+2*(1+2*2)))))) =>
    2+1+2+1+2+1+2+2+1+2+2+2+2+1+2+1+2+2 = 30

Vậy giá trị nhỏ nhất trong trường hợp trên là 27. Vậy số 27 được coi là số nguyên phức tạp(Có thể hiểu là 1 hàm tên là số nguyên phức tạp và tham số là 1 số được cho sẵn). Vậy số _nguyên_phức_tap(5678) => 27. Số nguyên phức tạp của số 1, 2, 3,… là:

1 2 3 4 5 5 6 6 6 7 8 7 8 8 8 8 9 8 9 9 ...

Tổng của các Số nguyên phức tạp từ 1 đến 100 là 1113.

###CHALLENGE

Tìm tổng các Số nguyên phức tạp từ 1 đến 1000(Có thể nhiều hơn nhưng nhỏ nhất buộc phải là 1 nha).

Chúc các bạn code vui vẻ!!!

P/s: Lời giải hay và bá đạo thì mình sẽ tag solution vào đấy nhé

phamvandung · March 19, 2018, 11:08pm

(1+4*4)(1+33*(1+3*3*4)) => 1+4+4+1+3+3+1+3+3+4 = 27

??

anon10709737 · March 20, 2018, 5:06am

Viết code hẳn hoi đi anh ơi

noname00 · March 20, 2018, 5:11am

Ý bạn ấy nói là ví dụ có gì đó có sai hay không ấy.

anon10709737 · March 20, 2018, 5:12am

Kiểu là phá hết cái ngoặc đi. Chuyển nhân thành cộng ý

phamvandung · March 20, 2018, 6:25am

Vẫn chưa thể tìm ra quy luật tìm số này, có ai thông não giúp tui hông???

noz1995 · March 20, 2018, 11:19am

Mình thấy đề này không ổn.

5678 = 23*59+29*149

Như vậy có thể tách số ban đầu thành tổng 2 số.
Số 5678 có 5678/2 cách cộng từ 2 số. (1*1 + 5677, 1*2 + 5676…)
Đề này không ổn.

noname00 · March 20, 2018, 11:33am

Vấn đề cuối cùng là tổng các số tham gia là nhỏ nhất anh ạ.

rogp10 · March 20, 2018, 11:44am

Mình thấy xác định duyệt kiểu gì cũng đã khó rồi

tntxtnt · March 20, 2018, 1:11pm

trên reddit có gợi ý + đáp án tối ưu kìa, vặn óc làm gì cho khổ

drgnz · March 20, 2018, 1:16pm

Cho óc thêm nếp nhăn chớ sao

Mà xem solu vẫn không hiểu sao mấy ổng ở trên reddit nghĩ ra được.

tntxtnt · March 20, 2018, 1:15pm

dễ tìm ra mà, đọc gợi ý rồi thì thấy nó rất hợp lý

rogp10 · February 19, 2019, 12:34pm

Test nhẹ: https://oeis.org/A005245

Challenge accepted

# pseudo
def c(n: uInteger): uInteger
   sieve[1..n]: uInteger;
   sieve.iota(1); # in-joke
   for i: auto in [2..n] do
      flag: auto = sieve[i] == i;
      # có proof thì mình sẽ sửa
      sieve[i] = [sieve[j-i] + j for j in [1..sieve[i-1]].min();
      if (flag) continue;
      t: uInteger(1);
      for j: auto in [i+i..i>sqrt(n) ? n:i*i].stride(i) do # ngăn tràn số
         sieve[j] = min(sieve[j], sieve[i] + sieve[++t])
      end
  end
  return sieve.sum();
end