Edited by author 09.05.2025 09:16

It was due to overflow. I changed a few variables to long long and it got accepted.

Edited by author 25.08.2015 13:20

Edited by author 25.08.2015 13:20

 "Nikolay thinks an integer is interesting if it is a prime number. However, Asya thinks an integer is interesting if the amount of its positive divisors is a prime number "
If it so, "Nikolay and Asya are happy when their tastes about some integer are common."
How come it can be true,  prime number is a number which does not have divisors except for 1 and itself, but it says ,in Asya sentence, that  "amount of its positive divisors is a prime number ",Does it mean 1 and the number given ?  Can somebody explain it to me and the sample given below the problem , please

The problem can be reduced to a matching problem.
It can be solved by Dinic's algorithm.

what in test #5?

what about ternary search in this task?



Edited by author 01.10.2020 22:01

please consider very small cases

First i tried to solve this problem using int64 (long long) , i got WA6. Then i used long number theory to solve this problem and i got AC!)

Good luck!

Problem can be reduced to edges in complete graph:
Given no. of edges, what is the max no. of vertices in a complete graph?

del

Edited by author 20.02.2024 17:47

Я просто накидал кучу каких-то непонятных оптимизаций, и оно почему-то зашло

//please tell me what's wrong, cause i cant understand...

#include <bits/stdc++.h>
#include<fstream>
#define all(a) (a).begin(), (a).end()
#define ll long long
#define sz size
#define dbl double
#define vll vector <ll>
#define INF LLONG_MAX
#define uniq(x) x.resize(unique(begin(x),end(x))-begin(x))
#define forik(i,m,n) for(ll i=m;i<n;++i)
#define re return

using namespace std;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie();
    vll numbers;
    ll num;
    while (cin >> num) {
        numbers.push_back(num);
    }
    for (ll i = numbers.size() - 1; i >= 0; i--) {
        dbl nek = sqrt(numbers[i]);
        cout << fixed << setprecision(4) << nek << endl;
    }
    re 0;
}

#include <iostream>
#include <stack>
#include <cmath>
using namespace std;

int main()
{
    stack<double> root;
    double input;

    while(cin >> input)
    {
        root.push(sqrt(input));
    }

    while(!root.empty())
    {
        cout << root.top() << endl;
        root.pop();
    }

    return 0;
}

435 981 301 -384 -1 345 0

Correct answer:
371.78
789.08

My solution produces an automaton with 2n^2 + n states, but what is the smallest possible size? Is it still ~n^2?

Edited by author 14.02.2024 16:19

worked at least two months....

Bruteforce all short numbers (i. e. length <= 3) and feed them to both input and output automata, then compare. Here are some useful tests:

1
1
1
1 1 1 1 1 1 1 1 1 1

1
3
0 1 0
1 3 3 3 3 3 3 3 3 2
3 3 3 3 3 3 3 3 3 3
3 3 3 3 3 3 3 3 3 3

8
3
0 1 0
1 3 2 3 3 3 3 3 3 3
3 3 3 3 3 3 3 3 3 3
3 3 3 3 3 3 3 3 3 3

These tests didn't help me figure out the issue, but maybe they can be useful for community

7
0 0
0 2
1 1
1 3
3 1
0 -1
-1 0
3.95284707521047407042

6
0 1
1 2
0 2
-1 1
-1 0
1 0
2.82842712474619029095

7
2 0
2 3
-2 3
-2 0
-2 -2
0 -2
2 -2
6.40312423743284853117

3
0 0
1 0
0 1
1.41421356237309514547

8
1 2
1 3
2 2
2 1
1 0
1 1
0 1
0 2
3.00000000000000000000

12
2 0
1 1
0 1
1 0
0 -2
-1 1
-1 2
0 2
-1 3
-4 0
0 -4
0 -1
6.79869268479037932229

12
2 0
1 1
0 1
1 0
-2 0
-1 1
-1 2
0 2
-1 3
-4 0
-3 -1
0 -1
6.00000000000000000000

7
0 0
1 2
1 1
3 1
1 -1
1 -3
-1 0
5.00000000000000000000

16
3 0
4 1
3 1
3 2
2 2
2 1
1 1
1 2
0 2
0 1
-1 1
-1 2
-2 2
-2 1
-3 1
-2 0
7.00000000000000000000

1. Use scanf/printf instead of cin/cout
2. Use make_heap, push_heap and pop_heap instead of priority_queue
3. Use C-style array instead of vector
4. Do not allocate n elements for an array