Final BNPC-HS 2008 Desember 15, 2008
Posted by marcadian in Event.trackback
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;
}
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.
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 ?
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 ).
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
@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
).
Sekian..
- Felix Jingga
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.
@okaswara
latihan terus menerus
Wow, sangat singkat, padat dan jelas…
Btw, makasih ya kk Felix! 
Kalo gw untuk soal A.., tinggal sort aja
hurufnya, trus tinggal search secara linear..
@wilbert
susah amat? ada O(n + n) pake O(n lg n + n)….
nice write up larr… :p
menurut gw..
soalnya kebanyakan sortnya
@Felix J
Lo coba liat code lo, sort itu keliatan seperti O(n lg n) atau O(1)??
wkwkwkw….
So, gampang ngecode yang mana? hahaha..
Sama aja sih sebenernya… wkwkw…
Kaburrrrrr….