Coding Coding Coding

[Darkc0der]

Halo semuanya dalam thread yg saya buka ini saya akan posting soal2 tentang programming mulai dari level mudah sampai sulit. Soal2 yang saya posting akan seputar matematika dan algoritma. Thread ini saya buka bukan sebagai ajang pamer kemampuan melainkan sebagai hiburan utk mengisi waktu luang dengan berpikir dan coding.



Soal 1 [4/10]: ( Sudah terjawab oleh bobomelulu)

f(1) = 1

f(2) = 2

f(3) = 3

f(x) = f(x-1) + f(x-2) + f(x-3) untuk x>3

Berapakah nilai 4 digit terakhir dari f(1,000,000,000,000,007) ?

(tantangan dari soal ini adalah bagaimana kita menghitung nilai secara cepat).


Spoiler for pembahasan:






Soal ini membutuhkan teknik perkalian matriks, teori modular aritmatika dan cara cepat memangkatkan bilangan.



Coba perhatikan matriks berikut:



A = [1 2 3] (isinya dari f(1), f(2) dan f(3))



B = 0 0 1

1 0 1

0 1 1



Coba kalikan A dengan B maka kita akan dapatkan



[2 3 6]



kalikan lagi dengan B maka kita akan dapatkan



[3 6 11]



kalau diperhatikan setiap elemen dalam matriks tersebut akan bergeser dan elemen terakhir akan digantikan dengan nilai penjumlahan 3 elemen sebelumnya.



Nah dari situ kita bisa mengambil kesimpulan bahwa jika ingin mendapatkan nilai f(X) kita harus melakukan perkalian matriks sebanyak X-3 kali untuk mendapatkan hasil di element terakhir.

Contoh:

Mau tau nilai f(4) berarti matriks A dikalikan 1x dengan B

Mau tau nilai f(5) berarti matriks A dikalikan 2x dengan B

Mau tau nilai f(6) berarti matriks A dikalikan 3x dengan B



((A x B) x B) x B sama dengan A x (B^3)



Berarti untuk menghitung f(1,000,000,000,000,007) sama dengan A x (B^1,000,000,000,000,004)



Nah timbul lagi kesulitan bagaimana kita menghitung nilai B^1,000,000,000,000,004 dengan cepat?



Kita gunakan metode divide and conquer berikut:



ilustrasi ketika menghitung B^35:

B^35 = B^17 * B^17 * B

B^17 = B^8 * B^8 * B

B^8 = B^4 * B^4

B^4 = B^2 * B^2

B^2 = B * B



Dari situ kita lihat bahwa utk menghitung B^35 hanya membutuhkan log2(35) = 5 operasi.

Berarti untuk menghitung B^1,000,000,000,000,004 hanya membutuhkan log2(1,000,000,000,000,004) = 50 operasi.



Nah lalu karena yang diminta hanya 4 digit terakhir tiap perhitungan kita modulus 10000. Teori modular aritmetika:

(a x b) % x = ((a%x) * (b%x)) % x

(a + b) % x = ((a%x) + (b%x)) % x








Spoiler for solusi c++ saya:







PHP Code:

#include

#include

#include

using namespace std;



#define REP(i,n) for(int i=0,_n=(n);i
ans = nextInteger()

freq = 1

while hasNextInteger()

temp = nextInteger()

if ans == temp then

freq++

else

freq--

end if



if freq == 0 then

ans = temp

end if

end while



print ans

Cara ini akan menghasilkan output dengan betul karena kondisi frekuensi > 50%, saya sudah buktikan cara ini benar dengan melakukan uji coba permutasi 10 elemen (1 1 1 1 1 1 2 3 4 5) .












Spoiler for cara bobomelulu beda dengan saya:






Karena rangenya cukup di 32-bit integer, gue perlu counter sebanyak 32 element.



Untuk tiap integer, kita cari binary representationnya. Misalkan angka 5, ... ....00000101 ada index bit 0 dan 2 yg nyala ... maka gue akan increment counter[0] dan counter[2].



Begitu seterusnya sampe setiap input habis dibaca.



Mestinya nilai frequensi terbesar bisa didapet dengan melihat counter[i] untuk tiap i dari 0 s/d 31 ... Kalo nilai counter[i] > 50jt, maka bit ini pasti juga nyala di nilai yg paling sering muncul.



Gue belum test bener, tapi ini coba coba dengan input:

{ 5, 5, 6, 7, 5, 5, 5, 9 }



0 1 0 1

0 1 0 1

0 1 1 0

0 1 1 1

0 1 0 1

0 1 0 1

0 1 0 1

1 0 0 1

-------

1 7 2 7 yg lebih dari 4 adalah bit 0 dan bit 2

0 1 0 1 => 5











Soal 3 [1/10]: ( Sudah terjawab oleh mnemonix)

Hitung digit ke-50 dibelakang koma dari 123412 / 4234



Contoh kalo yang ditanyakan digit ke-5 maka jawabannya adalah 5.

123412 / 4234 = 29.147850


Spoiler for pembahasan dari saya:






Ini soal sangat mudah, bisa di solve dengan kertas dan pulpen (kalo emang niat ). Tapi bisa juga dicodingin berdasarkan pembagian cara SD, berikut potongan code saya:


PHP Code:

int a = 123412;

int b = 4234;

System.out.print((a/b)+".");

a %= b;

for(int i=0;i
int calc(int n,int k) {

vectorp(n);

for(int i=0;i

Cara O(n lg n), cara ini efisien dilakukan jika nilai n lumayan besar (n

[REGIONALBALI]

lengkap banget penyelesainya.

klo ane sendiri selesan matrik paling menggunakn matlab(biar cepet)
kecuali ujian ndan...