Suhendry’s Blog

E - Palapa Number

Problem: E - Palapa Number
Author: Suhendry Effendy

Panjang digit yang mencapai 100 membuat program ini tidak bisa di-bruteforce begitu saja. Namun dengan prinsip Inklusi Eksklusi, problem ini bisa diselesaikan dengan mudah.

S : Semua bilangan desimal N digit.
A : Semua bilangan desimal N digit no leading zero yang dua digit depannya berjumlah genap.
B : Semua bilangan desimal N digit no leading zero yang dua digit akhirnya adalah prima.

Tentunya jawaban yang diharapkan adalah A u B. A u B dapat dihitung dengan S - ~(A u B) atau A + B - A n B.

Banyaknya bilangan 2 digit non leading zero yang jumlahnya genap adalah 45. Sedangkan banyaknya bilangan 2 digit yang prima adalah 25. Dengan demikian, nilai A, B dan A n B bisa dihitung dengan:

A = 45 * 10^(N-2)
B = 25 * 9 * 10^(N-3)
A n B = 45 * 25 * 10^(N-4)

Untuk B jangan lupa dengan non leading zero nya. Dengan demikian,

A u B = 45 * 10^(N-2) + 25 * 9 * 10^(N-3) - 45 * 25 * 10^(N-4)

Berikutnya tinggal gunakan aritmatika modulo untuk mengatasi modulo 9973 nya.

Solusi C/C++
oleh Suhendry Effendy

#include <cstdio>
using namespace std;

const int mod = 9973;

int power(int a, int n) {
  int ret = 1;
  while ( n-- > 0 ) ret = (ret * a) % mod;
  return ret;
}

int main()
{
  int T;
  scanf( "%d", &T );

  while ( T-- > 0 ) {
    int n;
    scanf( "%d", &n );
    int a = 45 * power(10,n-2);
    int b = 25 * 9 * power(10,n-3);
    int c = 45 * 25 * power(10,n-4);
    printf( "%d\n", (((a + b - c) % mod) + mod) % mod );
  }

  return 0;
}

Solusi JAVA
oleh Suhendry Effendy

import java.util.*;

public class E {
  int mod = 9973;

  int power(int n, int p) {
    int ret = 1;
    while ( p > 0 ) { ret = (ret * n) % mod; p--; }
    return ret;
  }

  void solve() {
    Scanner scan = new Scanner(System.in);
    int T = scan.nextInt();
    while ( T > 0 ) {
      int n = scan.nextInt();
      int a = 45 * power(10,n-2);
      int b = 25 * 9 * power(10,n-3);
      int c = 45 * 25 * power(10,n-4);
      System.out.printf( "%d\n", (((a + b - c) % mod) + mod) % mod );
      T--;
    }
  }

  public static void main(String[] args){
    new E().solve();
  }
}

• Problem A - General Election
• Problem B - Liar Game
• Problem C - Why is Math Book So Sad?
• Problem D - Noodle Team Contest
• Problem E - Palapa Number
• Problem F - New House

Pages: 1 2 3 4 5 6 7