TAKMIČENJA IZ PROGRAMIRANJA


Sva pitanja, predloge ili primedbe u vezi sa takmičenjima iz programiranja možete slati na e-mail:

tak.prog@gmail.com

U toku perioda za žalbe, sve žalbe možete slati na ovaj isti e-mail.

freksuma.cpp    690 b      izvorni kod rešenja
freksuma.tests.7z    47,472 b      test primeri
freksuma.solution.pdf    57,674 b      rešenje problema

zadatak: Frekventna suma

Dat je niz brojeva A = (a1, ..., aN). Posmatrajmo skup svih suma uzasotpnih članova S = {ai + ... + aj | 1 ≤ ijN}.

Ispisati vrednost iz skupa S koja se najčešće pojavljuje, kao i koliko puta se pojavljuje. U slučaju da ima više takvih, ispisati onu čija je vrednost najveća.

Ulaz.

(Ulazni podaci se učitavaju sa standardnog ulaza.) U prvom redu standardnog ulaza nalazi se prirodan broj N (1 ≤ N ≤ 3000). U sledećem redu nalazi se N prirodnih brojeva, redom a1 , ..., aN, svaki iz intervala [0, 3000].

Izlaz.

(Izlazne podatke ispisati na standardan izlaz.) U prvi i jedini red standardog izlaza ispisati dva prirodna broja, koji redom predstavljaju, broj koji se najšeće pojavljuje u skupu S, i koliko puta se pojavljuje. U slučaju da postoji više takvih brojeva, ispisati onaj koji ima najveću vrednost.

Ograničenja.

U 30% test primera će biti 1 ≤ N ≤ 100.

Primer 1.

standardni ulaz      standardni izlaz
3
1 2 3
        
3 2

Objašnjenje.

Skup S = {1, 1 + 2, 1 + 2 + 3, 2, 2 + 3, 3} = {1, 3, 6, 2, 5, 3}.

Primer 2.

standardni ulaz      standardni izlaz
8
17 13 17 13 5 6 5 6
        
30 3

Objašnjenje.

Primetimo da se i suma 11 pojavljuje 3 puta, ali je 30 veća suma.

fajl: freksuma.cpp
#include <iostream>
#include <cstdio>
#define ffor(_a,_f,_t) for(int _a=(_f),__t=(_t);_a<__t;_a++)
#define SET(__set, val) memset(__set, val, sizeof(__set))
#define FOR(__i, __n) ffor (__i, 0, __n)

using namespace std;

int cnt[9000001], sum[3001];

int main(){
  int n, val;
  scanf("%d", &n);
  sum[0] = 0;
  FOR (i, n){
    scanf("%d", &val);
    sum[i + 1] = sum[i] + val;
  }
  
  SET(cnt, 0);
  
  ffor (i, 1, n + 1){
    val = sum[i];
    FOR (j, i)
      cnt[val - sum[j]]++;
  }
  int mm = 0, ret = -1;
  
  FOR (i, 9000001)
    if (cnt[i] >= mm){
      mm = cnt[i];
      ret = i;
    }
    
  printf("%d %d\n", ret, mm);
    
  return 0;
}