|
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.
|
logo by Igor Antolović
|
|
|
zadatak: Frekventna suma
|
Dat je niz brojeva A = (a1, ..., aN). Posmatrajmo skup svih suma
uzasotpnih članova S = {ai + ... + aj | 1 ≤ i ≤ j ≤ N}.
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;
}
|
|
|