Bina Nusantara Programming Contest for High School Students 2008

Problem : A | B | C | D | E | F | G | H

F - Fungsi Pak Gaus

Jika kita menyelesaikan soal ini secara naif dengan mengalikan semua bilangan sesuai dengan rumus f(a, b) yang diberikan, maka kita akan mendapatkan time limit exceeded karena jumlah perkalian yang dibutuhkan bisa mencapai O(a * b) di mana a dan b masing-masing bisa mencapai 10000. Untuk menyelesaikan soal ini, kita harus kembali memperhatikan rumus f(a, b).

f(4, 3) = (4 x 4 x 4) x (3 x 3 x 3) x (2 x 2 x 2) x (1 x 1 x 1)
        = (4 ^ 3) x (3 ^ 3) x (2 ^ 3) x (1 ^ 3)
        = (4 x 3 x 2 x 1) ^ 3
        = 4! ^ 3

Dari contoh di atas, kita dapat mengambil kesimpulan bahwa f(4, 3) adalah sama dengan (4! ^ 3). Atau secara umum, f(a, b) adalah (a! ^ b). Dengan fakta ini, kita bisa mengurangi jumlah perkalian yang diperlukan menjadi O(a + b) yang jauh lebih kecil.

fac = 4 x 3 x 2 x 1     :: total ada 3, atau (a - 1) kali perkalian
ans = 24 x 24 x 24      :: total ada 2, atau (b - 1) kali perkalian

Untuk bagian modulus kita hanya perlu mengikuti rumus yang sudah diberikan di soal.

Statistik Problem F
YES = 10
NO - Wrong Answer = 22
NO - Time Limit Exceeded = 25
NO - Run-time Error = 4
NO - Compile Error = 3

Solusi C/C++ (oleh Suhendry Effendy)

#include <cstdio>
#include <algorithm>
using namespace std;

int main()
{
  int T;
  scanf( "%d", &T );

  while ( T-- ) {
    int a, b, c;
    scanf( "%d %d %d", &a, &b, &c );

    int fac = 1, ans = 1;
    for ( int i = 1; i <= a; i++ ) fac = (fac * i) % c;
    for ( int i = 1; i <= b; i++ ) ans = (ans * fac) % c;
    
    printf( "%d\n", ans % c );
  }

  return 0;
}

Solusi Pascal (oleh Eko Wibowo)

var
  t, a, b, c, fac, ans, i : longint;
begin
  read(t);
  while (t > 0) do
  begin
    t := t - 1;
    read(a,b,c);
    fac := 1;
    ans := 1;
    for i := 1 to a do fac := (fac * i) mod c;
    for i := 1 to b do ans := (ans * fac) mod c;
    writeln(ans mod c);
  end;
end.