2 1
3 1
4 3
5 1
6 4
7 2
8 6
9 8
10 7
ans: 8 or 1

The problem is very simple.
It is clear from the first glance what is going on.
The coding is trivial.
The math part is trivial.

And... for some reason it is almost impossible to get AC from the first try.

Можно просто перебирать ответ наименьшего возможного,  двойки,  пока не найдем нужное значение.

Для данного количества жителей можно за log этого количества по времени найти требуемое количество кондукторов.

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <cctype>
#include <algorithm>
#include <math.h>
#include <iostream>

using namespace std;

int main() {
int N, ch;
int h = 1;
int max = 0;
int second_max = 0;
cin >> N;
vector <int> m(N);
vector<int> v(N);
vector<int> k;
for (int i = 0; i < N; i++)
{
    cin >> ch;
    v[i] = ch;
}
for(int i = 1; i < N; i++)
{
    if(v[i] > max)
    {
        second_max = max;
        max = v[i];
    }
    else
    {
        if (v[i] > second_max)
        {
            second_max = v[i];
        }
    }
}
for (int i = 0; i < N; i++)
{
    if (v[i] != max && v[i] != second_max && v[i] != v[0])
    {
        k.push_back(v[i]);
    }
}
sort(begin(k), end(k));
m[0] = v[0];
m[1] = second_max;
m[N - 1] = max;
for (int i = 2; i < N-1; i++)
{
    m[i] = k[k.size() - h];
    h++;
}
for (auto j = 0; j < N; j++)
{
    for (auto i = 0; i < N; i++)
    {
        if(m[j] == v[i])
        {
            cout << i + 1 << " ";
            i = N;
        }
    }
}
    return 0;
}

Можно сдать тернарным поиском на Python 3.4 с параметрами :
 количество итераций -- 100
 максимальное А и максимальное B -- 10**18

My AC program had TL when we have this test (with a log of garbage, but still acceptable by task conditions)

131 393
struct used
.int
.int
struct aa
.int
.int
struct ab
.aa
.aa
struct ac
.ab
.ab
// many lines......
struct ew
.ev
.ev
struct ex
.ew
.ew
struct ey
.ex
.ex
struct ez
.ey
.ey
000000010000000200000003

Can you add this? Link to full test - https://gist.github.com/Izaron/1a4fd5894f45fafc2d6d46f0f8d81ce3

I solved this problem( 0.015 sec) but My algo is heuristic.
Why this problem is geometric? Or how can we use geometry in this task to reduce the search?

Insert this magic line before the code

#pragma comment(linker, "/STACK:36777216")

And it works!

#include <iostream>
#include <iomanip>
using namespace std;
int main()
{
    setlocale(LC_ALL,"Russian");
    int a,b;

    cin>>a>>b;
    a=a+b;
    cout<<"a+b="<<a<<endl;

    return 0;
}

I had WA25 when used char[20002];
After changed to char[30002] got AC.

I was so upset that I wa on #7 more than 10. I want to practice my suffix array,so I used it and used RMQ,But I wa on #7.
I very want to know what is #7.
Can the admin give the simple to me? thanks a lot
http://paste.ubuntu.com/23169621/
the suffix array algorithm is right cause I got AC ever using this Template~~

Приятно было прикоснуться к наследию легендарного человека

Я знаю,  что здесь еще есть от него задача Currency Exchange

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.