Suhendry’s Blog

F - New House

Problem: F - New House
Author: Suhendry Effendy

Karena batasan nilai N yang cukup kecil (hanya 10), problem ini bisa diselesaikan dengan pendekatan bruteforce. Total kompleksitas pengujian bruteforce hanya O(N^5). Algoritma ini masih bisa dioptimasi sedikit menjadi O(N^4).

Solusi C/C++
oleh Suhendry Effendy

#include <cstdio>
#include <algorithm>
using namespace std;

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

  while ( ncase-- ) {
    int n;
    scanf( "%d", &n );

    char arr[20][20];
    for ( int i = 0; i < n; i++ )
      scanf( "%s", arr[i] );

    int ans = 0;
    for ( int i = 0; i < n; i++ )
      for ( int j = 0; j < n; j++ )
        if ( arr[i][j] == '.' )
          for ( int tans = 1; ; tans++ ) {
            if ( i+tans-1 >= n || j+tans-1 >= n ) break;
            bool okay = true;
            for ( int r = i; r <= i+tans-1; r++ )
              for ( int c = j; c <= j+tans-1; c++ )
                if ( arr[r][c] == '#' ) okay = false;
            if ( !okay ) break;
            ans = max(ans,tans);
          }

    printf( "%d\n", ans );
  }

  return 0;
}

Solusi JAVA
oleh Suhendry Effendy

import java.util.*;

public class F {
  void solve() {
    Scanner scan = new Scanner(System.in);
    int T = Integer.parseInt(scan.nextLine());

    while ( T > 0 ) {
      int n = Integer.parseInt(scan.nextLine());

      String arr[] = new String[20];
      for ( int i = 0; i < n; i++ )
        arr[i] = scan.nextLine();

      int ans = 0;
      for ( int i = 0; i < n; i++ )
        for ( int j = 0; j < n; j++ )
          if ( arr[i].charAt(j) == '.' )
            for ( int tans = 1; ; tans++ ) {
              if ( i+tans-1 >= n || j+tans-1 >= n ) break;
              Boolean okay = true;
              for ( int r = i; r <= i+tans-1; r++ )
                for ( int c = j; c <= j+tans-1; c++ )
                  if ( arr[r].charAt(c) == '#' ) okay = false;
              if ( !okay ) break;
              if ( ans < tans ) ans = tans;
            }

      System.out.printf( "%d\n", ans );
      T--;
    }
  }

  public static void main(String[] args){
    new F().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