Test 6 is <tram,> or <trolleybus,>. (whitout <>) ;-)

Edited by author 28.02.2014 17:38

Ha-Ha! My solution works sometimes too 0.001, but how many iterations of your cycle on N=500?

Jokes on you! My solution is O(-∞)

Oh, I have understood. The array isn't the needed collection for this task. Stack is better.

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

int main() {
stack<double> a;
double b;
int c=0;
while(cin)
{cin >> b;
a.push(b);
c++;}
c-=1;
a.pop();
for(int i=0; i<c; i++)
{cout << fixed;
cout.precision(4);
cout << sqrt(a.top()) << endl;
a.pop();}
return 0;
}

Edited by author 10.06.2021 03:35

It's 2021 now, so... have you found out the problem? :)

I already stuck with my solutions at least 5 times, it's ok, I need fresh ideas :)

One of my first ideas was with segment tree and LCM.
1) We calculate order for every element.
2) It is easy to combine 2 segments. order(combined) = LCM(order(segment1), order(segment2))
3) But it hard to do multiplication.

If we multiply by m, we cannot just do order=LCM(order(m), order(segment)). Counterexample:
p=17
segment=[2] order(segment)=8
m=2
after multiplication
segment=[4] order(segment)=4
4 != LCM(order(2), order(segment)) = 8

I am trying to find a way how to express segment of any length in a short way (lets call it segment_data), so it has next properties:
1) I can calculate order quickly
2) I can create multiplication procedure over segment_data
3) Multiplication over segment_data leads to the same order as multiplication over raw segment
4) I can combine 2 segment_data into 1 (so I can build segment tree)

If segment_data is just order of a segment, I cannot make it work (example above). Property 3 is not working.

My last idea was to use segment_data = array of 2 elements (I understand I was not very clear in first post, it is confusing even for me). I found next: there are group of segments, that behaves exactly the same for our task.
I mean, if:
     for any i in (1..p-1): order(i * segment1) = order(i * segment2)
Then we can replace segment1 with segment2, and nothing changes for our task.
I generated groups of such segments for different p.
Example:
p=17

[6,7,10,12] can be replaced with [3,6]
after multiplication by 1..p-1, they lead to the same picture of orders:
[16 16 8 16 8 8 8 16 16 8 8 8 16 8 16 16]

[6,7,10,11] can be replaced with [6,7], picture
[16 16 4 16 4 8 8 16 16 8 8 4 16 4 16 16]

When I was investigating behavior of similar segments, I noticed segment of any length can be replaced with segment of length 2. And it will have the same properties. The plan was to have 2 numbers as nodes of segment tree. But I stuck with combining procedure.

Edited by author 29.05.2021 18:42

Why this solution is wrong?


#include <iostream>
using namespace std;

int main()
{
int herry;
int larry;
int all;
cin >> herry;
cin >> larry;
all=herry+larry-1;
herry=all-larry;
larry=all-herry;
cout << herry << " " << larry;
return 0;
}

Edited by author 03.07.2013 01:45