Nov 232009
 

C – String Prima

Author: Jeffrey Wijaya
Problem: klik di sini

Dengan panjang string tidak lebih dari 100 dan bilangan prima lebih kecil dari 1000 (maks. 3 digit), soal ini bisa diselesaikan dengan bruteforce. Cukup uji nC3 angka yang bisa dibentuk dari teks yang diberikan. Untuk mengatasi jika bilangan prima terbesar adalah 1 atau 2 digit, tambahkan dua angka nol di depan teks yang diberikan.

11 peserta berhasil menyelesaikan soal ini.

Solusi C/C++
oleh Eko Wibowo

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

bool isprime(int x)
{
  if ( x == 2 ) return true;
  if ( x  < 2 ) return false;
  for ( int i = 2; i * i <= x; i++ )
    if ( x % i == 0 ) return false;
  return true;
}

int main()
{
  int  T;
  char s[200];
  s[0] = s[1] = '0';
  scanf( "%d", &T );
  while ( T-- )
  {
    int ans = -1;
    scanf( "%s", s + 2 );
    int len = strlen(s);
    for ( int i  = 0; i < len; i++ )
      for ( int j = i + 1; j < len; j++ )
        for ( int k = j + 1; k < len; k++ ) {
          int temp = (s[i]-'0') * 100 + (s[j]-'0') * 10 + s[k] -'0';
          if ( isprime(temp) ) ans = max(ans,temp);
        }
    printf( "%d\n", ans );
  }
  return 0;
}

Solusi PASCAL
oleh Eko Wibowo

function isprime(x: longint): boolean;
var
  i: longint;
begin
  if ( x = 2 ) then
  begin
    isprime := true;
    exit;
  end;
  if ( x < 2 ) then
  begin
    isprime := false;
    exit;
  end;
  i := 2;
  while ( i * i <= x ) do
  begin
    if ( x mod i = 0 ) then
    begin
      isprime := false;
      exit;
    end;
    i := i + 1;
  end;
  isprime := true;
end;

var
  T, i, j, k, res, len, temp: longint;
  s: string;
begin
  readln(T);
  while ( T > 0 ) do
  begin
    T := T - 1;
    readln(s);
    s := '00' + s;
    len := length(s);
    res := -1;
    for i := 1 to len do
      for j := i + 1 to len do
        for k := j + 1 to len do
        begin
          temp := ord(s[i]-'0') * 100 + ord(s[j]-'0') * 10 + ord(s[k]-'0');
          if ( temp > res ) and isprime(temp) then res:=temp;
        end;
    writeln(res);
  end;
end.


  6 Responses to “BNPCHS 2009 – Qualification Round”

  1. saya kecewa 🙁

  2. Gw pas liat di Google Reader nongol “Suhendry’s Blog (1)” wah udah kesenengan gw akhirnya blog entah INC atawa ICPC nongol… Gak taunyaaaaa…… >>>>>>.<<<<<<<

    Hmm… jangan2 blog INC/ICPC teralu susah yah shu ;)) jadi ditunda2 mulu. Kalo HS aja langsung nongol ;))

  3. oh iya, ada ilham juga… doh, kabur dolo ah xD

  4. wkkwkwkwkwkw… gile shu… BNPCHS kluar dluan…. event belakangan, writeup keluar dluan….

  5. su…..where r u know???????

  6. hehe…mas shu lagi jd tersangka…:)

 Leave a Reply

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

(required)

(required)