ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1102. Странный диалог

please help me! Memory limit exceeded
Послано Mariana 11 июл 2013 23:35
#include <iostream>
#include <cstdlib>
#include <stdio.h>
//#pragma comment(linker, "/STACK:16777216")


using namespace std;

int flag=0;
int flag1=0;
char *a = new char [10000001];


  int f(int pos,int flag,int n){
    int l=0;
    if ((pos==n+1) && (flag==1)) {std::cout<<"YES"<<endl; flag1=1; return 0;}
    if ((pos==n+1) && (flag==0)) {}
    else if (pos<=n){
    {if ((a[pos]=='o') && (a[pos+1]=='u') && (a[pos+2]=='t') && (a[pos+3]=='p') && (a[pos+4]=='u') && (a[pos+5]=='t')) {f(pos+6,1,n);l=1;}
    if ((a[pos]=='i') && (a[pos+1]=='n') && (a[pos+2]=='p') && (a[pos+3]=='u') && (a[pos+4]=='t')) {f(pos+5,1,n);l=1;}
    if ((a[pos]=='p') && (a[pos+1]=='u') && (a[pos+2]=='t') && (a[pos+3]=='o') && (a[pos+4]=='n')) {f(pos+5,1,n);l=1;}
    if ((a[pos]=='o') && (a[pos+1]=='u') && (a[pos+2]=='t')) {f(pos+3,1,n);l=1;}
    if ((a[pos]=='o') && (a[pos+1]=='n') && (a[pos+2]=='e')) {f(pos+3,1,n);l=1;}
    if ((a[pos]=='i') && (a[pos+1]=='n')) {f(pos+2,1,n);l=1;}
    if (l==0) {}
    }}
}



int main()
{
    int k=0,n=0,j=0;
    int i=0;
    std::cin>>k;
    char c;
    for (j=1;j<=k+1;j++)
    {
        i=0; flag1=0;
        while (((c = getchar()) != '\n') ) {a[i]=c;i++;}
        n=i-1;

       if (n>0) {
                 f(0,0,n);
                  if (flag1==0) std::cout<<"NO"<<endl;}

    }




}

Edited by author 11.07.2013 23:48

Edited by author 11.07.2013 23:49
Re: please help me! Time limit exceeded
Послано Mariana 12 июл 2013 00:53
#include <iostream>
#include <cstdlib>
#include <stdio.h>
#include <string>
#include <cstring>

using namespace std;

int flag=0;
int flag1=0;
char *a = new char [10000000];

int main()
{
    int k=0,n=0,j=0,l=0;
    int i=0,pos=0;
    std::cin>>k;
    char c;
    for (j=1;j<=k+1;j++)
    {
        i=0; l=0;
        gets(a);
        n=strlen(a);n--;


        if (n>0){

        pos=n;

        while (pos>0){
        if ((a[pos]=='t') && (a[pos-1]=='u') && (a[pos-2]=='p') && (a[pos-3]=='t') && (a[pos-4]=='u') && (a[pos-5]=='o')) {l=1;pos=pos-6;}
        if ((a[pos]=='t') && (a[pos-1]=='u') && (a[pos-2]=='p') && (a[pos-3]=='n') && (a[pos-4]=='i')) {l=1;pos=pos-5;}
        if ((a[pos]=='n') && (a[pos-1]=='o') && (a[pos-2]=='t') && (a[pos-3]=='u') && (a[pos-4]=='p')) {l=1;pos=pos-5;}
        if ((a[pos]=='t') && (a[pos-1]=='u') && (a[pos-2]=='o')) {l=1;pos=pos-3;}
        if ((a[pos]=='e') && (a[pos-1]=='n') && (a[pos-2]=='o')) {l=1;pos=pos-3;}
        if ((a[pos]=='n') && (a[pos-1]=='i')) {l=1;pos=pos-2;}
        if (l==0) {break;}
         }
     if (l==1) std::cout<<"YES";
     else std::cout<<"NO";
    }}


delete [] a;

}
Re: please help me! Time limit exceeded
Послано Vedernikoff 'Goryinyich' Sergey (HSE: АОП) 12 июл 2013 14:22
Don't read the whole file (and even line!) into memory - each time you need only the last and previous words - so, this problem is solvable in O(1) memory
Re: please help me! Time limit exceeded
Послано Mariana 12 июл 2013 17:35
thanks, I understand