492 - Pig-Latin

[eXon]

[cpp]
#include <stdlib.h>
#include <math.h>
#include <ctype.h>
#include <fstream.h>
#include <string.h>

#ifndef ONLINE_JUDGE

#include <conio.h>

#endif

int finish;
long caseNo;
#ifdef ONLINE_JUDGE
const long MAX = 2000;
#else
const long MAX = 200;
#endif

char vovels[10] = {'a', 'e', 'u', 'i', 'o', 'A', 'E', 'U', 'I', 'O'};

void Input(){
}

char *c2s(char c){
char *str = new char;
strcpy(str, "");

str[0] = c;
return str;
}

void prn(char *word){
int b = 0;

if (!strlen(word))
return;
for (int i = 0; i < 10; i++)
if (vovels == word[0]){
b = 1;
break;
}
if (b){
cout << word << "ay";
} else {
for (int j = 1; j < strlen(word); j++)
cout << word[j];
cout << word[0] << "ay";
}
}

void Solve(){
char word[MAX];
char c[MAX] = "";
int ind;

while (!cin.eof()){
cin.getline(c, MAX);
ind = 0;
strcpy(word, "");
while (ind < strlen(c)){
if (!isalpha(c[ind])){
prn(word);
cout << c[ind];
strcpy(word, "");
} else strncat(word, c2s(c[ind]), 1);
ind++;
};
if (strlen(word) > 0){
prn(word);
}
cout << endl;
if (cin.eof())
break;
}

}

void Output()
{
}

#define DEBUG_
#define MULTIINPUT_

int main(){
#ifndef ONLINE_JUDGE
ifstream is = "input.txt";
cin = is;
#ifdef DEBUG
clrscr();
cout << endl;
#else
ofstream os = "output.txt";
cout = os;
#endif
#endif

#ifdef MULTIINPUT
for (caseNo = 0; !finish; caseNo++){
#endif
Input();
#ifdef MULTIINPUT
if (caseNo)
cout << endl;
if (finish)
return 0;
#endif
Solve();
Output();
#ifdef MULTIINPUT
}
#endif
return 0;
}
//@END_OF_SOURCE_CODE
[/cpp]

[turuthok]

Please check your Solve() routine ... you have this loop:

[c]while (ind < strlen(c)){[/c]

Each time it is at the beginning of a loop, you would call strlen(c), this is not efficient at all. You might want to try to call strlen(c) once and store it into a var, and use it in your while() expression ...

And one more, allocate more chars on your string ... the judge can be using a very long string.

-turuthok-

[eXon]

I modified code according to advices of turuthok, but it is still time limit exceeded. I have tested program on input, which contained over 43000 lines and working time was about 6 seconds. Could someone send to my e-mail (orenexon@mail.ru) critical tests? Here new code:
[cpp]
#include <stdlib.h>
#include <math.h>
#include <ctype.h>
#include <fstream.h>
#include <string.h>

#ifndef ONLINE_JUDGE

#include <conio.h>

#endif

int finish;
long caseNo;
#ifdef ONLINE_JUDGE
const long MAX = 200000;
#else
const long MAX = 200;
#endif

char vovels[10] = {'a', 'e', 'u', 'i', 'o', 'A', 'E', 'U', 'I', 'O'};

void Input(){
}

char str[2];

char *c2s(char c){
strcpy(str, "");

str[0] = c;
return str;
}

void prn(char *word){
int b = 0;

if (strlen(word) == 0)
return;
char c = word[0];
b = (c == 'a' || c == 'A' || c == 'e' || c == 'E' || c == 'u' || c == 'U' || c == 'o' || c == 'O' || c == 'I' || c == 'i');
if (b){
cout << word << "ay";
} else {
for (int j = 1; j < strlen(word); j++)
cout << word[j];
cout << word[0] << "ay";
}
}

int isalp(char c){
return ((c >= 'a' && c <= 'z')||(c >= 'A' && c <= 'Z'));
}

void Solve(){
char word[MAX];
char c[MAX] = "";
long ind;

while (!cin.eof()){
strcpy(c, "");
cin.getline(c, MAX);
ind = 0;
strcpy(word, "");
int sl = strlen(c);
while (ind < sl){
if (!isalp(c[ind])){
prn(word);
cout << c[ind];
strcpy(word, "");
} else strncat(word, c2s(c[ind]), 1);
ind++;
};
if (strlen(word) > 0){
prn(word);
}
if (cin.eof())
return;
cout << endl;
}

}

void Output()
{
}

#define DEBUG_

int main(){
#ifndef ONLINE_JUDGE
ifstream is = "input.txt";
cin = is;
#ifdef DEBUG
clrscr();
cout << endl;
#else
ofstream os = "output.txt";
cout = os;
#endif
#endif

Solve();
return 0;
}
//@END_OF_SOURCE_CODE
[/cpp]

[Dominik Michniewski]

try to move static tables from solve() function to global scope ....
maybe you exceed stack size and this caused TLE....
Yes, I think too that this should cause RTE, but I had sometimes TLE when I try to get elements , which is placed out of table range index ....

Maybe this help ...

Dominik

[eXon]

Anybody, help me!!! I don't know what causes TLE in the following code. It looks correct and works with really big tests. I made changings by recommendations of Dominik Michniewski, but there is no any results.
C++:

[cpp]
#include <stdlib.h>
#include <math.h>
#include <ctype.h>
#include <fstream.h>
#include <string.h>

#ifndef ONLINE_JUDGE

#include <conio.h>

#endif

int finish;
long caseNo;
#ifdef ONLINE_JUDGE
const long MAX = 2000;
#else
const long MAX = 200;
#endif

char vovels[10] = {'a', 'e', 'u', 'i', 'o', 'A', 'E', 'U', 'I', 'O'};

void Input(){
}

char *c2s(char c){
char *str = new char;
strcpy(str, "");

str[0] = c;
return str;
}

void prn(char *word){
int b = 0;

if (!strlen(word))
return;
for (int i = 0; i < 10; i++)
if (vovels == word[0]){
b = 1;
break;
}
if (b){
cout << word << "ay";
} else {
for (int j = 1; j < strlen(word); j++)
cout << word[j];
cout << word[0] << "ay";
}
}

char word[MAX];
char c[MAX] = "";
long ind;

void Solve(){

while (!cin.eof()){
// strcpy(c, "");
cin.getline(c, MAX);
ind = 0;
strcpy(word, "");
int sl = strlen(c);
while (ind < sl){
if (!isalp(c[ind])){
prn(word);
cout << c[ind];
strcpy(word, "");
} else strncat(word, c2s(c[ind]), 1);
ind++;
};
if (strlen(word) > 0){
prn(word);
}
if (cin.eof())
return;
cout << endl;
}

}

void Output()
{
}

#define DEBUG_
#define MULTIINPUT_

int main(){
#ifndef ONLINE_JUDGE
ifstream is = "input.txt";
cin = is;
#ifdef DEBUG
clrscr();
cout << endl;
#else
ofstream os = "output.txt";
cout = os;
#endif
#endif

#ifdef MULTIINPUT
for (caseNo = 0; !finish; caseNo++){
#endif
Input();
#ifdef MULTIINPUT
if (caseNo)
cout << endl;
if (finish)
return 0;
#endif
Solve();
Output();
#ifdef MULTIINPUT
}
#endif
return 0;
}
//@END_OF_SOURCE_CODE
[/cpp]

[turuthok]

You haven't really completely done what I meant:

This is inside your prn() routine.

Code: Select all

   } else { 
      for (int j = 1; j < strlen(word); j++) cout << word[j]; 
      cout << word[0] << "ay"; 
   } 
} 

Imagine that word is 50,000 characters long. In each of this 50,000 loop (it's actually 49,999 instead of 50,000), you call strlen(word) ... this is a bad practice and needs be fixed, eventhough it might not solve all your problems) ... Why is it a bad practice ?? Because strlen(word) in this case will always return 50,000. But, to get to return 50,000 the strlen function has to go from the beginning of string and find a terminating zero ... that itself is a loop of 50,000 times.

So, you have a loop of 50,000 and each time you'll again implicitly have a loop of 50,000 .... that is a total of 25,000,000 .... and I believe the judge can have more than 50,000 chars word length.

I'm very sure there's another quick and simpler way to print a string starting from the second character like you're trying to do there ....

-turuthok-

[turuthok]

eXon, I missed one more thing ... you also use strncat function ... I don't really use this function ... but, I'm pretty sure it would also have to find the end-of-string before concatenating with the second string ... this also is time consuming ... I suggest you don't use this function and instead maintain an array yourself and you keep your current index, ...

Simply speaking, ... you have to know the functions that you use otherwise it won't help you but give you headache instead ... I'm sure you can't figure out what caused your TLE because of those implicit loops inside those functions you use.

-turuthok-

[eXon]

I removed calling of strncat function and reduced using of strlen, but ... you understand me. I used file to test this program which has size of 1 648 934 bytes. Program worked with this file within 5 seconds, but I haven't got AC yet. Now global variable ind_ means current position in word and when prn is called it has a value whish equals to strlen(word)[/b]. I thought it would bring me AC. Check it:

[cpp]
#include <stdlib.h>
#include <math.h>
#include <ctype.h>
#include <fstream.h>
#include <string.h>

#ifndef ONLINE_JUDGE

#include <conio.h>

#endif

int finish;
long caseNo;
#ifdef ONLINE_JUDGE
const long MAX = 200000;
#else
const long MAX = 200;
#endif

char vovels[10] = {'a', 'e', 'u', 'i', 'o', 'A', 'E', 'U', 'I', 'O'};

void Input(){
}

char str[2];

char *c2s(char c){
strcpy(str, "");

str[0] = c;
return str;
}

int ind_;

void prn(char *word){
int b = 0;

if (strlen(word) == 0)
return;
char c = word[0];
b = (c == 'a' || c == 'A' || c == 'e' || c == 'E' || c == 'u' || c == 'U' || c == 'o' || c == 'O' || c == 'I' || c == 'i');
if (b){
cout << word << "ay";
} else {
int sl = ind_;
for (int j = 1; j < sl; j++)
cout << word[j];
cout << word[0] << "ay";
}
}

int isalp(char c){
return ((c >= 'a' && c <= 'z')||(c >= 'A' && c <= 'Z'));
}

char word[MAX];
char c[MAX] = "";
long ind;

void Solve(){
while (!cin.eof()){
ind_ = 0;
// strcpy(c, "");
cin.getline(c, MAX);
ind = 0;
strcpy(word, "");
int sl = strlen(c);
while (ind < sl){
if (!isalp(c[ind])){
prn(word);
cout << c[ind];
strcpy(word, "");
ind_ = 0;
} else {
// strncat(word, c2s(c[ind]), 1);
word[ind_++] = c[ind];
word[ind_] = 0;
}
ind++;
};
if (strlen(word) > 0){
prn(word);
}
if (cin.eof())
return;
cout << endl;
}

}

void Output()
{
}

#define DEBUG_

int main(){
#ifndef ONLINE_JUDGE
ifstream is = "input.txt";
cin = is;
#ifdef DEBUG
clrscr();
cout << endl;
#else
ofstream os = "output.txt";
cout = os;
#endif
#endif

Solve();
return 0;
}
//@END_OF_SOURCE_CODE
[/cpp]

[turuthok]

Did you still get it TLE ??? Or was it a WA ???

-turuthok-

[eXon]

I extremely changed my code. It works faster than previous, but I can't get AC (TLE appears every time I submit ). This program doesn't use any routines calls (instead isalpha). It reads file symbol by symbol and checks: if current char is a letter but previous isn't the new word starts (I write current symbol, first letter if it is consonant and finally "ay"). Else it just writes currnet symbol. The first letter of "consonant-starting" word is stored in variable fst (If word begins from vovel it contains zero-char). Previous and current symbols are stored in last and curr.
[cpp]
#include <stdlib.h>
#include <math.h>
#include <ctype.h>
#include <fstream.h>
#include <string.h>

#ifndef ONLINE_JUDGE

#include <conio.h>

#endif

int finish;
long caseNo;
#ifdef ONLINE_JUDGE
const long MAX = 200000;
#else
const long MAX = 200;
#endif

int isalp(char c){
return ((c >= 'a' && c <= 'z')||(c >= 'A' && c <= 'Z'));
}

void Solve(){
char curr = 0, last, fst = 0;
char s[2] = "";

while (!cin.eof()){
// reading next char
last = curr;
cin.getline(s, 2);
curr = s[0];
// If eoln
if (curr == 0)
cout << endl;
else
if (!isalpha(curr)){
if (!isalpha(last))
cout << curr;
else {
if (fst)
cout << fst;
cout << "ay" << curr ;
fst = 0;
}
} else {
if (!isalpha(last)){
if (curr == 'a' || curr == 'A' || curr == 'e' || curr == 'E' || curr == 'u' || curr == 'U'
|| curr == 'o' || curr == 'O' || curr == 'i' || curr == 'I'){
// fst = 0;
cout << curr;
} else
fst = curr;
} else cout << curr;
}
if (cin.eof())
return;
}
}

void Output()
{
}

#define DEBUG_

int main(){
#ifndef ONLINE_JUDGE
ifstream is = "input.txt";
cin = is;
#ifdef DEBUG
clrscr();
cout << endl;
#else
ofstream os = "output.txt";
cout = os;
#endif
#endif

Solve();
return 0;
}
//@END_OF_SOURCE_CODE
[/cpp]

[eXon]

I made this message just to place my topic to the top of the list. See above.

[Dominik Michniewski]

What's your output for this:

% $ # @ @ ala
$$$$ala

?

Do you think it's correct I don't think so )) (You miss output not-words...)

Maybe this help
Dominik

[Daredevil]

What's wrong with this:

C :

#include<stdio.h>
#include<string.h>
#include<ctype.h>
long len,i,k,dir;
char a[1000000];
void main(){
while(gets(a)){
len=strlen(a);
for(i=0;i<len;i++){
if(isalpha(a)){
if(a=='A'||a=='a'||a=='i'||a=='I'||a=='e'||a
=='E'||a=='u'||a=='U'||a=='o'||a[i]=='O'){dir=1;}
else{dir=2;}
}
if(dir!=0){
if(dir==1){
while(isalpha(a[i])){printf("%c",a[i]);i++;}
printf("ay");i--;
}
else{
k=i;i++;
while(isalpha(a[i])){printf("%c",a[i]);i++;}
printf("%c",a[k]);printf("ay");i--;
}
dir=0;
}
else{printf("%c",a[i]);}
}
printf("\n");
}
}

[angga888]

Set the array to 1500000, and you will get Accepted.

Good Luck!

[eXon]

I want to thank everybody who gave me useful advices. I finally got AC .