QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#708821 | #2933. Sequinary Numerals | sefnuray# | WA | 0ms | 3996kb | C++14 | 1.9kb | 2024-11-04 08:06:08 | 2024-11-04 08:06:08 |
Judging History
answer
#include <iostream>
#include <algorithm>
#include <bitset>
#include <vector>
#include <cmath>
#include <string>
#include <set>
#include <map>
#include <unordered_map>
#include <sstream>
#include <iomanip>
#include <stdexcept>
#include <utility>
#include <deque>
using namespace std;
typedef long long ll;
typedef long double ld;
#define MOD 1000007
ll gcd (int a, int b) {
return b ? gcd (b, a % b) : a;
}
void FastDoubling (ll n, ll res[]) {
ll a, b, c, d;
// Base Condition
if (n == 0) {
res[0] = 0;
res[1] = 1;
return;
}
FastDoubling((n / 2), res);
// Here a = F(n)
a = res[0];
// Here b = F(n+1)
b = res[1];
c = 2 * b - a;
if (c < 0)
c += MOD;
// As F(2n) = F(n)[2F(n+1) – F(n)]
// Here c = F(2n)
c = (a * c) % MOD;
// As F(2n + 1) = F(n)^2 + F(n+1)^2
// Here d = F(2n + 1)
d = (a * a + b * b) % MOD;
// Check if N is odd
// or even
if (n % 2 == 0) {
res[0] = c;
res[1] = d;
}
else {
res[0] = d;
res[1] = c + d;
}
}
int main() {
//these first two lines speed up input / output significantly
ios_base::sync_with_stdio(0);
cin.tie(0);
string seq;
cin>>seq;
if(seq.size()!= 0 ) {
int denPow = seq.size()-1;
ll num = 0;
ll den = pow(2, denPow);
for(int i = 0; i<seq.size(); i++) {
int d = (seq[denPow-i]-'0');
num+= d*(pow(3, i))*(pow(2, denPow-i));
}
ll whole = num/den;
num = num%den;
if(num!= 0) {
ll divis = gcd(num, den);
num /= divis;
den /= divis;
cout<<whole<<" "<<num<<"/"<<den;
} else {
cout<<whole;
}
} else {
cout<<"0";
}
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3864kb
input:
2101
output:
10
result:
ok single line: '10'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3748kb
input:
201
output:
5 1/2
result:
ok single line: '5 1/2'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3996kb
input:
2010211122112221202012
output:
16541 873801/1048576
result:
ok single line: '16541 873801/1048576'
Test #4:
score: -100
Wrong Answer
time: 0ms
memory: 3868kb
input:
22222222222222222222222222222222
output:
1725755 -572407425/-1073741824
result:
wrong answer 1st lines differ - expected: '1725755 572407425/1073741824', found: '1725755 -572407425/-1073741824'