Pembahasan Soal Kartu

Soal ini dibuat bukan untuk level IOI karena batasan data masih memungkinkan cara-cara konvensional tanpa perlu adanya trick-trick canggih. Singkatnya, solusinya dapat dibuat secara naif dan sederhana sbb.

Pertama anda memerlukan suatu array untuk menyimpan urutan kartu-kartu tsb dan kita sebut array X, yang berindeks 0, 1, 2, ..., N-1. Untuk memudahkan algoritma maka kita nomori ulang setiap kartu dengan mengurangi 1 pada setiap angka. Jadi X[i] array mula-mula berisi kartu i.

Jika jumlah baris adalah k dimana k=N/3, deal demi deal isi array akan mengalami pemindahan isi sbb. Kartu yang ada di X[0] tetap pada x[0],
kartu di X[1] pindah ke X[k],
kartu di X[2] pindah ke X[2k],
kartu di X[3] pindah ke X[1],
kartu di X[4] pindah ke X[k+1],
kartu di X[5] pindah ke X[2k+1],
kartu di X[6] pindah ke X[2],
kartu di X[7] pindah ke X[k+2]
... dst

sehingga secara umum
kartu di X[j] akan pindah ke X[(j mod 3) * k + j div 3].

Dalam implementasinya tentu saja operasinya dilakukan pada array yang berbeda sbb.

    for j := 0 to N-1 do 
        Y[(j mod 3) * k + j div 3] := X[j];
    X := Y;       

Pada setiap deal nomor kolom dimana kartu yang diambil tsb berada disebutkan, yaitu kolom c, dan kartu-kartu pada kolom c tsb ditandai. Untuk penandaannya ada yang menggunakan flag boolean, yaitu dengan menandai false kartu-kartu yang tidak berada di kolom c (inisialisasi semua true). Kartu-kartu i dengan flag[i] =true semakin lama semakin sedikit dan akhirnya tersisa kartu yang mungkin.

Cara tersebut memerlukan iterasi sebanyak jumlah kartu. Cara lain yang lebih efisien adalah menggunakan counter. Sebelum deal-deal dilakukan, setiap count[j] diinisialisasi 0. Ketika masukan adalah kolom c (c =1, 2, atau 3) maka counter dari setiap kartu pada kolom tsb bertambah 1. Dalam Pascal:

	for i := 0 to k-1 do
                inc(count[X[(c-1)+i*3]]);

yang hanya melakukan N/3 iterasi saja. Cara ini akan semakin lebih efisien jika dalam soal jumlah kolom besar.

Untuk soal standart IOI, biasanya ukuran data di paskan ke ukuran maksimum memori yang bisa digunakan sehingga cara-cara naif seperti ini masih perlu diefisienkan lagi.

Misalnya operasi deal kartu hanya dilakukan pada array X saja. Misalnya kita mulai dari X[1] dipindahkan ke X[k], X[k] dipindahkan ke X[(k mod 3)*k + k div 3], dst.

Jika jumlah deal adalah ITER maka kartu-kartu yang mungkin adalah kartu-kartu j dengan COUNT[j] = ITER.

    first := true;
    for j := 0 to N-1 do begin
        if (COUNT[j] = ITER) begin
            if not first then begin 
                write(' ');  
                first := false
            end;
            write(j+1)  {penomoran kartu dikembalikan ke urutan dari 1, 2, …}
        end
    end;