Jun 042008
 

Problem C. Panda Land 3: Text Wrapper

Deskripsi Soal C
Problem Author: Evan Leonardi

Diberikan input teks, anda diminta untuk memperbaiki formatnya agar teks tersebut bisa dicetak pada kertas yang lebarnya ditentukan (aturan formatting diberikan). Ini soal tersulit di babak penyisihan INC 2008 dan tidak ada satupun tim yang sempat menyelesaikannya sebelum waktu berakhir. Tim TSP dari BINUS hampir menyelesaikan soal ini di menit-menit terakhir, namun sayangnya mereka lupa menghapus baris debug ketika mengirimkan jawaban sehingga program mereka terkena Wrong Answer (padahal seharusnya sudah benar).

Soal ini memerlukan waktu implementasi (pembuatan program) lebih lama dibandingkan soal-soal yang lain, karena selain harus berhati-hati, peserta juga harus memperhatikan efisiensi program mereka. Pengguna C/C++ tidak disarankan untuk menggunakan STL string di sini. Sedangkan pengguna JAVA harus menggunakan BufferedReader dan BufferedWriter untuk membaca input dan menulis output (yang menggunakan Scanner pasti mendapat TLE ketika membaca input).

Solusi C/C++
oleh Evan Leonardi

spoiler

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define MAX_CHAR 3100000 + 1

void printSubStr ( char * str, int begin, int end )
{
  while( begin < end && str[begin] != 0 )
    putchar( str[begin++] );
}

int main (  )
{
  int Case = 1;
  int lebarKertas;
  int lebarKarakter[256];
  char * string = (char *)malloc( MAX_CHAR + 1 );
  int * tablen = (int *)malloc( sizeof( int ) * ( MAX_CHAR + 1 ) );

  while( scanf( "%d", &lebarKertas ) == 1 )
  {
    printf( "Case #%d:\n", Case++ );
    memset( lebarKarakter, 0, sizeof( lebarKarakter ) );

    int bufLen;
    char buffer[30];

    while( gets( buffer ) )
    {
      if( strcmp( buffer, "END OF LIST" ) == 0 ) 
        break;
      sscanf( buffer + 2, "%d", &lebarKarakter[buffer[0]] );
    }
    
    int strLen = 1;
    char ch;
    
    bufLen = 0;
    while( ( ch = getchar() ) )
    {
      if( ch == 'n' && string[strLen - 1] == '\\' )
        string[strLen - 1] = '\n';
      else if( ch != '\n' )
        string[strLen++] = ch;
      else if( ch == '\n' ) // buffer activated
      {
        buffer[bufLen] = 0;
        bufLen = strlen( buffer );
        if( strcmp( buffer, "END OF FILE" ) == 0 ) break;
        bufLen = 0;
        continue;
      }

      if( bufLen < 13 ) buffer[bufLen++] = ch;
    }
    string[( strLen -= 11 )] = 0;

    tablen[0] = 0;
    for( int i = 1; i <= strLen; ++i )
      tablen[i] = tablen[i - 1] + lebarKarakter[string[i]];

    int lastPos = 1;
    int lastSpace = 0;
    for( int i = 1; i < strLen; ++i )
    {
      ch = string[i];
      if( ch == '\n' )
      {
        printSubStr( string, lastPos, i ); putchar( '\n' );
        lastPos = i + 1;
        lastSpace = i;
      }
      else if( tablen[i] - tablen[lastPos - 1] > lebarKertas )
      {
        if( ch == ' ' )
        {
          printSubStr( string, lastPos, i ); putchar( '\n' );
          lastPos = i;
          lastSpace = i - 1;
        }
        else
        {
          if( lastSpace + 1 == lastPos )
          {
            int idx = i;
            while( tablen[idx - 1] - tablen[lastPos - 1] >= lebarKertas ) --idx;
            printSubStr( string, lastPos, idx ); puts( "-" );
            lastPos = idx;
            lastSpace = idx - 1;
            i = i - 1;
          }
          else
          {
            printSubStr( string, lastPos, lastSpace + 1 ); putchar( '\n' );
            lastPos = lastSpace + 1;
          }
        }
        
      }
      
      if( ch == ' ' )
        lastSpace = i;
    }
    printSubStr( string, lastPos, strLen ); putchar( '\n' );
  }
  
  free( string );
  free( tablen );
}

Solusi JAVA
oleh Felix Halim

spoiler

import java.util.*;
import java.io.*;

public class textwrap {
  void solve() throws IOException {
    BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    int[] W = new int[256];
    String t;

    for (int TC=1; (t = bf.readLine())!=null; TC++){
      bw.write("Case #"+TC+":\n");

      int L = Integer.parseInt(t);
      Arrays.fill(W,-1); W['\n'] = 0;
      for (String s; (s=bf.readLine())!=null; ){
        if (s.equals("END OF LIST")) break;
        W[s.charAt(0)] = Integer.parseInt(s.substring(2));
      }

      StringBuffer sb = new StringBuffer();
      for (String s; (s=bf.readLine())!=null; ){
        if (s.equals("END OF FILE")) break;
        sb.append(s);
      }

  
      char[] s = sb.toString().replaceAll("\\\\n","\n").toCharArray();
      StringBuffer cur = new StringBuffer();
      boolean first = true;
      int length = 0;

      for (int i=0; i<s.length; i++){
        if (s[i]=='\n'){
          bw.write(cur.toString());
          bw.write("\n");
          cur.setLength(0);
          length = 0;
          first = true;
        } else if (s[i]==' '){
          if (length + W[s[i]] > L){
            if (length==0) throw new RuntimeException("Space is too big");
            bw.write(cur.toString());
            bw.write("\n");
            cur.setLength(0);
            cur.append(s[i]);
            length = W[s[i]];
          } else {
            cur.append(s[i]);
            length += W[s[i]];
          }
          first = false;
        } else {
          bw.write(cur.toString());
          cur.setLength(0);
          while (i<s.length && s[i]!=' ' && s[i]!='\n'){
            if (length + W[s[i]] > L){
              if (first){
                if (length + 1 > L){
                  bw.write(cur.substring(0,cur.length()-1));
                  bw.write("-\n");
                  cur.delete(0,cur.length()-1);
                  length = W[cur.charAt(0)];
                } else {
                  bw.write(cur.toString());
                  bw.write("-\n");
                  cur.setLength(0);
                  cur.append(s[i]);
                  length = W[s[i]];
                  i++;
                }
              } else {
                bw.write("\n");
                first = true;
                length = 0;
                for (int j=0; j<cur.length(); j++)
                  length += W[cur.charAt(j)];
              }
            } else {
              cur.append(s[i]);
              length += W[s[i]];
              i++;
            }
          }
          i--;
        }
      }
      if (cur.length()>0) bw.write(cur.toString());
      bw.write("\n");
    }
    bf.close();
    bw.close();
  }
  public static void main(String[] args) throws Exception {
    new textwrap().solve();
  }
}

 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)