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

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

rt

Edited by author 14.04.2024 21:19

When I tried the brute force algorithm, I TLE at #15


How to solve this problem? Please send the solution to 13588731339@163.com

:V

I tried this approach with Java: Test 5. TL
With C++: Test 9. TL

And seems like this is not enough, however time complexity is O(αk^2 + α|S|*k) where α is hash map hidden constant.

So... did anyone managed to solve it this way?

( window | A    | aisle |B     C| aisle |    D | window )-- Premium   (1-2)
( window | A   B| aisle |C     D| aisle |E   F | window )-- Business  (3-20)
( window | A B C| aisle |D E F G| aisle |H G K | window )-- Economy   (21-64)




Edited by author 30.05.2022 16:38

It took me a while to get this one correct, and it's because I found part of the descritpion to be ambiguous/unclear - so I'm posting this clarification which hopefully will help anyone else who has the same misunderstanding.

"if a student has got satisfactory marks, the scholarship is not given, "

I read this to mean "got ONLY satisfactory marks" but my solutions were rejected.
Once I modified my solution to treat it as "got ANY satisfactory marks", the solution was accepted.

First time I've got WA #4 because of this test case:

Input:
6
1 1 2 1 1 1

Correct answer:
2 1 1 2 3 1

Instead of using getline(cin, str), use two different string such as string s1, s2.
Then compare s1!

When n > 6 the cases are wrong. Try to do it without placing a circle in the center.

How is it POSSIBLE to find 42 test case?
It seems like everything should work fine..

already done. for someone who doesn't know how to do it:

a,b = input().split()
print(int(a)+int(b))
a = int(1)
b = int(5)

Edited by author 28.03.2024 16:23