Memory: 0,942 KB, Time: 0.125
http://acm.timus.ru/status.aspx?author=96814

Please add the following testcase:

869637034218881024 = 2^18 * 1806487 * 1836383

The answer should be "Yes". My solution prints "No" and nevertheless has AC.

For WA12 try this:
9126492316491641269352615215701236589213658621356281376589216562319562396592381659862195621281E-190
100
#

Output must be:
0.0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000009126

What is test #2?

3 times! what the reason?
vc++ 0.328 sec
g++ 1.078 sec

upd.
in 3 problems vs is really faster than g++ (2-3 times). Compiler problem?

Edited by author 28.10.2014 17:39

Edited by author 28.10.2014 17:39

The test contents points entered clockwise, which doesn't respond the condition.
I succeed passing the test only after applied an algo, which is not sesitive to the order of points in polygone

Edited by author 29.04.2024 19:57

Edited by author 29.04.2024 19:57

I want to solve the problem using a dynamic array. But the compiler outputs this: HEAP CORRUPTION DETECTED: after Normal block (#150) at 0x000001EEFBCDB420.
CRT detected that the application wronte to memory after end of heap buffer.

#include <iostream>
#include <cmath>
#include <iomanip>
using namespace std;
void main()
{
    int size = 0, i = 0;
        int* a = new int[size];
    unsigned int x;
    while (cin >> x)
    {
        size += 1;
        for (; i < size;++i)
        {
            a[i] = x;

        }

    }

    for (int i = size-1; i >= 0; --i)
    {
        cout << fixed << setprecision(4) << sqrt(a[i]) << endl;
    }
    delete[] a;

Edited by author 20.03.2023 12:40

When need stop the flow. Help me pls!

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

int main() {

    double number;
    vector<double> numbers;

    while (cin >> number)
        numbers.push_back(number);

    cout.precision(4);
    cout.setf(std::ios::fixed);

    for (auto iter = numbers.rbegin(); iter != numbers.rend(); ++iter)
        cout << sqrt(*iter) << endl;

    return 0;
}

/* https://acm.timus.ru/problem.aspx?space=1&num=1001 */
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
/* #include <sys/queue.h> */
/*
 * Singly-linked List definitions.
 */
#define    SLIST_HEAD(name, type)                        \
struct name {                                \
    struct type *slh_first;    /* first element */            \
}

#define    SLIST_HEAD_INITIALIZER(head)                    \
    { NULL }

#define    SLIST_ENTRY(type)                        \
struct {                                \
    struct type *sle_next;    /* next element */            \
}

/*
 * Singly-linked List functions.
 */
#define    SLIST_INIT(head) do {                        \
    (head)->slh_first = NULL;                    \
} while (/*CONSTCOND*/0)

#define    SLIST_INSERT_AFTER(slistelm, elm, field) do {            \
    (elm)->field.sle_next = (slistelm)->field.sle_next;        \
    (slistelm)->field.sle_next = (elm);                \
} while (/*CONSTCOND*/0)

#define    SLIST_INSERT_HEAD(head, elm, field) do {            \
    (elm)->field.sle_next = (head)->slh_first;            \
    (head)->slh_first = (elm);                    \
} while (/*CONSTCOND*/0)

#define    SLIST_REMOVE_HEAD(head, field) do {                \
    (head)->slh_first = (head)->slh_first->field.sle_next;        \
} while (/*CONSTCOND*/0)

#define    SLIST_REMOVE(head, elm, type, field) do {            \
    if ((head)->slh_first == (elm)) {                \
        SLIST_REMOVE_HEAD((head), field);            \
    }                                \
    else {                                \
        struct type *curelm = (head)->slh_first;        \
        while(curelm->field.sle_next != (elm))            \
            curelm = curelm->field.sle_next;        \
        curelm->field.sle_next =                \
            curelm->field.sle_next->field.sle_next;        \
    }                                \
} while (/*CONSTCOND*/0)

#define    SLIST_FOREACH(var, head, field)                    \
    for((var) = (head)->slh_first; (var); (var) = (var)->field.sle_next)

/*
 * Singly-linked List access methods.
 */
#define    SLIST_EMPTY(head)    ((head)->slh_first == NULL)
#define    SLIST_FIRST(head)    ((head)->slh_first)
#define    SLIST_NEXT(elm, field)    ((elm)->field.sle_next)

struct num_entry {
    double num;
    SLIST_ENTRY(num_entry) entries;
};
SLIST_HEAD(tq_num, num_entry);

#define my_abs(x) ((x)>0?(x):-(x))

double my_sqrt(double c) {
    double err = 1e-15;
    double t = c;
    if (c < 0) {
        return -1;
    }
    while (my_abs(t- c/t) > err * t) {
        t = (c/t + t) / 2.0;
    }
    return t;
}

int main() {
    struct tq_num head;
    struct num_entry *np;
    unsigned long long m;

    SLIST_INIT(&head);
    /* https://acm.timus.ru/help.aspx?topic=cpp */
    while (scanf("%llu ", &m) != EOF) {
#ifndef ONLINE_JUDGE
        printf("m=%llu\n", m);
#endif
        np = (struct num_entry *)malloc(sizeof(struct num_entry));
        np->num = (double)m;
        SLIST_INSERT_HEAD(&head, np, entries);
    }
    while (!SLIST_EMPTY(&head)) {
        np = SLIST_FIRST(&head);
        printf("%.4f\n", my_sqrt(np->num));
        SLIST_REMOVE(&head, np, num_entry, entries);
        free(np);
    }
    return 0;
}

Edited by author 28.04.2024 12:11

1) in Graham scan, sort points by polar angle, for equal polar angles - by distance from p0
2) second part of the problem is similar to problem 1020

After cracking my brain for 2 weeks in the search of the polynominal solution, I decided to use my observations to code the most optimized random algorithm I could think of.

Surprisingly, I didn't even have to use simulated annealing: hill climb was enough. I also have 2 optimizations that I planned to implement but didn't have enough time.

I was expecting very strong tests considering all the dramatic comments from coders way better than me.

Maybe it's only a matter of time before admins add new tests that crack my solution, but I can't think of a single test that is strong enough to survive all optimizations...

I'm extremely curious about the polynominal solution, so maybe I will continue thinking about this problem... But it's so incredibly hard...

a, b = map(int, input().split())
print(10-a, 10-b)

Finally I've solved this problem using very hard optimised Main & Lorentz's algo, and 0.405s only.

But I noticed many people solved this problem very fast and using much less memory.
What algo do you use? I doubt it's possible to speed-up Main & Lorentz or Crochemore algos so much.

Is it some alternative (like suffix tree) solution, or just some strong idea can be applied to this particular problem? Is it possible to solve it in O(n)?

So clearly realising (if monkey will follow others then monkey never will create that word because of re-using letters)?

4
1 0
3 0
3 2
1 2
3 1
0
Answers:
2.00000000

4
1 0
3 0
3 2
1 2
3 1
1
45
Answers:
2.00000000
2.00000000

4
1 0
3 0
3 2
1 2
3 1
2
45
-90
Answers:
2.00000000
2.00000000
0.50000000

4
1 0
3 0
3 2
1 2
3 1
2
-45
-45
Answers:
2.00000000
0.50000000
0.00000000

3
-2.000 1.000
1.000 -2.000
4.000 1.000
1.000 1.000
1
359
Answers:
9.00000000
0.00000000