Panel użytkownika
Nazwa użytkownika:
Hasło:
Nie masz jeszcze konta?

Zadanie z main mijanka

Ostatnio zmodyfikowano 2017-06-03 18:35
Autor Wiadomość
badyl94
Temat założony przez niniejszego użytkownika
Zadanie z main mijanka
» 2017-06-03 14:46:26
Hej pracuje nad zadaniem z main'a https://main2.edu.pl/c​/konkurs-podstaw-algorytmiki/p​/mij/
Wszystko niby jest ok ale działa za wolno ma ktoś pomysł jak ten algorytm przyspieszyć?

C/C++
#include <iostream>
using namespace std;

int main()
{
    int n;
    cin >> n;
    int tab[ n ];
    for( int i = 0; i < n; i++ ) cin >> tab[ i ];
   
   
    int wynik = 0;
   
    for( int i = 0; i < n; i++ )
    {
        for( int j = i; j < n; j++ )
        {
            if( tab[ i ] < tab[ j ] ) wynik++;
           
        }
    }
   
    cout << wynik;
   
    return 0;
}
P-162019
pekfos
» 2017-06-03 15:37:18
Użyj innego algorytmu. Po to jest limit czasu, żeby nie dało się użyć podejścia naiwnego.
P-162022
michal11
» 2017-06-03 15:40:17
Wczytuj liczby po kolei, przy każdej wczytanej jedynce dodawaj do wyniku liczbę dotychczas wczytanych zer. Czyli w zasadzie potrzebujesz tylko 2 intów i jeden pętli
P-162023
badyl94
Temat założony przez niniejszego użytkownika
» 2017-06-03 17:42:00
Zrobiłem "chyba" tak jak pisał michal11
C/C++
#include <iostream>
using namespace std;
int main()
{
    int n;
    cin >> n;
    int tab[ n ];
    int wynikZero = 0, wynik = 0;
    for( int i = 0; i < n; i++ ) cin >> tab[ i ];
   
    for( int i = 0; i < n; i++ )
    {
        if( tab[ i ] < 1 ) wynikZero++;
       
        if( tab[ i ] > 0 ) wynik = wynik + wynikZero;
       
    }
   
   
    cout << wynik;
   
    return 0;
}

wyrzuca mi cos takiego na sprawdzarce
4 wiersz 1: wczytano '-2037444346', a oczekiwano '122516607238'
5 wiersz 1: wczytano '1035931238', a oczekiwano '26805735014'
6 wiersz 1: wczytano '420698446', a oczekiwano '124974750030'
8 wiersz 1: wczytano '-1739176257', a oczekiwano '148584679103'
9 wiersz 1: wczytano '214640261', a oczekiwano '124768691845'
P-162028
Monika90
» 2017-06-03 18:10:26
Zrezygnuj z tablicy i użyj typu long long do zliczania samochodów.
P-162029
Chowan
» 2017-06-03 18:11:38
z tego co się doczytałem to @michal11 proponował zrobić wszystko w jednej pętli

C/C++
#include <iostream>
using namespace std;
int main()
{
    int n;
    cin >> n;
    int tab[ n ];
    int wynikZero = 0, wynik = 0;
    for( int i = 0; i < n; i++ ) {
        cin >> tab[ i ];
        if( tab[ i ] == 0 ) wynikZero++;
       
        if( tab[ i ] == 1 ) wynik += wynikZero; }
   
    cout << wynik;
   
    return 0;
}
P-162030
Kinexity
» 2017-06-03 18:15:39
Jeżeli dobrze rozumiem zadanie to taki kod powinien zadziałać:
C/C++
#include <iostream>
using namespace std;

int main()
{
    unsigned long long n, r, lw = 0, wynik = 0;
    cin >> n;
    for( unsigned long long i = 0; i < n; i++ ) {
        cin >> r;
        if( r == 0 ) {
            ++lw;
            continue;
        }
        wynik += lw;
    }
    cout << wynik << endl;
    return 0;
}
P-162032
badyl94
Temat założony przez niniejszego użytkownika
» 2017-06-03 18:35:22
Dzięki pomogło :)
Rzeczywiście tablice są tu nie potrzebne Dzięki jeszcze raz
P-162033
« 1 »
  Strona 1 z 1