11988 - Broken Keyboard (a.k.a. Beiju Text)

All about problems in Volume 119. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

MauriWilde
New poster
Posts: 14
Joined: Sun Jan 20, 2013 1:58 am

11988 - Broken Keyboard (a.k.a. Beiju Text)

Post by MauriWilde » Tue Jan 29, 2013 5:04 am

Why am I getting TLE in this problem?

My code (c++):

Code: Select all

#include <iostream>

using namespace std;

int main()
{
    string s;
    while(getline(cin, s))
    {
        bool sw = true;
        string ans = "";
        string aux = "";
        for (int i=0; i<s.length(); i++)
        {
            if (s[i] == ']')
                sw = true;
            else if (s[i] == '[')
            {
                sw = false;
                ans = aux + ans;
            }
            else if (sw)
                ans += s[i];
            else if (!sw)
                aux += s[i];
        }
        ans = aux + ans;
        cout << ans << endl;
    }
    return 0;
}
Thank you ^_^

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11988 - Broken Keyboard (a.k.a. Beiju Text) TLE

Post by brianfry713 » Tue Jan 29, 2013 11:22 pm

You could speed up the input by using scanf.

You could use a list or deque instead of a string to build the output faster.
Check input and AC output for thousands of problems on uDebug!

awinashse
New poster
Posts: 2
Joined: Tue Jan 29, 2013 10:27 am

Re: 11988 - Broken Keyboard (a.k.a. Beiju Text) TLE

Post by awinashse » Thu Jan 31, 2013 7:55 am

How can I speed up my code.. I am getting TLE for this porblem. :(

Code: Select all

#include<stdio.h>
char input[100000],append[100000],output[100000];
int main() {
 int ob,i,oi,ai;
 while(gets(input)) {
 ob=oi=ai=0;
 for(i=0;i<strlen(input);i++){
   if(input[i]=='[') {
     ob++;
     strcat(append,output);
     strcpy(output,append);
     memset(append, 0, sizeof(append));
     oi+=ai;
     ai=0;
     continue;
   }
   if(input[i]==']') {
     ob--;
     strcat(append,output);
     strcpy(output,append);
     memset(append, 0, sizeof(append));
     oi+=ai;
     ai=0;
     continue;
   }
   if(ob==0){
     output[oi++]=input[i];
   }
   if(ob > 0) {
     append[ai++]=input[i];
   }
 }
 printf("%s\n",output);
 memset(output,0,sizeof(output));
 }
 return 0;
}

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11988 - Broken Keyboard (a.k.a. Beiju Text) TLE

Post by brianfry713 » Thu Jan 31, 2013 8:52 pm

You could use a list or deque instead of a string to build the output faster.
Check input and AC output for thousands of problems on uDebug!

Halah
New poster
Posts: 4
Joined: Mon Jul 22, 2013 3:24 pm

Re: 11988 - Broken Keyboard (a.k.a. Beiju Text) TLE

Post by Halah » Mon Jul 22, 2013 3:44 pm

Hi all,

I got WA .. what is the wrong in my code? :(

My code (JAVA):

Code: Select all

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

public class Main {
    
    public static void main(String[] args) throws Exception {
        
        BufferedReader br = new BufferedReader (new InputStreamReader (System.in));
        StringBuilder sb = new StringBuilder();
        boolean home = true;
        String s = br.readLine();

        List<Character> text;
        List<Character> beijuT;
        
        while(s != null)
        {
            text = new LinkedList<Character>();
            beijuT = new LinkedList<Character>();
            for (int i = 0; i < s.length(); i++) {
                
                if (s.charAt(i) == ']')
                    home = true;
                else if (s.charAt(i) == '[')
                {
                    home = false;
                } 
                else if (home)
                    text.add(s.charAt(i));
                else if (!home)
                    beijuT.add(s.charAt(i));
                
            }
            for(Character ch: beijuT)
                sb.append(ch);
            
            for(Character ch: text)
                sb.append(ch);
            
            sb.append("\n");
            
            s = br.readLine();
        }
        sb.deleteCharAt(sb.length()-1);
        System.out.println(sb);
    }
    
}



brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11988 - Broken Keyboard (a.k.a. Beiju Text) TLE

Post by brianfry713 » Tue Jul 23, 2013 1:36 am

Try the gift I/O, the link is at:
http://uva.onlinejudge.org/index.php?op ... ontest=278
Input:

Code: Select all

a[b[c
Output should be:

Code: Select all

cba
Check input and AC output for thousands of problems on uDebug!

raj
Learning poster
Posts: 78
Joined: Fri Feb 15, 2013 5:39 pm

Re: 11988 - Broken Keyboard (a.k.a. Beiju Text) TLE

Post by raj » Thu Aug 22, 2013 8:47 am

Need Help .... :( :( I am getting TLE
and i also know the idea that in c++ i could do it easily by using Iteraor.begin() and Iterator.end() method... if i want to do this kind of activity in java what the way can i do???

Code: Select all

ACCEPTED

Last edited by raj on Fri Aug 23, 2013 7:25 am, edited 1 time in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11988 - Broken Keyboard (a.k.a. Beiju Text) TLE

Post by brianfry713 » Fri Aug 23, 2013 12:46 am

Replace lines 28-33 with:
for(Character ch: l)
z.write(ch);
Check input and AC output for thousands of problems on uDebug!

raj
Learning poster
Posts: 78
Joined: Fri Feb 15, 2013 5:39 pm

Re: 11988 - Broken Keyboard (a.k.a. Beiju Text) TLE

Post by raj » Fri Aug 23, 2013 7:24 am

Thanks sir... :)

User avatar
uDebug
A great helper
Posts: 475
Joined: Tue Jul 24, 2012 4:23 pm

Re: 11988 - Broken Keyboard (a.k.a. Beiju Text) TLE

Post by uDebug » Tue Jan 21, 2014 8:50 am

I'm enclosing links to the input / output that brianfry713 mentioned above and that I found very useful during testing / debugging. I'm unable to post the actual input and output here since it's too big.

(Link to) Input:
http://pastebin.com/33Yd2Xz2

(Link to) AC Output:
http://pastebin.com/2gRmgyZB
Check input and AC output for over 7,500 problems on uDebug!

Find us on Facebook. Follow us on Twitter.

qwer452369
New poster
Posts: 2
Joined: Fri Mar 28, 2014 4:24 pm

UVA 11988

Post by qwer452369 » Fri Mar 28, 2014 4:46 pm

I don't know how to print after sending a line, press enter didn't work...

Code: Select all

#include<iostream> 
using namespace std;
struct letter{
	char chr;
	letter *next;
};
int main(){
	char input;
	letter head, tail, *p, *tmp;
	bool isFirst=1, HorE=0;//HorE: 1=HOME, 0=END
	while(cin>> input){
		if(input!='\n'){
			if(input=='['){
				HorE=1;
				tmp=&head;
			}
			else if(input==']'){
				HorE=0;
				tmp=tail.next;
			}
			else{
				if(isFirst){
					p = new letter;
					head.next = p;
					tail.next= p;
					p->chr=input;
					p->next=NULL;
					tmp = p;
					
					isFirst=0;
				}
				else{
					if(HorE==1){
						p = new letter;
						p->chr = input;
						p->next = tmp->next;
						tmp->next=p;
						tmp=p;
					}
					else if(HorE==0){
						p = new letter;
						p->chr = input;
						p->next = NULL;
						tmp->next=p;
						tail.next=p;
						tmp=p;
					} 
				}
				
			}
		}
		else{
			for(p=head.next;p!=NULL;p=p->next){
				cout << p->chr;
			}
		}
	}
	
}

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: UVA 11988

Post by brianfry713 » Fri Mar 28, 2014 10:38 pm

Your code isn't printing anything when I run it on the sample input
Check input and AC output for thousands of problems on uDebug!

qwer452369
New poster
Posts: 2
Joined: Fri Mar 28, 2014 4:24 pm

Re: UVA 11988

Post by qwer452369 » Wed Apr 02, 2014 10:23 am

brianfry713 wrote:Your code isn't printing anything when I run it on the sample input
that's because i didn't figure out how to print after pressing enter,
so you should press enter, than input EOF(Ctrl+Z for windows)

And thanks for your help :D , I've figured it out these days !

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: UVA 11988

Post by brianfry713 » Wed Apr 02, 2014 9:50 pm

I find it easier to redirect a file to stdin.

In UNIX I would copy the sample input to 11988.in, and the sample output to 11988.out, compile your code using g++ to a.out, then you can run
./a.out < 11988.in
or
./a.out < 11988.in | diff - 11988.out
Check input and AC output for thousands of problems on uDebug!

sajal2k8
New poster
Posts: 16
Joined: Mon Nov 18, 2013 5:15 pm

11988 RE why?

Post by sajal2k8 » Fri Sep 19, 2014 10:39 am

I am getting runtime error. Please help.

Code: Select all

#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
    string s,str="",strt[10000],t="";
    int check=0,stri=0;
    while(getline(cin,s))
    {
        for(int i=0;i<s.length();i++)
        {

            if(s[i]=='[')
            {
                i++;
                while(s[i]!='[' && s[i]!=']' && i!=s.length())
                {
                    str +=s[i];
                    i++;
                    check=1;
                }
                if(check==1)
                {
                  strt[stri]=str;
                  str="";
                  stri++;
                    i--;
                    check=0;
                }
            }
            else if(s[i]==']')
            {
                i++;
                while(s[i]!='[' && s[i]!=']' && i!=s.length())
                {
                    t +=s[i];
                    i++;
                    check=1;
                }
                if(check==1)
                {
                    i--;
                    check=0;
                }
            }
            else
            {
                t +=s[i];
            }
        }
        for(int i=stri-1;i>-1;i--)
            cout<<strt[i];
        cout<<t<<endl;
        check=0,stri=0,t="";
    }
    return 0;
}
Thanks in advance :) :D

Post Reply

Return to “Volume 119 (11900-11999)”