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

#include<stdio.h>
int main()
{
int i,n,sum;
scanf("%d",&n);
if(n>0)
{
for (i=1;i<=n;i++)
{ sum=sum+i; }
printf("%d",sum);
}
if(n<0)
{
for (i=n;i<=1;i++)
{
sum=sum+i;}
printf("%d",sum);}
else if(n==0){ printf("not applicable");}
}

If you are getting an error on test 5 then use double instead of float.
Если у вас ошибка при 5ом тесте, используйте переменные double вместо float.

2
ABCGRS
ACBGYV
2

i kinda changed the variables
a = the first sum suggested by petr
b = the ---------------------- taxi driver
c = amount added by petr everytime
d = ---------------- taxi driver
we can say that at step n of bargaining:
petr -> a + n*c
taxi -> b - n*d

where looking for a time when petr's suggestion is less than the drivers
which means a + nc <= c - n*d
but there sometime when petr suggest more than what the driver suggest the previous time.
that's why i am comparing between the last petr's suggestion and the previous one of the driver a+c*n > b-d*(n-1). in this case petr says ok to the taxi driver and do not suggest more than that.


void solve() {
    int a, c, b, d;
    cin >> a >> c >> b >> d;
    if (a >= b) {
        cout << a;
        return;
    }
    int n = (b-a)/(c+d);
    if ((b-1)%(c+d)!=0) n++;
    if (a+c*n > b-d*(n-1)) {
        cout << b - d*(n-1) << ln;
    }
    else {
        cout << a + n*c << ln;
    }
}


Edited by author 10.09.2022 21:11

Any hints about test 7?