Skip to content
27 Desember 2008 / Jeffrey Hermanto Halimsetiawan

Problem Solving – Bilangan Biner NPC Qualification Round



UPDATE : 26 Oktober 2009
Problem Biner
National Programming Contest [NPC] Qualification Round
Schematics 2009 HMTC - ITS

PROBLEM A (BEBAS)
TIME LIMIT : 1 detik
Cari jumlah angka 1 pada bilangan biner dari bilangan desimal antara 1 ­- N
Misal : 5
0001 = 1
0010 = 1
0011 = 2
0100 = 1
0101 = 2
Total = 7
Input :
 0 <= T <= 10 ­­> Jumlah Test Case
 0 <= N <= 150000000
Output :
Jumlah angka 1 pada bilangan biner nya mulai dari 1 ­ N
Sample Input :
4
0
10
100000000
150000000
Sample Output :
0
17
1314447116
2014995018

Sepintas soal ini terlihat mudah bagi kita, banyak orang yang akan berpikir seperti ini:
misal : N = 5
i = 1
1 / 2 = 0 sisa 1
i = 2
2 / 2 = 1 sisa 0
1 / 2 = 0 sisa 1
i = 3
3 / 2 = 1 sisa 1
1 / 2 = 0 sisa 1
i = 4
4 / 2 = 2 sisa 0
2 / 2 = 1 sisa 0
1 / 2 = 0 sisa 1
i = 5
5 / 2 = 2 sisa 1
2 / 2 = 1 sisa 0
1 / 2 = 0 sisa 1  +
------------------
Jumlah '1'   = 7 

TAPI, coba lihat soal lagi batas N = 150000000 (seratus lima puluh juta) dan time limit nya hanya 1 detik.
Jika kita pakai cara ini dan kita masukkan nilai N = 150000000 maka akan membutuhkan waktu lebih dari 1 menit untuk menghasilkan outputnya.

Nah, jadi solusinya kita harus "mengakali" soal tersebut.
Caranya dapat ditemukan, jika kita melihat pola bilangan biner seperti ini :
Misal : N = 15
A3 A2 A1 A0
 0  0  0  0
 0  0  0  1
 0  0  1  0
 0  0  1  1
 0  1  0  0
 0  1  0  1
 0  1  1  0
 0  1  1  1
 1  0  0  0
 1  0  0  1
 1  0  1  0
 1  0  1  1
 1  1  0  0
 1  1  0  1
 1  1  1  0
 1  1  1  1

Dari pola di atas dapat terlihat :
A0 0 1 0 1 0 1 0 1 . . .       --> 0, 1 kali  - 1, 1 kali, dst
1 set : 0 1 --> 2 bilangan
A1 0 0 1 1 0 0 1 1 . . .       --> 0, 2 kali  - 1, 2 kali, dst
1 set : 0 0 1 1 --> 4 bilangan
A2 0 0 0 0 1 1 1 1 . . .       --> 0, 4 kali  - 1, 4 kali, dst
1 set : 0 0 0 0 1 1 1 1 --> 8 bilangan
A3 0 0 0 0 0 0 0 0 1 1 1 . . . --> 0, 8 kali  - 1, 8 kali, dst
1 set : 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 --> 16 bilangan 

Algoritmanya :
1. N = 15, cari jumlah bit (binary digit) nya = 4 bit
2. Buat looping sebanyak jumlah bitnya
3. Mulai dari A0
   count += N / set * set / 2;
         += 15 / 2 * 2 / 2
         += 7
   countMod = N % set + 1 - set /2;
            = 15 % 2 + 1 - 2/2
            = 1 + 1 - 1
            = 1
   if (countMod > 0)
       count += countMod;
             += 1
   Jadi, jumlah '1' pada A0 = 7 + 1 = 8

   Kemudian, A1
   count += N / set * set / 2;
         += 15 / 4 * 4 / 2
         += 6
   countMod = N % set + 1 - set /2;
            = 15 % 4 + 1 - 4/2
            = 3 + 1 - 2
            = 2
   if (countMod > 0)
       count += countMod;
             += 2
   Jadi, jumlah '1' pada A1 = 6 + 2 = 8

   Kemudian, A2
   count += N / set * set / 2;
         += 15 / 8 * 8 / 2
         += 4
   countMod = N % set + 1 - set /2;
            = 15 % 8 + 1 - 8/2
            = 7 + 1 - 4
            = 4
   if (countMod > 0)
       count += countMod;
             += 4
   Jadi, jumlah '1' pada A2 = 4 + 4 = 8

   Kemudian, A3
   count += N / set * set / 2;
         += 15 / 16 * 16 / 2
         += 0
   countMod = N % set + 1 - set /2;
            = 15 % 16 + 1 - 16/2
            = 15 + 1 - 8
            = 8
   if (countMod > 0)
       count += countMod;
             += 8
   Jadi, jumlah '1' pada A3 = 0 + 8 = 8
4. Total jumlah '1' pada A3-A2-A1-A0 = 8 + 8 + 8 + 8
                                     = 32

Algoritmanya seperti diatas, akan jauh lebih cepat daripada cara yg
dibahas di awal tadi. Pada algoritma ini, kita hanya "mengakali"
soal dengan menggunakan perhitungan aritmatik dan perulangan yang
hanya sedikit saja.
Time limit 1 detik sudah lebih dari cukup untuk memproses output
di atas. Mudah kan..
  1. guess / Nov 7 2009 10:26

    cara menampilkan susunan angka2 dalam format sebagai berikut tu gimana mas codingannya :

    1
    2 2
    3 3 3
    4 4 4 4

    kirim ke emailq ya mas🙂

    • Jeffrey Hermanto / Nov 8 2009 13:45

      Mudah kq untuk soal seperti itu :

      
      #include 
      #include 
      
      int main(){
          int N, i, j;
          printf("Input : ");
          scanf("%d",&N);
          for (i=0;i<N;i++){
              for (j=0;j<=i;j++){
                  printf("%d ",i+1);
              }
              printf("\n");
          }
         getch ();
          return 0;
      }
      

      semoga bisa dpahami dan bermanfaat😀

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s

%d blogger menyukai ini: