Imprimă pagina - 312 Sume 2

infoarena - concursuri, probleme, evaluator, articole => Arhiva de probleme => Subiect creat de: Mircea Pasoi din Februarie 04, 2007, 00:43:20

Titlul: 312 Sume 2
Scris de: Mircea Pasoi din Februarie 04, 2007, 00:43:20

Aici puteţi discuta despre problema Sume 2 (http://infoarena.ro/problema/sume2).

Titlul: Răspuns: 312 Sume 2
Scris de: Savin Tiberiu din Februarie 04, 2007, 10:55:35

nu ar fi trebuit intai sa dati acces userilor la problema si abia apoi sa o puneti in arhiva si topic pe forum??

Titlul: Răspuns: 312 Sume 2
Scris de: Adrian Diaconu din Februarie 04, 2007, 12:00:03

Ups... :-'
S-a rezolvat, acum ar trebui sa fie vizibil.

Titlul: Răspuns: 312 Sume 2
Scris de: Paul-Dan Baltescu din Februarie 04, 2007, 12:59:38

In enunt, fisierele de intrare/iesire sunt gresite (lipseste un 2 acolo :) ).

Titlul: Răspuns: 312 Sume 2
Scris de: Adrian Diaconu din Februarie 04, 2007, 13:28:11

S-a rezolvat si asta :)

Titlul: Răspuns: 312 Sume 2
Scris de: David si Goliat din Februarie 04, 2007, 16:32:52

De ce iau la toate testele "Killed by signal 11(SIGSEGV)" cu toate ca declar 6 MB de memorie si limita e 16 ??

Titlul: Răspuns: 312 Sume 2
Scris de: Mircea Pasoi din Februarie 04, 2007, 16:59:11

http://infoarena.ro/documentatie/evaluator

Titlul: Răspuns: 312 Sume 2
Scris de: Farcasanu Alexandru Ciprian din Ianuarie 18, 2008, 10:41:13

Care este varianta optima de rezolvare.....adica eu sortez vectorul cu numerele din fisierul de intrare.....si apoi am facut asa

Cod:

for (i=1;i<=n;i++)
	{
	c++;
	if(c==l) { d=i; e=i; break;}
	for(j=i+1;j<=n;j++)
		{
		c=c+2;
		if(c>=l) { d=i; e=j; break;}
		}
	if(d!=0) break;
	}
fprintf(g,"%d",v[e]+v[d])

iau 4 WA si 6 tle.....

Later Edit: nu raspunde nimeni ? nu stie chiar nimeni?

Titlul: Răspuns: 312 Sume 2
Scris de: Serban Andrei Stan din Aprilie 21, 2008, 11:50:15

Nu cumva limita de timp este eronat pusa? Am trimis o sursa, si iau pe ultimele trei teste TLE, cu 128ms. In enunt, limita este de 200ms... ???

Titlul: Răspuns: 312 Sume 2
Scris de: Bogdan-Alexandru Stoica din Aprilie 21, 2008, 11:59:18

limita este pusa corect. evaluatorul arata timpul la care ti-a omorat programul si probabil afiseaza un pic mai putin. s-au luat 100 de puncte si cu 134ms: http://infoarena.ro/job_detail/13486
incearca sa trimiti sursa asta si o sa te convingi:

Cod:

#include <stdio.h>

int main()
{
	while(1);
	return 0;
}

Titlul: Răspuns: 312 Sume 2
Scris de: Serban Andrei Stan din Aprilie 21, 2008, 12:03:50

Am trimis programelul de ciclare, si iau TLE, dar cu 252 ms :sad: . O sa incerc sa scot o solutie mai smechera, sau sa o optimizez pe asta... http://infoarena.ro/job_detail/182812. Gata, s-a rezolvat, tle-urile s-au facut incorecturi :D. Multumesc mult!

Titlul: Răspuns: 312 Sume 2
Scris de: Andrei Grigorean din Aprilie 21, 2008, 12:27:49

Savim, pune te rog un link catre jobul unde spuneai ca ai luat TLE la 128 de ms.

Titlul: Răspuns: 312 Sume 2
Scris de: Serban Andrei Stan din Aprilie 21, 2008, 12:41:47

Pai, nu il mai gasesc. Sau s-a facut incorect de la sine, sau am gresit eu... in acest caz imi cer mii de scuze. Oricum, sunt destul de sigur ca luam tle cu 128 ms...

Titlul: Răspuns: 312 Sume 2
Scris de: Andrei Grigorean din Aprilie 21, 2008, 12:57:47

:)) nu cred ca s-a facut incorect de la sine... Poate ai vazut gresit. In mod normal nu ar trebui sa iei TLE cu 128 de ms.

Titlul: Răspuns: 312 Sume 2
Scris de: Mihai Botezatu Catalin din Martie 01, 2009, 11:58:14

Imi da o eraore la test killed by signal sigsev 11, ce inseamna?Imi poate zice cineva? ](*,)

Titlul: Răspuns: 312 Sume 2
Scris de: Pripoae Teodor Anton din Martie 01, 2009, 13:40:59

Citeste documentatia inainte sa postezi aiurea. Deja sunt cred ca peste 20-30 de posturi in care se intreaba asta :|. Poti da un search pe forum inainte de intreba. Aici e documentatia despre evaluator: http://infoarena.ro/documentatie/evaluator (http://infoarena.ro/documentatie/evaluator)

Titlul: Răspuns: 312 Sume 2
Scris de: Maria Stanciu din Martie 01, 2009, 16:40:13

Citat din mesajul lui: Mihai Botezatu Catalin din Martie 01, 2009, 11:58:14

Imi da o eraore la test killed by signal sigsev 11, ce inseamna?Imi poate zice cineva? ](*,)

"11(SIGSEGV): Segmentation fault. Asta in 99% din cazuri inseamna ca ai probleme cu accesul la memorie. Ai iesit din limitele unui vector, ai facut stack overflow, etc." (citat din documentatie, si eu te sfatuiesc sa dai click si sa citesti)

Titlul: Răspuns: 312 Sume 2
Scris de: speedzeal din Iulie 22, 2009, 12:50:30

Ma chinuiesc de cateva saptamani la problema asta... ](*,)...Imi da cineva un hint?
Multumesc.

Titlul: Răspuns: 312 Sume 2
Scris de: Andrei Misarca din Iulie 22, 2009, 14:33:30

Incearca sa cauti binar rezultatul. Gandeste-te daca am o suma fixata cum pot determina cate sume sunt mai mici sau egale cu ea

Titlul: Răspuns: 312 Sume 2
Scris de: aladin aladinn din Octombrie 04, 2009, 21:00:26

vad ca sunt multi care au luat 70 si apoi 100 ,poate sa imi dea cinevaun hint cum sa mai scot 30 de puncte?am folosit cautare binara am pus si long long nu stiu ce sa mai fac :'( multumesc anticipat

Titlul: Răspuns: 312 Sume 2
Scris de: Andrei Misarca din Octombrie 04, 2009, 23:38:42

Eu luam 80 pentru că nu declaram K si soluția long long.

Titlul: Răspuns: 312 Sume 2
Scris de: aladin aladinn din Octombrie 05, 2009, 12:20:37

am pus long long ,am verificat pe numere de 20 de cifre si merge :? nu stiu ce sa-i mai fac ](*,)
{later edit} uitasem sa pun long long la o variabila :-'...,dar acum iau 80 cu 2 TLE #-o vreo idee de optimizare?

Titlul: Răspuns: 312 Sume 2
Scris de: UAIC.VlasCatalin din August 10, 2011, 12:24:12

care-i ideea la problema asta, ceva indicii pls!! :)

Titlul: Răspuns: 312 Sume 2
Scris de: Simoiu Robert din August 10, 2011, 12:39:14

Ti-a dat Mishu un hint cu vreo 5 posturi mai sus.

Titlul: Răspuns: 312 Sume 2
Scris de: George Marcus din August 11, 2011, 13:53:54

Citat din mesajul lui: Andrei Misarca din Iulie 22, 2009, 14:33:30

Gandeste-te daca am o suma fixata cum pot determina cate sume sunt mai mici sau egale cu ea

Cum se raspunde cel mai (destul de) eficient la aceasta intrebare?

Titlul: Răspuns: 312 Sume 2
Scris de: Tirca Bogdan din August 15, 2011, 00:42:41

Sa zicem ca suma fixata este S. Pentru a afla cate sume sunt mai mici ca aceasta, pentru fiecare element din vector trebuie sa vedem cate elemente din acelasi vector sunt mai mici sau egale cu S - element_curent si cate sunt strict mai mici decat S - element_curent. Sumele acestor valori sa le notam cu upper si lower. Tot ce mai trebuie facut este sa verificam daca lower < k && k <= upper.

Titlul: Răspuns: 312 Sume 2
Scris de: Cosmin Rusu din Decembrie 20, 2011, 17:44:04

Cod:

#include <fstream>
using namespace std;
int main()
{
    ifstream cin("sume2.in");
    ofstream cout("sume2.out");
    int A[100005], i, j, S[100005], o, aux, a=0;
    long long k, n;
    cin>>n;
    cin>>k;
    for(i=1;i<=n;i++)
      cin>>A[i];
    for(i=1;i<=n;i++)
     {
       for(j=1;j<=n;j++)
          S[j+a]=A[i]+A[j];
       a=i*n;
     }  
do
{
 o=1;
 for(i=1;i<n*n;i++)
  if(S[i]>S[i+1])
  {
   o=0;
   aux=S[i];
   S[i]=S[i+1];
   S[i+1]=aux;
   }
}while(!o);
cout<<S[k]<<"\n";
cin.close();
cout.close();

return 0;
}

Ce am gresit ? La celelalte 8 imi da Killed by signal! :-'

Titlul: Răspuns: 312 Sume 2
Scris de: Mihai Calancea din Decembrie 20, 2011, 18:48:43

N-ul e 50 000. Ce-ti spune asta despre N ^ 2?

Titlul: Răspuns: 312 Sume 2
Scris de: Teodor Sz din Ianuarie 28, 2014, 19:47:16

Am probleme cu limitele ](*,) daca pun int iau 40p ( http://www.infoarena.ro/job_detail/1088260 ) , daca pun unsigned int iau 60p (http://www.infoarena.ro/job_detail/1088263) cu killbysem la primele 4 pot ( ](*,) ](*,) ](*,) ) si daca pun long long iau 0p :-k

Titlul: Răspuns: 312 Sume 2
Scris de: Adrian Budau din Ianuarie 29, 2014, 14:04:49

Nu e de la limite. Ai tu greseli in program. Ti-am gasit destul de repede greseala in program si nu iti voi spune care este dintr-un motiv foarte simplu. NU inveti nimic din asta.

Incearca sa te uiti prin codul tau la fiecare linie scrisa sa-ti gasesti greseala. Daca nu poti asa, invata sa-ti scrii un generator de teste, pentru problema asta e foarte simplu, functiile srand si rand (le poti cauta pe cplusplus.com) sunt aici ca sa te ajute. Dupa poti sa faci si un mini-evaluator (un program care genereaza, ruleaza sursa ta si iti spune daca a rulat bine sau nu), unde aici iti este prietena functia system (pe care din nou o poti cauta pe cplusplus.com). Rog si ca nimeni altcineva sa nu-ti raspunda exact cu problema insasi, singura chestie pe care o castigi sunt inca 40 de puncte, cand ai putea castiga niste experienta.

Titlul: Răspuns: 312 Sume 2
Scris de: Valeriu Motroi din August 31, 2014, 10:12:30

Complexitatea necesară pentru 100p este O(N logN)?
Cu O(N log^2N) iau doar 60p :( ](*,)

Edit: am optimizat un pic, și a mers.

Titlul: Răspuns: 312 Sume 2
Scris de: Balosache Alexandru Cosmin din Martie 18, 2015, 19:23:57

Poate sa ma ajute si pe mine cineva cu problema asta imi trebuie o varianta cat mai optima?