QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#629082#2933. Sequinary NumeralsTenshi#WA 0ms3604kbC++201.6kb2024-10-11 03:14:152024-10-11 03:14:16

Judging History

你现在查看的是最新测评结果

  • [2024-10-11 03:14:16]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3604kb
  • [2024-10-11 03:14:15]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
 
#define debug(x) cerr << #x << ": " << (x) << endl
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define dwn(i,a,b) for(int i=(a);i>=(b);i--)
#define pb push_back
#define all(x) (x).begin(), (x).end()
 
#define x first
#define y second
// #define int __int128
#define int long long
using pii = pair<int, int>;
 
inline void read(int &x){
    int s=0; x=1;
    char ch=getchar();
    while(ch<'0' || ch>'9') {if(ch=='-')x=-1;ch=getchar();}
    while(ch>='0' && ch<='9') s=(s<<3)+(s<<1)+ch-'0',ch=getchar();
    x*=s;
}

struct Node{
	int a;
	pii b;
};

Node res;

pii f(int a, int b){
	int g=__gcd(a, b);
	return {a/g, b/g};
}

pii add(pii a, pii b){
	int lw=a.y*b.y;
	int hi=a.x*b.y+a.y*b.x;
	return f(hi, lw);
}

Node add(Node x, Node y){
	int a=x.a+y.a;
	pii b=add(x.b, y.b);
	a+=b.x/b.y;
	b.x%=b.y;
	return {a, b};
}

pii mul(int x, pii y){
	int a=x*y.x;
	int b=y.y;
	return f(a, b);
}

pii mul(pii x, pii y){
	int a=x.x*y.x;
	int b=x.y*y.y;
	return f(a, b);
}

Node mul(Node x, Node y){
	int a=x.a*y.a;
	pii b={0, 1};
	auto t=mul(x.a, y.b);
	// debug(t.y);
	b=add(b, mul(x.a, y.b));
	// debug(b.x), debug(b.y);
	b=add(b, mul(y.a, x.b));
	b=add(b, mul(x.b, y.b));
	a+=b.x/b.y;
	b.x%=b.y;

	return {a, b};
}

void print(Node x){
	cout<<x.a;
	if(x.b.x) cout<<" "<<x.b.x<<"/"<<x.b.y;
}

signed main(){
	string s; cin>>s;
	reverse(all(s));
	int n=s.size();
	const Node M={{1}, {1, 2}};
	Node B={1, {0, 1}};
	res={0, {0, 1}};
	rep(i, 0, n-1){
		Node val={s[i]-'0', {0, 1}};
		res=add(res, mul(B, val));
		
		B=mul(B, M);
	}
	print(res);
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3604kb

input:

2101

output:

10

result:

ok single line: '10'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3568kb

input:

201

output:

5 1/2

result:

ok single line: '5 1/2'

Test #3:

score: 0
Accepted
time: 0ms
memory: 3604kb

input:

2010211122112221202012

output:

16541 873801/1048576

result:

ok single line: '16541 873801/1048576'

Test #4:

score: -100
Wrong Answer
time: 0ms
memory: 3596kb

input:

22222222222222222222222222222222

output:

416444 501334399/-1073741824

result:

wrong answer 1st lines differ - expected: '1725755 572407425/1073741824', found: '416444 501334399/-1073741824'