Imprimă pagina - 1120 Inundatie

Titlul: 1120 Inundatie
Scris de: Andrei Parvu din Aprilie 02, 2011, 21:27:37

Aici puteti discuta despre problema Inundatie (http://infoarena.ro/problema/inundatie).

Titlul: Răspuns: 1120 Inundatie
Scris de: Vlad Schnakovszki din Aprilie 04, 2011, 11:46:38

Aveti careva vreo idee de ce imi da programul asta incorect? Stiu ca nu e complexitate optima, dar totusi, ar trebui sa ia cateva teste. ](*,)

Cod:

#include <cstdio>
#define LIM 90005
using namespace std;
FILE *f=fopen("inundatie.in", "r"), *g=fopen("inundatie.out", "w");
unsigned long long inu[LIM];
long m, n, i, j, x, k, max;
inline void citeste()
{
	fscanf(f, "%ld%ld", &n, &m);
	n=m*n;
	for (i=1;i<=n;i++)
		{
			fscanf(f, "%ld", &x);
			if (x)
			{
				for (j=2;j<=x;j++)
					inu[j]+=j-1;
				for (j=x+1;j<=n;j++)
					inu[j]+=x;
			}
		}
	max=inu[n];
}

inline void rezolva()
{
	fscanf(f, "%ld", &k);
	for (i=1;i<=k;i++)
	{
		fscanf(f, "%ld", &x);
		if (x>n)
			fprintf(g, "%lld\n", max);
		else
			fprintf(g, "%lld\n", inu[x]);
	}
}

int main()
{
	citeste();
	rezolva();
	fclose(f);
	fclose(g);
	return 0;
}

Titlul: Răspuns: 1120 Inundatie
Scris de: Andrici Cezar din Aprilie 04, 2011, 19:05:22

Iau 70 de puncte si 3 incorecte ](*,). Aveti idee daca exista un test special sau ceva de genu? :-k?

---- Edit -----
Am luat 100 pana la urma, nu mai trebuie! :winner1:

Titlul: Răspuns: 1120 Inundatie
Scris de: Botocan Bogdan din Aprilie 06, 2011, 18:21:49

Si o mica idee de rezolvare... ? :-'

Titlul: Răspuns: 1120 Inundatie
Scris de: Adrian Craciun din Aprilie 06, 2011, 18:35:17

matricea poate fi transformata intr-un vector ... pe care il sortam
si apoi cautam binar ... cred ca am zis destul si o sa te prinzi cum se rezolva :D

Titlul: Răspuns: 1120 Inundatie
Scris de: Teodor Plop din Aprilie 14, 2011, 20:14:04

exact asta am facut si eu.am transformat matricea in vector.o cautare binara pentru eq-1 in vector...apoi afisez suma de la pozitia 1 la pozitia cautarii binare + (eq-1) * numarul elementelor ramase.
ceva gresit in asta?

Titlul: Răspuns: 1120 Inundatie
Scris de: Tirca Bogdan din Aprilie 15, 2011, 09:19:31

Pentru un query=0 ce-ti afiseaza? Si din cate tin minte trebuie lucrat pe long long

Titlul: Răspuns: 1120 Inundatie
Scris de: Mihai Visuian din Aprilie 18, 2011, 20:34:41

dar ce se cauta binar??

Titlul: Răspuns: 1120 Inundatie
Scris de: Sturzu Antonio-Gabriel din Aprilie 18, 2011, 20:50:07

Cauti binar prima pozitie pentru care numarul de etaje e strict mai mare decat numarul
de etaje-1 din query.

Titlul: Răspuns: 1120 Inundatie
Scris de: Teodor Plop din Aprilie 19, 2011, 17:47:12

da..am lucrat si pe long long :| ... tot 60 iau..

Titlul: Răspuns: 1120 Inundatie
Scris de: Teodor Plop din Aprilie 19, 2011, 18:03:11

si da..am tratat si cazul cu eq=0 ;
if (x==0)
{
printf("0\n");
break;
}

Titlul: Răspuns: 1120 Inundatie
Scris de: Mihai Visuian din Aprilie 20, 2011, 13:55:42

teodor, dar nu da bine daca faci dupa formula precedenta
sau cum merge de exemplu pentru eq = 2?

Titlul: Răspuns: 1120 Inundatie
Scris de: Ion Vlad-Doru din Iulie 07, 2011, 20:03:38

@ Teodor: Vezi sa nu fie nevoie de continue in loc de break acolo.

Titlul: Răspuns: 1120 Inundatie
Scris de: Teodor Plop din Septembrie 13, 2011, 15:36:40

continue in loc de break... genial. nu m-as fi gandit la asta :)) . mersi.

Titlul: Răspuns: 1120 Inundatie
Scris de: Plesa Mihail Iulian din Decembrie 28, 2011, 11:58:25

Eu am facut programul:

Cod:

#include<cstdio>
using namespace std;
long int a[90001],i,j,s,d,ok=0,m,x,n,m1,q,aux,s1;
int main()
{FILE*f=fopen("inundatie.in","r");
FILE*g=fopen("inundatie.out","w");
fscanf(f,"%ld %ld",&n,&m1);
n=n*m1;
for(i=1; i<=n; i++)
	fscanf(f,"%ld",&a[i]);
for(i=1; i<=n; i++)
	for(j=i+1; j<=n; j++)
		if(a[i]>a[j]){
			aux=a[i];
			a[i]=a[j];
			a[j]=aux;
		}
fscanf(f,"%ld",&q);
for(i=1; i<=q; i++){
	s1=0;
	ok=0;
fscanf(f,"%ld",&x);
x--;
s=1;
d=n;
while(ok==0){
	m=(s+d)/2;
	if(x>a[m])
		s=m+1;
	if(x<a[m])
		d=m-1;
	if((x>=a[m] && x<a[m+1]) || x==a[m])
		ok=1;
}
for(j=1; j<=m; j++)
	s1=s1+a[j];
s1=s1+(x*(n-m));
fprintf(g,"%ld\n",s1);
}
}

pe 9 din 10 teste este depasita limita de timp. Ma puteti ajuta va rog?
Multumesc!

Titlul: Răspuns: 1120 Inundatie
Scris de: Pirtoaca George Sebastian din Decembrie 28, 2011, 12:10:50

Mihai , tu acolo depasesti cu mult limita, incearca sa inveti o sortare mai rapida quick sort sau sort din STL. Problema se rezolva cu ajutorul cautarii binare. Ti-am trimis sursa mea prin PM. Sper ca am fost de ajutor.

Titlul: Răspuns: 1120 Inundatie
Scris de: Plesa Mihail Iulian din Decembrie 28, 2011, 12:33:52

Citat din mesajul lui: Pirtoaca George Sebastian din Decembrie 28, 2011, 12:10:50

Multumesc frumos!

Titlul: Răspuns: 1120 Inundatie
Scris de: Albu Alexandru din Martie 28, 2012, 18:50:18

Eu am facut problema cu sort din STL si pentru aflarea pozitiei am folosit lower_bound. De ce imi da TLE pe 5 teste? http://infoarena.ro/job_detail/728522

L.E: Am luat 100pct.

Titlul: Răspuns: 1120 Inundatie
Scris de: Vasilut Lucian din Iulie 15, 2012, 11:47:59

Salutare.Am folosit la problema asta :
sortarea cu sort din STL + cautarea pozitiei cu upper_bound.
iau 50 pct cu TLE :'(
Nu stiu ce as mai putea reduce...
Vreo sugestie ceva?
Multumesc Anticipat!!! :D

Titlul: Răspuns: 1120 Inundatie
Scris de: Salajan Razvan din Iulie 15, 2012, 11:59:09

incearca sa scapi de for-ul de dupa ce afli pozitia :)(iti mananca timp si il poti scoate :) )

Titlul: Răspuns: 1120 Inundatie
Scris de: Vasilut Lucian din Iulie 15, 2012, 12:12:17

Am facut sume partiale si am luat 100 \:D/

Salajan Razvan: mersi pt sugestie :thumbup:

Titlul: Răspuns: 1120 Inundatie
Scris de: FMI Paun Matei din Decembrie 23, 2012, 22:40:57

Nu inteleg dc iau 60. ](*,)
-pun in vector nr din matrice
-sortez cu sort din STL
-fac sume partiale
-caut binar pozitia
-afisez sume [ poz_cautata ] + ( nr - poz_cautata ) * ( valoarea_cautata - 1 ) ;
si am luat si cazul particular cu 0
Sugestii ?

Titlul: Răspuns: 1120 Inundatie
Scris de: Visan Radu din Decembrie 23, 2012, 23:18:06

printf ( "0\n" ) ;

Titlul: Răspuns: 1120 Inundatie
Scris de: FMI Paun Matei din Decembrie 23, 2012, 23:25:30

Citat din mesajul lui: Visan Radu din Decembrie 23, 2012, 23:18:06

printf ( "0\n" ) ;

ms nu mi-as fi dat niciodata seama :))

Titlul: Răspuns: 1120 Inundatie
Scris de: FMI Razvan Birisan din Februarie 28, 2013, 12:42:14

Pentru :

Cod:

25 62
490 5082 15571 30526 29419 24137 9069 5877 10608 18682 19164 13157 16429 21470 794 11563 25494 20143 7626 3315 16635 7044 30328 31396 28920 32675 20513 13528 24844 30358 11254 7311 136 15233 32093 10532 13483 31922 24377 22656 22539 28026 11883 28557 18742 10811 11673 7917 19610 8899 5677 24557 17826 32472 15009 7604 2850 12564 7675 32449 23285 11252 
9363 25236 12517 27947 16924 26538 1226 21308 18658 3503 13302 28999 15953 18416 6609 21795 22711 5135 7105 29614 2635 26874 11341 12129 15725 4637 2433 11560 9775 19159 14996 27504 19733 11819 4296 20353 14105 20153 12178 7438 20210 2796 24571 3082 29590 29044 13126 28862 20478 18935 14547 10777 24617 5635 19267 19015 18275 7752 14557 11653 23495 24580 
19248 29491 2819 28350 29178 3370 31835 7735 5449 22865 5105 2206 21216 31083 15171 17667 10972 23859 4853 25102 24472 12971 29137 30961 3277 12465 21772 27803 14846 28627 9674 10542 27667 17764 30693 30644 31300 21711 9706 14862 10808 19244 28261 9004 22382 30993 30303 16260 10717 16043 21796 25020 8151 32269 3402 18346 28467 1991 5870 2943 427 13755 
24385 13631 4227 10284 24900 117 9068 22808 15311 10788 30375 31176 26840 23296 3181 20133 31218 478 28047 32077 32276 12906 23898 230 29852 23576 1213 14515 29075 27997 22702 17636 22323 14110 16329 9651 18598 9321 15162 20652 14865 6755 5854 12364 16849 5249 25765 16846 3845 20731 18235 17730 10572 8574 20455 13279 24016 13346 29619 28826 32131 26779 
23501 26360 20648 1459 5421 3104 25494 25336 25464 30260 4280 23217 15140 32225 27609 6167 9950 7733 29342 5570 7208 1713 9812 24674 839 5024 29420 29103 30300 8359 1860 14243 31697 27036 681 7142 16374 28059 7065 8074 4588 2135 9165 24312 10179 13743 3447 4650 28127 13186 21960 23835 26016 30147 30901 1148 22338 8400 20987 23209 23297 32255 
3936 30939 32129 7802 6204 6303 878 8270 3641 8583 4191 18878 19287 16159 13569 28381 307 4898 10353 21852 23944 22510 12521 2720 22518 1846 32671 24599 3330 22775 1002 461 19039 11949 31143 23354 12396 16070 14043 15967 3325 5207 31898 273 21342 14094 20263 1172 21909 3944 6492 23403 8936 23331 8012 367 12191 17911 1064 23071 10763 31361 
26463 26935 8391 16256 23817 31108 24126 30019 17798 9718 7533 1890 18530 30967 31723 9901 30332 5627 19750 24418 22376 8536 13039 24483 26129 23129 7993 550 16547 7053 8989 28975 4008 13669 12066 30139 26737 22270 10428 18174 11959 31036 30994 28176 14722 24 30980 4580 16202 1595 24173 16249 19804 1739 3749 596 20096 22917 31307 24877 25817 13580 
26177 4841 6924 11136 17911 32712 12453 21843 2797 25312 1462 7768 3443 8138 27072 26909 29364 8347 20951 31867 13298 20501 14850 28523 11027 1055 13793 1819 18525 27763 29842 15170 21886 22935 15316 21680 27087 28686 7789 23081 29657 7119 29130 16243 31769 22518 18150 2734 1280 7866 27245 25572 11326 5535 12320 17121 28992 18924 3451 12101 17655 4448 
18325 18135 18140 25377 14409 32284 21297 15605 28307 20265 18057 26804 11836 19125 6794 13822 4794 16242 16370 31785 22866 27550 23000 30845 5759 27860 15925 23716 23191 25129 24482 8540 2476 29812 1123 29039 27312 14573 28325 16613 12765 8698 23044 25720 2644 29253 29264 15688 25349 26130 10129 19664 718 1744 840 17689 10215 23789 25336 26925 13949 29679 
15333 20943 15005 25793 19484 27241 16724 23114 23731 14918 19733 17476 31058 19969 26970 11340 16627 21822 8590 24885 13285 18583 24363 27810 8983 11226 29472 1748 9363 16497 20085 31936 12617 15393 11825 15461 20494 22520 15996 31580 29156 19328 30977 11185 25468 2105 17046 13041 30713 18758 3103 6020 20727 19303 31407 6205 26572 16679 23281 25136 15373 22359 
25543 22724 19285 23994 3120 9225 13889 26626 30831 31051 14015 31483 17002 20967 19337 6663 8528 1117 15596 18634 13438 29607 24270 21798 30116 18633 13295 32106 5667 27306 22127 18118 19386 10274 18833 6147 20578 18516 6334 27760 6518 30014 26573 13088 2583 13454 22657 11858 9423 25271 26963 26417 116 25669 12658 2494 1104 365 7689 15626 12158 8169 
5312 19368 28567 20227 8069 12386 19087 23023 1420 23339 24537 21597 30100 16981 1234 21839 9581 5124 92 21544 2743 7139 10697 23558 4332 12565 28412 2386 28833 16495 1482 1430 3080 18148 19622 30094 29882 20544 7806 3457 32435 19994 7648 16337 1182 23299 15201 14802 16724 15876 31551 8920 25247 16968 15941 20884 14659 14101 4591 27552 10815 11265 
19407 9048 17744 15714 29743 2028 9399 1286 17400 7091 31292 804 14803 9410 28019 5011 2701 27582 12094 17210 28864 23790 26259 6600 8112 16276 23167 11173 23923 30590 32107 2088 2133 1240 15775 22538 2938 13892 16132 16410 1733 16685 25134 23603 11769 13399 15513 26219 8990 30907 26163 24206 20519 21651 16411 17867 977 9393 6313 17068 21966 16404 
20654 16716 5667 14781 26109 25540 19407 29887 1834 22246 1709 16022 5265 24366 2203 25529 12954 12789 2524 29299 20796 28392 7355 8174 19648 19897 29809 913 3016 21524 4937 7307 16015 10197 9218 21936 9074 20856 629 31621 29872 720 14200 22678 25454 13820 27649 27664 17406 14488 6031 28299 20320 30512 28101 6440 7689 7418 20312 25308 16356 23492 
16940 10251 5527 28715 13498 28761 20231 13838 4277 18109 13086 24898 24813 22487 5324 11911 3699 19075 6475 8379 30974 1710 13224 7758 28301 24168 31103 758 17998 19771 13574 31140 8895 16827 22604 12982 7955 9567 13763 19054 27607 5775 8701 29603 7893 2302 25267 15030 14905 16442 3851 29896 12018 22658 17690 12074 24155 20951 22696 13077 24347 20821 
24372 29084 2378 3268 15672 27614 3541 5227 6319 27520 7459 28452 21715 8027 24824 15542 31531 28785 19866 21086 13765 8998 3635 1455 16065 6317 4215 6557 26895 17600 29574 468 9848 11156 24084 28750 12003 31756 32711 24868 11473 6701 16864 6308 4907 11730 27422 18341 61 2464 15071 18967 20994 32317 16265 13278 20386 28093 27688 8161 3129 13149 
12633 30045 26330 13172 7526 6016 19412 10150 18354 13107 6963 31579 2904 7991 22666 19567 21775 627 2032 25644 2129 13452 23625 15477 16316 3255 6855 25923 27832 4811 22448 24150 6746 18075 28769 14628 22408 29058 26259 5910 3166 13887 221 22515 16081 21251 21626 3228 2706 18889 7245 507 20533 25318 290 30774 24467 15841 14135 23080 8557 25732 
5371 2321 1106 5171 1813 4236 12482 12669 1448 22210 18579 6641 28373 7390 13716 18483 27266 25537 19313 32335 15194 2294 16598 27212 8469 12264 17367 30981 12282 19282 11664 19252 16802 23288 6408 208 25342 12693 24924 20121 25500 22292 19225 4593 27173 23298 23785 22253 12843 11076 11122 1196 22305 17157 7291 9191 20651 17907 25936 29642 1049 23467 
18536 16642 3885 24433 22086 13080 12325 14373 13725 1021 28405 27762 14007 21990 27605 18249 13847 7001 30459 8334 4702 17800 21930 7697 14699 11487 22635 191 4294 26585 9883 21018 15679 1047 25381 1510 3538 21939 3729 25637 3534 20690 19006 20294 567 8568 24811 15002 22120 30113 14460 25863 15356 11661 4347 11264 495 26203 13534 2740 26369 4825 
32392 6534 27483 5787 22290 8638 25973 5962 4682 6526 24119 30783 19452 7159 30815 13392 10865 12764 26402 2538 10806 32279 14358 11617 22302 8892 29775 30083 5770 29243 23752 13939 26344 16601 17925 16053 14458 27233 22263 10885 17241 24598 12064 365 32441 21229 14328 21014 7534 19961 9614 16479 13232 21799 27250 14764 27163 23595 8915 17280 25081 10682 
15077 6223 11972 31482 21637 1677 2279 31543 12320 17931 7621 25559 7377 14211 8444 22672 13257 17010 747 21464 25332 17701 28786 14237 2778 19223 32760 22071 13251 32122 12211 1947 7710 532 6435 7889 12835 15436 32224 21416 4792 9349 4502 29864 22417 10666 9550 30024 12956 20746 6127 11361 1180 2151 12292 22243 9491 24137 17087 12999 24934 5272 
19518 17988 30524 16746 23822 10054 3623 29210 238 22300 29830 1178 725 1648 9130 11018 12854 21885 20279 19849 3458 25724 973 15947 30191 18527 6376 29675 20600 14274 31237 15875 14372 1055 2823 10235 9612 13121 11224 32286 12183 19707 8019 10483 18825 12569 22882 21194 8764 2455 30819 2965 2220 11537 28113 24313 31162 1403 6688 4261 15145 20242 
24552 29411 10221 17298 29254 2924 4517 1450 25216 31361 23398 24749 12519 22583 12730 12426 25858 31763 1000 1534 28904 25302 8822 23304 25582 9882 9965 27550 12418 15646 2268 1694 2391 28767 1055 27399 6595 17768 13409 1385 7525 17770 2528 8602 6922 23823 31600 25771 18129 17932 6595 8986 20366 12022 26599 26441 7021 5462 7440 15407 14296 1535 
13208 4174 154 14239 26948 17637 16964 13205 5321 15718 23503 258 29839 810 9092 1571 23220 20836 4889 5086 23124 7508 32541 20378 23048 28349 23958 28500 12204 7320 24552 31727 10598 16906 25592 3532 10211 32660 146 14235 11748 23690 12552 4977 2298 23750 25628 9754 30605 7837 29216 3248 28707 5394 15964 10348 28127 12874 1968 15549 26184 5696 
11387 13207 19533 5562 26043 31758 17541 11644 15733 14115 28347 13755 17495 9950 26793 27092 19100 5021 28164 6206 8240 7083 14777 3773 8212 8468 3191 5849 2821 18872 31853 5775 30040 17823 29269 10566 19497 20364 30641 17669 13748 7125 14932 16354 20739 10609 26917 18878 6346 10579 20000 11823 28047 28662 18845 29374 2829 9530 4821 9555 27867 9838 
14
28397
26185
20142
25990
16022
29067
6511
11759
8343
31257
21336
26553
5608
9813

Cod:

????

Titlul: Răspuns: 1120 Inundatie
Scris de: George Marcus din Februarie 28, 2013, 12:49:07

E corect.

Titlul: Răspuns: 1120 Inundatie
Scris de: FMI Razvan Birisan din Februarie 28, 2013, 16:52:47

Am luat 60 de puncte cu WA. Am rulat programul pe mai multe exemple,dar nu îmi dau seama ce greșesc. #-o

-Citesc numerele din fișier ca și cum ar fi un vector.
-Sortez vectorul cu Quick Sort.
-Fac sumele parțiale.
-Caut binar poziție pe care se află elementul >= eqk-1
-Afișez suma elementelor mai mici ca eqk + (eqk-1)*numărul de elemente rămase.

infoarena

infoarena - concursuri, probleme, evaluator, articole => Arhiva de probleme => Subiect creat de: Andrei Parvu din Aprilie 02, 2011, 21:27:37