QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#116042#4771. Bird treemomoyuu#AC ✓4ms3468kbC++171.5kb2023-06-28 01:26:482023-06-28 01:26:51

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-06-28 01:26:51]
  • 评测
  • 测评结果:AC
  • 用时:4ms
  • 内存:3468kb
  • [2023-06-28 01:26:48]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
using ll = long long;


ll gcd(ll a,ll b){
    if(b) return gcd(b,a%b);
    else return a;
}
void solve(){
    string s;
    cin>>s;
    ll a = 0,b = 0;
    int n = s.size();
    int ni = 0;
    while(s[ni]!='/'){
        a *= 10;
        a += s[ni] - '0';
        ni++;
    }
    for(int i = ni + 1;i<n;i++){
        b *= 10;
        b += s[i] - '0';
    }
    ll na = 1,nb = 1;
    ll now = 0;
    string ans = "";
    ll la = 0;
    ll lb = 1;
    ll ra = 1;
    ll rb = 0;
    while(na!=a||nb!=b){
        //cout<<na<<" "<<nb<<endl;
        int cnt = 0;
        if(nb*a>b*na){
            if(now%2==1) cnt = 0;
            else cnt = 1;
        }else{
            if(now%2==0) cnt = 0;
            else cnt = 1;
        }
        if(cnt==0) ans += "L";
        else ans += "R";
        if(now%2==1) cnt ^= 1;
        now++;

        if(cnt==0) {
            ll bb = nb + lb;
            ll aa = na + la;
            ra = na;
            rb = nb;
            na = aa / gcd(aa,bb);
            nb = bb / gcd(aa,bb);
            //ans += "L";
        }else{
            ll bb = nb + rb;
            ll aa = na + ra;
            la = na;
            lb = nb;
            na = aa / gcd(aa,bb);
            nb = bb / gcd(aa,bb);
           // ans +="R";
        }
    }
    cout<<ans<<endl;

}

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int t;
    cin>>t;
    while(t--){
        solve();
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3404kb

input:

3
1/2
2/5
7/3

output:

L
LRR
RLLR

result:

ok 3 lines

Test #2:

score: 0
Accepted
time: 4ms
memory: 3468kb

input:

96
1/2
1/3
1/4
1/5
1/6
1/7
1/8
2/1
2/3
2/5
2/7
3/1
3/2
3/4
3/5
3/7
3/8
4/1
4/3
4/5
4/7
5/1
5/2
5/3
5/4
5/6
5/7
5/8
6/1
6/5
6/7
7/1
7/2
7/3
7/4
7/5
7/6
7/8
8/1
8/3
8/5
8/7
10000/9999
9999/10000
1/10000
10000/1
1000000000/300001
300001/1000000000
701408733/433494437
433494437/701408733
380211999/53852...

output:

L
LR
LRL
LRLR
LRLRL
LRLRLR
LRLRLRL
R
LL
LRR
LRLL
RL
RR
LLR
LLL
LRRL
LRRR
RLR
RRL
LLRL
LLLR
RLRL
RLL
RRR
RRLR
LLRLR
LLRR
LLLL
RLRLR
RRLRL
LLRLRL
RLRLRL
RLRR
RLLR
RRRL
RRLL
RRLRLR
LLRLRLR
RLRLRLR
RLLL
RRRR
RRLRLRL
RRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLR...

result:

ok 96 lines