Final BNPC-HS 2008

Soal A (By Andrian Kurniady)

Buat array untuk frekuensi huruf dari a-z, lalu hitung ada berapa banyak yang nilanya lebih besar dari nol.

#include <cstdio>
#include <cstring>
int main()
{
  int t;
  char s[300];
  int freq[256];
  scanf("%d",&t);
  while (t--)
  {
    memset(freq,0,sizeof(freq));
    scanf("%s",s);
    int len = strlen(s);
    for(int i=0;i<len;i++) 
      if (s[i]>='a' && s[i]<='z') freq[s[i]]++;
    int res = 0;
    for(int i='a';i<='z';i++) res += (freq[i]>0);
    printf("%d\n",res);
  }
  return 0;
}

Laman: 1 2 3 4 5 6 7 8

17 comments on “Final BNPC-HS 2008”

Halo kk, saya mau tanya yang soal F, perulangan yang…

for(int i=1;i<=a;i++) p = (p * i)%c;

…melakukan faktorial, dan setiap dikalikan (dengan i) langsung dimod dengan c gitu ya?

Yang saya bingung, kan persamaannya:
(a*b)mod c = ((a mod c)*(b mod c))mod c

Kalau pakai perulangan yang diatas hasil persamaannya:
(((…((((1*1)mod c)*2)mod c)*…)mod c)*a)mod c

Jadi yang mau saya tanya persamaan yang kedua dapetnya dari mana ya? Makasih kk. 😀

SukaSuka

gni, (1 * 2 * 3 * 4) % c = ((1 * 2) * 3 * 4) % c
= (((1 * 2) * 3) * 4)%c (nah kan ud dlm btk a * b)
= {[(1*2)*3] %c * (4 %c)%c} % c
= {[(1*2)%c * (3%c)] % c * (4%c)}%c
= {[(1 % c * 2 % c) % c * (3%c)] % c * (4%c)}%c

intinya sih kamu kerjain perkaliannya sepasang2 dari depan (kan perkalian itu asosiatif)
jadi kalo 1 * 2 * 3 * 4, kerjain dl 1*2, hasilnya dikali 3, kemudian hasilnya dikali lagi dengan 4.

btw gmana soal2nya ? 😀

SukaSuka

Wah, bener juga ya, saya nggak mikir sampe situ… Tp kk, di persamaan kk nilai i-nya di mod c dulu, padahal yang di perulangan nggak, emangnya sama ya hasilnya?

Soal2nya? Kalo soal2nya sih ada yang gampang, tapi ada yang susah juga… Walaupun bener kata kk, soal tahun ini secara keseluruhan lebih gampang daripada tahun kemarin (semoga dipertahankan :p ).

SukaSuka

Bisa sama, bisa enggak, kalo kasus ini pasti sama. Bisa ga sama itu karena overflow, nah disini kan di mod maksimal dengan 10000. kalo suatu angka di mod dengan x, maka hasilnya dlm rentang 0..x-1, nah berarti kan p maks 9999 dan i juga maks 9999, kalo dikaliin langsung masih cukup dalam int. (p mod c * i mod c)mod c kan = (p*i) mod c 😀 Persamaan itu digunakan cuma untuk nilainya enggak overflow. kalo 10000! mod c dimana c maks 10000, maka hasil akhirnya kan kecil, cuma 0..c-1. Nilainya sih pasti sama kok.dah males bikin susah2, dikerjain jg kagak 😀 mending gampang2 aja lah

SukaSuka

@Okaswara

sebenarnya di soal F ini, constrainnya sudah dirubah jadi hanya 10rb, jadi tidak usah takut untuk memakai persamaan yang ada di soal.

hasil itu akan tidak sama, jika pada saat (p*i) sudah overflow…

kalo (p*i) nya lom overflow, hasilnya akan tetap sama….

karna constrain soal kecil, jadinya ini soal tidak bermasalah untuk ikut persamaan (axb)mod c = (a mod c x b mod c) mod c

tapi lain jika soalnya adalah soal yang asli (belum diturunkan constrainnya). Jika memakai soal asli, persamaan yang ada di soal kalo lsg di pake, akan mendapatkan hasil TLE. (Operasi mod, costnya mahal skali :P).

Sekian..

– Felix Jingga

SukaSuka

Duh, bener juga… Lagi-lagi saya nggak mikir sampe situ… T_T Saya agak bingung, soalnya persamaannya bersarang berkali-kali gitu… 😮 Jd kesimpulannya kita pecah jadi seperti persamaan yang bagian kanan, trus karena hasil kalinya nggak melebihi 32 bit (jadi nggak mungkin overflow), kita jadikan kayak persamaan bagian kiri lagi, maksudnya gitu ya? Btw, makasih ya kk Marcadian dan kk Felix atas bimbingannya… 😀

Kk2 saya mau nanya nih, maaf agak OOT, cara belajar algoritma/pemrograman yang bagus dan bener gimana ya? Atau mungkin kk2 bisa ngasitau saya cara belajar algoritma/pemrograman kk2 sendiri? Makasih ya sarannya. 😀

SukaSuka