For some reason I get TLE with G++ 4.9 and AC with Visual C++ 2013 with exactly the same code. I tried to use scanf/printf instead of cin/cout, but had no difference. On my machine this code works <100ms for every n with G++. Can anyone explain why I get TLE with G++? Thanks!

#include <string>
#include <queue>
#include <iostream>

using namespace std;

int main() {
    int n;
    cin >> n;
    queue<string> result;
    result.push("a");
    result.push("b");
    result.push("c");
    char abc[] = {'a', 'b', 'c'};
    for (int i = 1; i < n; i++) {
        while (true) {
            string &s = result.front();
            if (s.size() > i) {
                break;
            }
            char last = s[s.size() - 1];
            if (s.size() > 1) {
                char lbo = s[s.size() - 2];
                for (int k = 0; k < 3; k++) {
                    char c = abc[k];
                    if (last != c && lbo != c) {
                        result.push(s + c);
                    }
                }
            } else {
                for (int k = 0; k < 3; k++) {
                    char c = abc[k];
                    if (last != c) {
                        result.push(s + c);
                    }
                }
            }
            result.pop();
        }
        if ((i + 1) * result.size() > 100000) {
            cout << "TOO LONG";
            return 0;
        }
    }
    while (!result.empty()) {
        cout << result.front() << endl;
        result.pop();
    }
    return 0;
}

no bitwise shit needed, no storing 17 bits for indexes and no such stuff! just use unsigned stack* [1000] for the stacks (store elements in a dynamic array, reallocating memory for each push), and unsigned  top[1000] for the index of the top element. with this i got AC with 663 KB! good luck!

As stated in the statement, after spraying or aromatizing of fruit it may become to have fractional value.
25th test is the first case where you need to aromatize one flower and dearomatize another in such way that both of them have fractional value, but their sum is integer.

Edited by author 07.11.2009 05:19

Try this test:
100000 99999 0
1 2 1000000
2 3 1000000
...
99999 100000 1000000

Answer: 10049708502000000

Good Luck!

Solution looks like bruteforce with a precalc, not a dynamic programming one. Or precalc counts as DP? Or DP is just a clever bruteforce?

Edited by author 25.07.2017 20:10

I think the dataset for this problem is weak. I got AC without checking for cycles.

Input:
3 3
1 3
3 2
2 1
1 3 2
Correct output:
NO

But my code ( http://ideone.com/ZljGZ5 ) returns YES and it got Accepted.

Edited by author 25.07.2017 14:17

Edited by author 25.07.2017 14:18

И не только мне,  как показывает форум.

Можно решить это с помощью алгоритма Дейкстры.

Моё время на Clang C++14 равно 2.7 сек.
На Visual C++2013 вообще  TLE#8.

Give me some tests. PLEASE.

a=int(input())
tasks_left=12-a
if tasks_left*45<=240:
    print('TRUE')
else:
    print('FALSE')

144
->185
29756
->29929
800000000
->1001578525
41088
->51365
123456
->123457
1369
->0
369
->0
1024
->1285
58
->59
21414
->0
2000000000
->2500015625
961
->0
1870
->1871
23432
->35151

P.S. use long long (else WA7)

http://ideone.com/KOHykO

Examples and my examples work.
ideome works

How to look at all stdin ???

Edited by author 28.07.2017 03:35

?????abxxxab?????
abab
output: 3
answer: 4

I use very simple algo, prompt other algo please.

Edited by author 10.08.2011 15:32

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

int main()
{
    long int n,k,val,fact=1,coeff=0;

    char ch[24],*num,*excl;

    gets(ch);

    num=strtok(ch," ");
    n=atoi(num);

    excl=strtok(NULL,NULL);
    k=strlen(excl);

    while(coeff*k<n)
    {
        val=n-coeff*k;
        fact=fact*val;
        coeff++;
    }


    if(n%k!=0)
        fact=fact*(n%k);
    else fact=fact*k;

    printf("%ld",fact);

    return 0;
}


Hi! I am getting runtime error(access violation) although the solution seems to work for different set of inputs. Please help me out!

Если вы используете DFS в итеративной форме,  то вы можете получить TLE#4.

Если вы перепишите DFS в рекурсивную форму и будете компилировать на Visual C++,  то получите AC за менее чем 0.1 секунды.

It may take around ten minutes if you precalc in Python.

It takes just few moments to precalc in C++.

Maybe special Python libraries for calculations would be OK.

Don't forget about case n=1
answer:
a
b
c

10 6
8
2 1
2 2
4 5
5 2
5 4
6 5
9 4
10 5

Ansver: 1366

Задача заставила подумать.
Как уже описано на форуме,  нужно научиться считать количество единиц, которые встречаются в числах от 1 до X и подбирать X бинарным поиском.

И вот мне этот подсчет долго не давался.

Итог такой.

Считать можно рекурсивно.
Для этого нужно воспользоваться тем,  что для чисел вида X=999...999 искомое количество единиц равно (log10(X)+1) *10^log10(X).
Этот факт я заметил эксперимнтально.

То есть я имею в виду
count_ones (99)=20
count_ones (999)=300
count_ones (9999)=4000
и так далее.

Отсюда и вытекает способ .

Вычисляем сначала для X с зануленными разрядами кроме самого главного,  затем прибавляем значение функции от X с зануленным главным разрядом .

Я приведу пример для небольшого числа.

Пусть X=666.

Тогда посчитаем отдельно для 0-99, умножим на 6,  прибавим к ответу; затем отдельно для 100-200, прибавим это к ответу , затем рекурсивно для 600-666 то есть просто для 0-66.