There is only one eligible lowered numbered ball at any round. Keeping track of this should result in O(n) solution

Write down the sequence, on paper, by hand.
Now, right down the index of each digit on the sequence.
Do you know prefix sums and binary search? It's kinda useful for many problems btw...

Edited by author 15.05.2024 05:54

I solved 1009 and 1012. Now im using new algorithm (log(n)) and program works fast and correct with my tests.

Can you give more tests?

if the cube is at e2, neighbors are:
e1 (near), e3 (far), d2 (left) and f2 (right)

for your convenience
24 orientations of cube:
1 2 3 4 5 6
1 2 4 5 6 3
1 2 5 6 3 4
1 2 6 3 4 5
2 1 3 6 5 4
2 1 4 3 6 5
2 1 5 4 3 6
2 1 6 5 4 3
3 5 1 6 2 4
3 5 2 4 1 6
3 5 4 1 6 2
3 5 6 2 4 1
4 6 1 3 2 5
4 6 2 5 1 3
4 6 3 2 5 1
4 6 5 1 3 2
5 3 1 4 2 6
5 3 2 6 1 4
5 3 4 2 6 1
5 3 6 1 4 2
6 4 1 5 2 3
6 4 2 3 1 5
6 4 3 1 5 2
6 4 5 2 3 1

test:
4
1 4 2 3 6 5
1 4 3 6 5 2
1 4 5 2 3 6
1 4 6 5 2 3
ans:
1
1 2 3 4

:)

For WA12 try this:
9126492316491641269352615215701236589213658621356281376589216562319562396592381659862195621281E-190
100
#

Output must be:
0.0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000009126

What is test #2?

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

/* 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

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...

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

Edited by author 14.04.2024 21:19

Can Anyone be kind enough to explain this ques to me? I'll be grateful to you..

:V