Olimpiade Sains Provinsi (OSP) 2014 - Komputer, Nomor 50

Strategi terbaik adalah dengan selalu membuat potongan sekecil mungkin agar kita mendapatkan potongan sebanyak mungkin pada akhirnya. Setiap ingin membuat potongan baru, kita harus memastikan bahwa potongan terbaru tersebut tidak akan membuat segitiga dengan semua potongan lain yang sudah kita buat. Cara mengecek nya adalah dengan melihat dua potongan terbesar, apakah jumlah dari kedua potongan tersebut lebih besar daripada panjang potongan yang ingin kita buat (apabila panjangnya sama maka belum membentuk segitiga).

Mari kita coba simulasikan.

Pertama, buat potongan dengan panjang 1 karena panjang minimal adalah 1.
Kedua, buat potongan dengan panjang 1 lagi karena pasti tidak membentuk segitiga (baru ada dua potongan termasuk yang baru ini).
Ketiga, buat potongan dengan panjang 2, karena apabila kita membuat potongan dengan panjang 1 maka akan membentuk segitiga.
Keempat, buat potongan dengan panjang 3, karena dua potongan terbesar menghasilkan jumlah 3.
Kelima, buat potongan dengan panjang 5, karena dua potongan terbesar menghasilkan jumlah 5.
Keenam, buat potongan dengan panjang 8, karena dua potongan terbesar menghasilkan jumlah 8.

Jika kita perhatikan, potongan ke x yang kita buat akan memiliki panjang f(x) dimana f(x) = f(x-1) + f(x-2), karena potongan ke x panjangnya adalah jumlah dari panjang potongan ke x-1 dan panjang potongan ke x-2.

Untuk setiap N, banyaknya potongan maksimal yang dapat kita buat adalah K potongan, dimana K adalah bilangan terbesar yang memenuhi syarat f(1) + f(2) + .. + f(K) <= N. Contoh, untuk N = 7 akan menghasilkan K = 4 karena f(1) + f(2) + f(3) + f(4) = 1 + 1 + 2 + 3 = 5.

Note: Karena jumlah dari panjang semua potongan harus tepat N, maka potongan terbesar kita buat sebesar mungkin sampai jumlah semua potongan tepat N.

Source code:

var
  n,i,sum,ans: longint;
  f: array[1..100] of longint;

begin
  readln(n);
  if n<=2 then writeln(n) else
  begin
    f[1] := 1;
    f[2] := 1;
    sum := 2; // f[1] + f[2]

    for i:=3 to 100 do
    begin
      f[i] := f[i-1] + f[i-2];
      sum := sum + f[i];
      if sum <= n then ans := i else break;
    end;

    writeln(ans);
  end;
end;