ამოხსნების სტატუსი

ამ გვერდზე თქვენ იხილავთ გაგზავნილი ამოხსნების სტატუსს.


გაგზავნის თარიღი: 14.08.2020 11:48:49

ამოცანა: ჯაჭვი

მომხმარებელი: gamzaza

ვერდიქტი: სრული ამოხსნა

შეფასება: 100.0 ქულა







#include <bits/stdc++.h>

using namespace std;

//სტრინგების როგორც რიცხვების შეკრება, გამოკლება, გამრავლების ოპერაციები
int sum(int a, int b, int& carry);
int sub(int a, int b, int& rem);
int mult(int a, int b, int& carry);
string add(string a, string b);
string multiply(string a, char b);
string subtract(string a, string b);

int main(){
    //freopen("pil.I13","r",stdin);
   // freopen("pil.O13","w",stdout);
    int n;
    cin >> n;
    string steps[n];
    steps[0] = "1";
    stack<int> s;
    //ყოველ ინდექსზე მყოფი რიცხვის შეცვლა რამდენ მოქმედებაში მოხერხდება თუ მის წინ სულ 0ები წერია და
    // შეცვლის შემდეგ ისევ 0ები ეწერება
    for(int i = 1; i < n; i++){
        string cur = multiply(steps[i-1], '2');
        steps[i] = add(cur, "1");
    }
    int cur;
    //სტეკში ვყრით მხოლოდ ერთიანის ინდექსებს
    for(int i = 0; i < n; i++){
        cin >> cur;
        if(cur) s.push(i);
    }
    if(s.empty()){
        cout << 0 << endl;
        return 0;
    }
    string res = steps[s.top()];
    s.pop();
    int k = 0;
    while(!s.empty()){
        cur = s.top();
        s.pop();
        if(k == 1){
            res = add(res, steps[cur]);
            k = 0;
        }else{
            res = subtract(res, steps[cur]);
            k = 1;
        }
    }
    cout << res << endl;
    return 0;
}


//სტრინგის კონკრეტულ ინდექსებზე მყოფი რიცხვების შეკრება, რასაც ასევე ემატება წინა შეკრებიდან
//გადმოსული carry რაც ან 1-ია ან 0. ამ შეკრების შემდეგ carry-ის ისევ ვცვლით.
int sum(int a, int b, int &carry){
    int result = a + b + carry;
    if (result >= 10) {
        result -= 10;
        carry = 1;
    } else {
        carry = 0;
    }
    return result;
}
//სტრინგის კონკრეტულ ინდექსებზე მყოფი რიცხვების გამრავლება, რასაც ასევე ემატება წინა ნამრავლიდან
//გადმოსული carry. ამ შეკრების შემდეგ carry-ის ისევ ვცვლით ნამრავლის 10ზე გაყოფით.
int mult(int a, int b, int& carry){
    int res = a * b + carry;
    carry = res / 10;
    res = res % 10;
    return res;
}
//სტრინგის კონკრეტულ ინდექსებზე მყოფი რიცხვების გამოკლება, რასაც ასევე აკლდება წინა სხვაობიდან
//გადმოსული rem. ამ შეკრების შემდეგ rem-ის ისევ ვცვლით.
int sub(int a, int b, int& rem){
    int res = a - b - rem;
    if(res < 0){
        res = 10 + res;
        rem = 1;
    }else rem = 0;
    return res;
}
//სტრინგების როგორც რიცხვების შეკრება
string add(string a, string b){
    int s = 0;
    int carry = 0;

    if (b.length() > a.length() ||
        (b.length() == a.length() && b[0] - '0' > a[0] - '0')) {
        swap(a, b);
    }

    string res = "";
    int i = a.length() - 1;
    int j = b.length() - 1;
    while (i >= 0) {
        if (j < 0) {
            s = sum(a[i] - '0', 0, carry);
        }else {
            s = sum(a[i] - '0', b[j] - '0', carry);
            j--;
        }
        i--;
        res = (char)(s + '0') + res;
    }
    if (carry){
        res = '1' + res;
    }
    return res;
}
//სტრინგის ერთნიშნა რიცხვზე გამრავლება
string multiply(string a, char b){
    int s = 0;
    int carry = 0;
    string res = "";
    int i = a.length() - 1;
    while (i >= 0) {
        s = mult(a[i] - '0', b - '0', carry);
        i--;
        res = (char)(s + '0') + res;
    }
    if(carry){
        res = (char)(carry + '0') + res;
    }
    return res;
}

//სტრინგების როგორც რიცხვების გამოკლება
string subtract(string a, string b){
    int dif = 0;
    int rem = 0;
    string res = "";
    int i = a.length() - 1;
    int j = b.length() - 1;
    while(i >= 0){
        if(j >= 0){
            dif = sub(a[i] - '0', b[j] - '0', rem);
            j--;
        }else{
            dif = sub(a[i] - '0', 0, rem);
        }
        i--;
        res = (char)(dif + '0') + res;
    }
    int startIndx = 0;
    for(; startIndx < res.length()-1; startIndx++){
        if(res[startIndx] != '0') break;
    }
    return res.substr(startIndx); //თუ პასუხი იქნება 00004 დავაბრუნებთ 4-ს
}

ტესტები

შემავალი მონაცემები
4
1 0 1 0
გამომავალი მონაცემები
6
თქვენი პასუხი
6
ჩეკერის პასუხი
YES
შემავალი მონაცემები
4
1 0 1 0
გამომავალი მონაცემები
6
თქვენი პასუხი
6
ჩეკერის პასუხი
YES
შემავალი მონაცემები
1
1
გამომავალი მონაცემები
1
თქვენი პასუხი
1
ჩეკერის პასუხი
YES
შემავალი მონაცემები
500
0 1 0 0 1 0 0 0 1 1 1 1 1 0 1 1 0 0 1 1 1 1 1 0 1 1 1 0 0 1 0 0 1 1 0 0 1 1 1 0 1 0 0 0 1 0 0 0 0 1 0 0 1 0 1 0 0 0 1 1 0 0 0 1 1 0 1 0 1 1 1 1 1 0 1 1 0 0 1 0 1 0 1 1 0 0 1 1 0 0 1 0 0 1 1 1 0 0 0 1 1 1 0 1 1 1 0 0 1 1 1 0 1 0 1 1 0 1 1 1 1 0 0 1 1 1...
გამომავალი მონაცემები
2847262540876021597807142803116845209440741719297654597607548150317054727279401701134982912658881475084036118676027203634468650009314763847077348207132
თქვენი პასუხი
2847262540876021597807142803116845209440741719297654597607548150317054727279401701134982912658881475084036118676027203634468650009314763847077348207132
ჩეკერის პასუხი
YES
შემავალი მონაცემები
1000
0 1 1 0 0 1 0 0 0 0 0 0 1 1 0 1 0 1 1 1 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 1 0 0 1 0 0 0 0 0 0 0 1 0 1 0 1 0 0 1 0 1 1 0 0 1 1 0 1 0 0 1 1 1 1 1 0 1 0 0 1 0 1 1 1 1 0 0 1 1 1 0 0 1 0 1 0 1 0 1 0 0 0 0 0 0 1 0 1 1 1 1 1 0 0 1 1 1 0 1 0 1 0 0 1 ...
გამომავალი მონაცემები
3110334155101303991964029558801988361408331053174950468527870081767224384966023532898651092873799853663045879130952109659726734854035669979922255837591183498988774019669947655237823262708147090322672958185538488455194947300862158053951375728763530303406390...
თქვენი პასუხი
3110334155101303991964029558801988361408331053174950468527870081767224384966023532898651092873799853663045879130952109659726734854035669979922255837591183498988774019669947655237823262708147090322672958185538488455194947300862158053951375728763530303406390...
ჩეკერის პასუხი
YES
შემავალი მონაცემები
1000
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
გამომავალი მონაცემები
1071508607186267320948425049060001810561404811705533607443750388370351051124936122493198378815695858127594672917553146825187145285692314043598457757469857480393456777482423098542107460506237114187795418215304647498358194126739876755916554394607706291457119...
თქვენი პასუხი
1071508607186267320948425049060001810561404811705533607443750388370351051124936122493198378815695858127594672917553146825187145285692314043598457757469857480393456777482423098542107460506237114187795418215304647498358194126739876755916554394607706291457119...
ჩეკერის პასუხი
YES
შემავალი მონაცემები
3
0 0 0
გამომავალი მონაცემები
0
თქვენი პასუხი
0
ჩეკერის პასუხი
YES
შემავალი მონაცემები
9
1 1 1 0 1 0 1 0 1
გამომავალი მონაცემები
410
თქვენი პასუხი
410
ჩეკერის პასუხი
YES
შემავალი მონაცემები
25
1 1 1 0 1 1 0 1 1 1 0 0 0 0 1 1 0 1 0 1 0 0 1 0 0
გამომავალი მონაცემები
7568677
თქვენი პასუხი
7568677
ჩეკერის პასუხი
YES
შემავალი მონაცემები
28
0 1 1 1 1 1 1 1 1 1 1 0 0 0 0 1 0 1 1 0 0 0 0 0 1 0 1 1
გამომავალი მონაცემები
167445844
თქვენი პასუხი
167445844
ჩეკერის პასუხი
YES
შემავალი მონაცემები
30
0 0 1 0 0 0 1 1 0 1 1 1 0 1 0 0 0 1 1 1 0 1 1 1 0 0 1 1 1 0
გამომავალი მონაცემები
390843256
თქვენი პასუხი
390843256
ჩეკერის პასუხი
YES
შემავალი მონაცემები
100
1 1 0 1 0 1 0 0 1 0 0 1 1 0 0 1 1 0 0 1 0 0 0 0 1 0 0 0 0 1 0 1 1 0 1 1 1 0 0 1 0 0 0 1 1 0 1 1 1 1 0 1 1 1 0 0 1 1 1 1 1 1 1 0 1 1 0 1 1 1 1 0 1 0 0 0 1 1 1 0 0 0 1 0 1 1 0 0 1 0 1 0 0 0 0 0 1 0 0 1
გამომავალი მონაცემები
1111099096870146813528342860237
თქვენი პასუხი
1111099096870146813528342860237
ჩეკერის პასუხი
YES
შემავალი მონაცემები
100
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
გამომავალი მონაცემები
845100400152152934331135470250
თქვენი პასუხი
845100400152152934331135470250
ჩეკერის პასუხი
YES
შემავალი მონაცემები
300
0 1 1 1 1 1 0 1 0 1 0 1 1 0 1 0 0 0 1 1 1 1 1 1 1 0 1 0 1 1 1 0 1 1 1 1 1 1 1 0 0 0 1 0 0 0 0 1 1 0 1 0 0 0 1 1 0 1 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 1 1 1 0 1 0 0 1 1 1 1 1 1 0 1 0 1 1 1 0 0 1 0 1 0 1 1 0 1 0 0 1 0 0 1 1 1 1 1 1 0 1 0 0 0 1 1 1 0 1 0 1 0...
გამომავალი მონაცემები
72625136771763282767191983955506242642648015746639038100996692034027824315889886392980267
თქვენი პასუხი
72625136771763282767191983955506242642648015746639038100996692034027824315889886392980267
ჩეკერის პასუხი
YES