Problem A. Superstitious Skylab Tower
Problem Author: Ryan Leonel
Problem yang ingin kita selesaikan bisa ditulis dalam kalimat: ada berapa lantai valid di bawah lantai k? Sebelum menyelesaikan soal ini, kita coba dulu sub-problem yang lebih mudah: ada berapa lantai valid yang panjang digitnya tidak lebih dari n. Dengan demikian, kita fokuskan dulu pada bagaimana cara menghitung jumlah lantai yg valid dari 0 s/d 99...9 (sesuai panjang digit maksimal).
Sub problem tersebut dapat diselesaikan dengan membuat state f(n, p) dengan n adalah panjang digit dan p adalah angka sebelumnya (diperlukan karena kita ingin mencegah munculnya kombinasi angka 13). f(n, p) dapat diselesaikan dengan mencoba semua angka pada digit terdepan dan menghindari angka 4 serta 3 (jika angka sebelumnya adalah 1).
Setelah sub problem di atas diselesaikan, kita bisa memanfaatkannya untuk menyelesaikan soal ini. Caranya dengan memecah k menjadi beberapa komponen sedemikin sehingga setiap komponen bisa diselesaikan dengan fungsi f(n, p) di atas. Contohnya:
k = 2867
2867 : 0000 - 1999 (n = 3) -> 0000-0999, 1000-1999
2867 : 2000 - 2799 (n = 2) -> 2000-2099, 2100-2199, ..., 2700-2799
2867 : 2800 - 2859 (n = 1) -> 2800-2809, 2810-2819, ..., 2850-2859
2867 : 2860 - 2866 (n = 0) -> 2860-2860, 2861-2861, ..., 2866-2866
Setelah mendapatkan jumlah lantai yang ada di bawah k, kita tinggal mengalikan hasilnya dengan tinggi setiap lantai (h).
Solusi C/C++
oleh Suhendry Effendy
#include <cstdio>
#include <algorithm>
using namespace std;
long long dp[13][10];
bool valid(int a, int b) { return !(a == 1 && b == 3) && b != 4; }
long long f(int n, int p) {
if ( dp[n][p] != -1 ) return dp[n][p];
long long &ret = dp[n][p] = 0;
for ( int i = 0; i < 10; i++ )
if ( valid(p, i) ) ret += f(n - 1, i);
return ret;
}
int main()
{
memset(dp,-1,sizeof(dp));
for ( int i = 0; i < 10; i++ ) dp[0][i] = 1;
int T;
scanf( "%d", &T );
while ( T-- ) {
long long k, h, ans = 0;
scanf( "%I64d %I64d", &k, &h );
for ( int n = 1; k != 0; n++ ) {
int t = k % 10; k /= 10;
for ( int i = 0; i < t; i++ )
if ( valid(k % 10, i) ) ans += f(n - 1, i);
}
printf( "%I64d\n", ans * h );
}
return 0;
}
Solusi JAVA
oleh Suhendry Effendy
import java.util.*;
public class Super {
long[][] dp = new long[13][10];
boolean valid(int a, int b) {
return !(a == 1 && b == 3) && b != 4;
}
long f(int n, int p) {
if ( dp[n][p] != -1 ) return dp[n][p];
long ret = 0;
for ( int i = 0; i < 10; i++ )
if ( valid(p, i) ) ret += f(n - 1, i);
return dp[n][p] = ret;
}
void solve() {
for (long[] m : dp) Arrays.fill(m,-1);
for ( int i = 0; i < 10; i++ ) dp[0][i] = 1;
Scanner scan = new Scanner(System.in);
int T = scan.nextInt();
while ( T-- > 0 ) {
long k, h, ans = 0;
k = scan.nextLong();
h = scan.nextLong();
for ( int n = 1; k != 0; n++ ) {
int t = (int)(k % 10); k /= 10;
for ( int i = 0; i < t; i++ )
if ( valid((int)(k % 10), i) ) ans += f(n - 1, i);
}
System.out.println(ans * h);
}
}
public static void main(String[] args){
new Super().solve();
}
}
|