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. 😀
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
@okaswara
latihan terus menerus 😀 😉
SukaSuka
Wow, sangat singkat, padat dan jelas… 😮 Btw, makasih ya kk Felix! 😀
SukaSuka
Kalo gw untuk soal A.., tinggal sort aja
hurufnya, trus tinggal search secara linear.. 🙂
SukaSuka
@wilbert
susah amat? ada O(n + n) pake O(n lg n + n)…. 😛
SukaSuka
nice write up larr… :p
SukaSuka
menurut gw..
soalnya kebanyakan sortnya 😀
SukaSuka
@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….
SukaSuka
materi’a gax ada penjelasan’a …???
kurang paham..:(
SukaSuka
boleh tanya ne
SukaSuka
saya kesulitan tentang mod ne minta bantuannya :
11^100 mod 41 = ….
SukaSuka
Ping-balik: Programming | Re-reading Life