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

Обсуждение задачи 1769. Старая уральская легенда

TLE on test #6 (C++) how to improve algorithm?
Послано Ernestas 25 сен 2011 21:59
Can't get past test #6 (Time limit exceeded) and I have no idea how could I improve/change the algorithm, looking for suggestions ;P. Thanks. Here's the code (with comments ^^):

#include <cstdlib>
#include <iostream>
#include <string>
using namespace std;

int powering(int n){
    int r = 1;
    for (int i = 0; i<n; i++){ r = r*10;}
    return r;
    }

int main(int argc, char *argv[])
{
    std::string inputNumber;
    std::cin >> inputNumber;
    int length = inputNumber.length();
    char digits[100001];
    int num[100001];

    for (int i=0; i<length; i++){ //reading input
            digits[i] = inputNumber[i]; num[i] = digits[i] - '0';}

    for (int i=0; i<length; i++) // starting cycle for all n
        {
            int q = powering(i);
            int n = q;          // n = 10^i
            bool unique;
            for(int m = 0; m<(q*10); m++){ // running through every number in 10^i to 10^(i+1)-1

                unique = true;
                for(int j = 0; j<(length-i); j++) //with a given number, checking if it's in the string;
                {
                        int temp = n;
                        for(int x = j+i; x>=j; x--){ // checking if the number is unique in given position // x = current digit, i = number of digits (zero based)
                                temp = temp - num[x];
                                if(temp == 0){unique = false; break;}
                                if(temp % 10 != 0){break;}else{temp = (int)(temp/10);}
                        }
                        if(unique == false){break;} // if given number is not unique, breaks the cycle
                }
                if(unique == true){std::cout << n << endl; return 1; } // checks if the number checked was unique (add pause here if you want to test)
                if(n<((q*10)-1)){n++;}else{break;} // checks if 10^(i+1)-1 is reached, if not, then n++;
            }
        }
    return EXIT_SUCCESS;
}

Edited by author 25.09.2011 22:01

Edited by author 25.09.2011 22:01

Edited by author 25.09.2011 22:01