Darkc0der
20th November 2011, 10:31 PM
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:
<span style="color: #000000">
#include
#include
#include
using namespace std;
<span style="color: #FF8000">#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) :D.
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 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 [I]pembahasan dari saya:
Ini soal sangat mudah, bisa di solve dengan kertas dan pulpen (kalo emang niat :p). Tapi bisa juga dicodingin berdasarkan pembagian cara SD, berikut potongan code saya:
PHP Code:
<span style="color: #000000">
int a = 123412;
int b = 4234;
System.out.print((a/b)+".");
a %= b;
for(int i=0;i<span style="color: #007700"><span style="color: #000000">
int calc(int n,int k) {
vector p(n);
for(int i=0;i<span style="color: #007700">
Cara O(n lg n), cara ini efisien dilakukan jika nilai n lumayan besar (n
</div>
</div>
Cara O(n), cara ini efisien dilakukan jika nilai n besar (n
<span style="color: #000000">
int calc(int n,int k) {
int ret = 0;
for(int i=2;i<span style="color: #007700">
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:
<span style="color: #000000">
#include
#include
#include
using namespace std;
<span style="color: #FF8000">#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) :D.
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 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 [I]pembahasan dari saya:
Ini soal sangat mudah, bisa di solve dengan kertas dan pulpen (kalo emang niat :p). Tapi bisa juga dicodingin berdasarkan pembagian cara SD, berikut potongan code saya:
PHP Code:
<span style="color: #000000">
int a = 123412;
int b = 4234;
System.out.print((a/b)+".");
a %= b;
for(int i=0;i<span style="color: #007700"><span style="color: #000000">
int calc(int n,int k) {
vector p(n);
for(int i=0;i<span style="color: #007700">
Cara O(n lg n), cara ini efisien dilakukan jika nilai n lumayan besar (n
</div>
</div>
Cara O(n), cara ini efisien dilakukan jika nilai n besar (n
<span style="color: #000000">
int calc(int n,int k) {
int ret = 0;
for(int i=2;i<span style="color: #007700">