QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#66061 | #5103. Fair Division | dani_tro# | WA | 352ms | 3212kb | C++14 | 1.8kb | 2022-12-06 03:24:01 | 2022-12-06 03:24:02 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
long long n, p, q;
double res = 0.0, f, st;
double pow1(double q, int st)
{
if(st == 0)return 1.0;
if(st == 1)return q;
double ans = pow1(q, st / 2) * pow(q, st / 2);
if(st % 2 == 0)ans *= q;
return ans;
}
bool tr(long long p, long long q, long long m)
{
long long p1 = 1, q1 = 1;
double f = p * (1.0 / q);
double tmp = f;
long long res = 0;
for(int i = 0; i < n; i++)
{
p1 *= p;
//if(p1 < p)return false;
if(p1 > m || q1 > m)return false;
}
//if(p == 1 && q == 3)cout << res << endl;
for(int i = 0; i < n; i++)
{
res += p1 * q1;
//cout << p1 << " " << q1 << endl;
p1 /= p;
q1 *= q;
if(p1 > m || q1 > m || res > m || res < p)return false;
if(q1 < q)return false;
}
//m *= q1;
for(int i = 0; i < n - 1; i++)
{
if(res % q == 0)res /= q;
}
//if(p == 1 && q == 2)cout << res << endl;
//double kt = m;
//kt /= res;
//long long ts = round(kt);
//if(p == 1 && q == 2)cout << kt << " " << ts << " " <<setprecision(41) << kt - ts << endl;
//cout << m << " " << res << endl;
if(m % res != 0)return false;
return true;
}
int main()
{
/*int n = 6;
q = 2 * (1.0 / 3);
int m = 91000;
cout << m * ( 2 / (pow(3, n) - (pow(3 - 2, n)))) << endl;
st = 1.0;
for(int i = 0; i < n - 1; i++)st *= (1 - q);
for(int i = 1; i <= 10000; i++)
{
res += 91000 * q * (st);
for(int j = 0; j < n; j++)st *= (1 - q);
}
cout << res << endl;
*/
long long m;
cin >> n >> m;
if(m < n)
{
cout << "impossible\n";
return 0;
}
for(int q = 1; q < 10000; q++)
{
for(int p = q - 1; p > 0; p--)
{
if(tr(p, q, m) == true)
{
cout << q - p << " " << q << endl;
return 0;
}
}
}
cout << "impossible\n";
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 352ms
memory: 3212kb
input:
13 382475111752106101
output:
impossible
result:
wrong answer 1st lines differ - expected: '17 28', found: 'impossible'