1

Тема: Алготестер задачі.Алгоритмічне програмування.С++

Люблю розв'язувати задачі, але ця задача ввела мене в тупік.Ось силка https://www.algotester.com/uk/ArchivePr … play/40684      .   Каже неправильна відповідь на 31-ому прикладі.Мій приклад розв'язання:

#include <iostream>

using namespace std;

// функція Big_char рахує кількість великих символів що йдуть підряд, починаючи з тої позиції яку я їй скажу

int Big_char(string S,int i,int n){
    int k=0;
    while( int(S[ i ]) <97  && i<n  ){
        i++;
        k++;
    }

    return k;
}

int main(){
    string S;
    cin>>S;
    int n,k=0;
    n = S.size();
    k = n;

   //тут я йду по стрічці і перевіряю скільки великих символів йде підряд, і відповідно для кожного випадку збільную k

    for(int i=0;i<n;i++){
        if( Big_char(S,i,n)>2 ){
            k+=3;
            i+= (  Big_char(S,i,n)-1 );
        }
        else{
            if( Big_char(S,i,n)==1 ){
                k++;

            }
            if( Big_char(S,i,n)==2 ){
                k+=2;
                i+=1;

            }

        }


    }
    if(n>1){
            if( int(S[n-1])<97 &&  int(S[n-2])<97) k-=1;
    }
    cout<<k;
    return 0;

}

Задачі роз'язую в середощі CodeBlocks. Я учень 10 класу і буду дуже вдячний вашій допомозі.

Подякували: koala, leofun012

2

Re: Алготестер задачі.Алгоритмічне програмування.С++

що складного? якщо 4, або більше, великих підряд, натискай 2 рази, інакше натискай 1 раз.
почитай про кінцеві автомати

Подякували: leofun01, zxzpogoncuk2

3 Востаннє редагувалося koala (21.12.2019 07:35:27)

Re: Алготестер задачі.Алгоритмічне програмування.С++

По-перше, дякую за майже ідеальне питання. Є все: умова, код і опис проблеми з достатнім для відтворення описом, а також додаткова корисна інформація (на кшталт вашого досвіду і середовища розробки). Навіть трохи невдала назва не псує враження.
По-друге, раджу трохи по стилю:
- акуратніше вирівнювати код (зайві пусті рядки та if в один рядок - погано);
- зазвичай прийнято не називати функції та змінні з великої літери;
- "магічні числа", тобто літерали всередині коду без пояснень - зло. Що таке 97? В C/C++ char, насправді, такі самі числа, як і int, і можна писати просто S[i]<'a' ('a'==97, можете перевірити), але краще скористатися функцією isupper з <ctype.h>/<cctype>, ця функція працюватиме і з іншими кодуваннями, а також чітко продемонструє ваш намір виявити велику літеру;
- змінні бажано ініціалізувати одразу при створенні:

int n = S.size();
int k = n;

- якщо у вас є кілька взаємовиключних if-else, їх можна записати так:

if (умова) {
    вираз;
} else if (умова) {
    вираз;
} else if (умова) {
    вираз;
} else {
    вираз;
}

або через switch-case. Це покращує читаність.
По-третє, по оптимальності:
- ви викликаєте Big_char 4 рази, замість викликати 1 раз і зберегти результат;
- ви передаєте в Big_char string та його довжину; загалом, лише в останніх версіях C++ string::size стала гарантовано швидкою, так що це могло б мати сенс, якби ви передавали посилання на стрічку (string &). Ви ж передаєте копію стрічки.

Ну і по суті - ви не дуже уважно виписали останню умову, про не натискання зайвого SHIFT в кінці стрічки. Наприклад, ви не зможете ввести "AA" менш ніж за 4 натискання (↑a↑a чи ↑↑aa), а цей код відповідає, що 3.

І так, підтримую ur_naz, що про скінчені автомати таки варто почитати. Хоча конкретно тут це буде на муху з обухом іти, та й у словник декому варто зазирнути.

Подякували: leofun01, wander, zxzpogoncuk3

4

Re: Алготестер задачі.Алгоритмічне програмування.С++

трохи рефакторінгу циклу
    for(int i=0;i<n;i++){
        int b = Big_char(S,i,n);
        if(b==1){
            k+=1;
        } else if(b==2) {
            k+=2;
            i+=1;
        } else if(b>2) {
            k+=3;
            i+= (  b-1 );
        }
    }

А тепер стає зрозумілим, що в усіх трьох варіантах i збільшується на b-1, а k - на b, але не більш як на 3, тобто можна скористатися функцією min з  <algorithm>:

    for(int i=0;i<n;i++){
        int b = Big_char(S,i,n);
        if(b>0){
            k+=min(3,b);
            i += (b-1);
        } 
    }

Але якщо Big_char поверне 0, то k не зміниться, тобто зміниться на 0, і i теж має не змінитися, тобто змінитися не менш як на 0:

    for(int i=0;i<n;i++){
        int b = Big_char(S,i,n);
        k += min(3, b);
        i += max(0, b-1);
    }

Тепер би ще перейменувати змінні на щось на кшталт keys_needed та upper_length - і буде просто ідеально.

Подякували: zxzpogoncuk1

5 Востаннє редагувалося koala (21.12.2019 01:07:55)

Re: Алготестер задачі.Алгоритмічне програмування.С++

А, ну і ще cin::operator>> читає до пробіла; тут це не має особливого значення, але в цілому це треба враховувати.
А ще бажано обгортати алгоритм в окрему функцію, без введення-виведення.

Подякували: zxzpogoncuk1

6 Востаннє редагувалося ur_naz (21.12.2019 01:33:47)

Re: Алготестер задачі.Алгоритмічне програмування.С++

мені просто те слово не подобається. як і люди, ще не знають, що ніки не відмінюються

Подякували: zxzpogoncuk1

7 Востаннє редагувалося koala (21.12.2019 09:45:54)

Re: Алготестер задачі.Алгоритмічне програмування.С++

ur_naz написав:

мені просто те слово не подобається.


Ну вибачте, математичні терміни - то математичні терміни. Скінчена множина має скінчену кількість елементів, на відміну від нескінченої; а у вас як - кінцева множина і некінцева?

ur_naz написав:

як і люди, ще не знають, що ніки не відмінюються

Ой, ну вибачте, виправив. За правилами, до речі, відмінюються, бо це просто слова; але якщо вам так приємніше - особисто вас не відмінюватиму. Хоча узагалі трохи дивно бачити зауваження до мого способу написання від людини, що жодного разу ще не спромоглася написати моє псевдо без помилок.

Подякували: leofun011

8

Re: Алготестер задачі.Алгоритмічне програмування.С++

А ви пробували закинути задачу на перевірку? Її зарахувало як правильну? Просто зараз далеко від дому і не можу перевірити.

9

Re: Алготестер задачі.Алгоритмічне програмування.С++

І як правильно називати тему питання, щоб мене зрозуміли? Я буду часто просити допомоги при розв'язанні задач.

10

Re: Алготестер задачі.Алгоритмічне програмування.С++

Дякую всім хто намагався допомогти. Хоч я не виправив недоліки коду(я надто лінивий), але ви допомогли зробити мені задачу на максимальний бал.
#include <iostream>

using namespace std;

int Big_char(string S,int i,int n){
    int k=0;
    while( int(S[ i ]) <97  && i<n  ){
        i++;
        k++;
    }

    return k;
}

int main(){
    string S;
    cin>>S;
    int n,k=0;
    n = S.size();
    k = n;
    for(int i=0;i<n;i++){
            int b = Big_char(S,i,n);
        if( b>2 ){
            k+=3;
            i+= ( b-1 );
            if(i== (n-1)) k--;
        }
        else{
            if( b==1 ){
                k++;

            }
            if(b==2 ){
                k+=2;
                i+=1;

            }

        }


    }

    cout<<k;
    return 0;

}


https://replace.org.ua/uploads/images/9774/510bf14f1bfabbbb27e9fccb2ec7103e.jpg

11 Востаннє редагувалося koala (21.12.2019 15:10:10)

Re: Алготестер задачі.Алгоритмічне програмування.С++

Для порівняння:

#include <iostream>
#include <cctype>
#include <algorithm>

using namespace std;

int upper_length(const string& s,int start){
    int position = start;
    int size = s.size();
    while( position<size && isupper(s[position]) ){
        ++position;
    }
    return position-start;
}

int count_keys(const string& s)
{
    int size = s.size();
    int keys_needed = size;
    int upper;

    for(int i=0;i<size;i++){
        upper = upper_length(s,i);
        keys_needed += min(3, upper);
        i += max(0, upper-1);
    }
    if(upper>=3){
        keys_needed -= 1;
    }
    return keys_needed;
}

int main(){
    string s;
    getline(cin, s);
    cout<<count_keys(s);
    return 0;
}

Сподіваюся, пан ur_naz спроможеться написати розв'язок на скінчених автоматах, це буде найкращий варіант.

Подякували: zxzpogoncuk1

12 Востаннє редагувалося koala (21.12.2019 16:26:27)

Re: Алготестер задачі.Алгоритмічне програмування.С++

Заголовок має ідентифікувати проблему.
"Алготестер, задача 1508, кількість натискань на Shift: не вдається пройти тести" - досить інформативно, порівняно із поточним.
Я переношу питання в C++.

Подякували: zxzpogoncuk1