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

Smakołyki - ilość sposobów wyboru słodyczy

Ostatnio zmodyfikowano 2018-04-04 23:02
Autor Wiadomość
M44NBE
Temat założony przez niniejszego użytkownika
Smakołyki - ilość sposobów wyboru słodyczy
» 2018-03-30 21:59:39
Teść zadania: https://main2.edu.pl/c​/konkurs-podstaw-algorytmiki/p​/sma/

Rozwiązuję zadanie poniższym sposobem dla danych wejściowych:
5 3
1 3 2 2 3

1 - 1 możliwość [1]
3 - 2 możliwości [3; 3,1]
2 - 3 m. [2; 2,3; 2,3,1]
2 - 1 m. [2]
3 - 2 m. [3; 3,2]    1 + 2 + 3 + 1 + 2 = 9

Podczas sprawdzania pojawiają się błędy:
2a wiersz 1: wczytano '53', a oczekiwano '36'
3a wiersz 1: wczytano '6307725', a oczekiwano '430001'
3b wiersz 1: wczytano '28', a oczekiwano '19'
4a wiersz 1: wczytano '2246063', a oczekiwano '137815'
5a wiersz 1: wczytano '1789516979', a oczekiwano '25796059'
5b wiersz 1: wczytano '261602', a oczekiwano '261391'
6a wiersz 1: wczytano '2814387425', a oczekiwano '18506036'
7a wiersz 1: wczytano '6192726304', a oczekiwano '63903167'
7b wiersz 1: wczytano '513997', a oczekiwano '513991'
8 wiersz 1: wczytano '500000500000', a oczekiwano '265159214416'
9 wiersz 1: wczytano '500000500000', a oczekiwano '1237634347'
10 wiersz 1: wczytano '500000500000', a oczekiwano '274098756558'

wszystkie wczytane zmienne są większe od oczekiwanych, dlatego możliwe, że dla niektórych danych wejściowych nie powinienem zwiększać zmienną 'sum' o zwracaną z funkcji 'subsequentNumbers'
sum += subsequentNumbers( n - box );
 
Męczę się z tym zadaniem i sam już nie wiem co jest w nim źle, możliwe, że rozumowanie początkowe nie do końca jest prawidłowe, dlatego proszę o podpowiedź.

Kod:
C/C++
#include <iostream>
using namespace std;
long long subsequentNumbers( long x ) //zwracanie ilości możliwości w ciągu kolejnych liczb
{
    long long suma( 0 );
    for( int i = 1; i <= x; i++ )
         suma += i;
   
    return suma;
}
int main()
{
    int n, m, box( 0 ); long long sum( 0 );
    cin >> n >> m;
    int * c = new int[ n ];
   
    for( int i = 0; i < n; i++ )
         cin >> c[ i ];
   
    for( int j = 1; j < n; j++ )
    {
        if( c[ j ] == c[ j - 1 ] )
        {
            sum += subsequentNumbers( j - box );
            box = j;
        }
    }
    sum += subsequentNumbers( n - box );
    cout << sum;
    return 0;
}
 
P-170376
darko202
» 2018-04-04 23:02:12
zadanie

Natalia ustawiła w rzędzie n smakołyków.
Każdy smakołyk ma przypisany pewien rodzaj.
Natalia może teraz wybrać pewną liczbę (od 1 do n ) sąsiednich smakołyków,
a następnie je wszystkie zjeść.
Jedynym warunkiem jest to, aby żadne dwa smakołyki nie były tego samego rodzaju.

Pomóż Natalii
i znajdź liczbę sposobów, na które może wybrać sąsiednie smakołyki.

Wejście
Pierwszy wiersz wejścia zawiera dwie liczby całkowite :
n - liczbę smakołyków
m - liczbę dostępnych ich rodzajów
(1 ≤ n, m ≤ 1 000 000),

Drugi wiersz zawiera n liczb całkowitych c0, c1, . . . , cn−1

(1 ≤ ci ≤ m), gdzie ci oznacza rodzaj i-tego smakołyka.

Wyjście
Pierwszy i jedyny wiersz wyjścia powinien zawierać jedną liczbę całkowitą, równą liczbie sposobów,
na któreNatalia może wybrać sąsiednie smakołyki.

Przykład
Dla danych wejściowych:
5 3
1 3 2 2 3
poprawnym wynikiem jest: 9



Rozwiązania :

(1), (3), (2), (2), (3),
(1 3), (3 2), (2 3),
(1 3 2),

stąd liczba 9 jako rozwiązanie
P-170462
« 1 »
  Strona 1 z 1