Notice that the number of pieces you cut the cables needn't be precisely equal to k. Just >=k is OK. Set types as long long for variables used as sum of cables lengths For me, what worked was replacing "%i"'s with "%d"'s in scanf's. :) Try this: 1 5 1.00 answer: 0.20 Edited by author 02.04.2021 18:58 if you read data as: double x; cin>>x; a[i]=x*100; it doesn't work! Yes, i use binary-search and got Ac in 0.046 s. GOOD LUCK!!! In test #4 n=10000 and k=1. You can write this case apart. program Project1; {$APPTYPE CONSOLE} uses SysUtils; var i, j, m, n, maxa, x0, xn, x, p : integer; s : int64; l : real; a : array [1..10000] of integer; begin readLn(n, m); maxa := 0; s := 0; for i := 1 to n do begin readLn(l); a[i] := round(100*l); s := s + a[i]; if maxa < a[i] then maxa := a[i]; end; if s div m < 1 then writeLn('0.00') else begin if m = 1 then writeLn(maxa/100:10:2) else begin xn := s div m; x0 := 0; repeat p := 0; x := (xn+x0) div 3; for i := 1 to n do inc(p, a[i] div x); if p >= m then x0 := x else xn := x; until p = m; for i := xn downto x0 do begin p := 0; for j := 1 to n do inc(p, a[j] div i); if p = m then begin writeLn(i/100:0:2); halt; end; end; end; end; end. I use binary search to solve this problem and had trouble with input this input gots AC: double x; int j,t; fscanf(inf,"%lf",&x); L[i]=(int)(x*100.0+1e-9); but this got WA9 fscanf(inf,"%i.%i",&t,&j); L[i]=t*100+j; output in boyh programs was like this fprintf(outf,"%i.%0.2i\n",ANS/100,ANS%100); possible reasons: 1. input data hasn't 2 digits after decimal point(maybe it have none digits and no point at all) 2. chacker is floating-point written program with do errors and you have to do the same errors to AC. this code is wrong fscanf(inf,"%i.%i",&t,&j); L[i]=t*100+j; you must use scanf("%d", &x); instead of scanf("%i", &x); why ? try to input "09" %d reads it as 9, but %i reads some random thing #include <stdio.h> #include <math.h> int n, k; double * data; int ok (double z) { long s = 0; for (int i = 0; i < n; i++) s += floor (data[i] / z); return s >= k; } int main () { scanf ("%d%d", &n, &k); data = new double [n]; double l; for (int i = 0; i < n; i++) { scanf ("%lf", &l); data[i] = l; } if (!ok(0.01)) { printf ("0.00\n"); return 0; } double x = 0.01, y = 1e5, z; while (y - x >= 0.0001) { z = (x + y) / 2; if (ok(z)) x = z; else y = z; } printf ("%.2lf\n", z); return 0; } Wrong Answer. simple test: 5 10 3.34 2.34 7.54 1.87 0.03 your answer: 1.26 but 7.54/1.25 = 5 (1.26*6 = 7.56) and you have only 9 cables with length 1.26: 2 + 1 + 5 + 1 + 0 = 9 3.34 2.34 7.54 1.87 0.03 a have this mistake too :)) Wrong Answer. simple test: 5 10 3.34 2.34 7.54 1.87 0.03 your answer: 1.26 but 7.54/1.26 = 5 (1.26*6 = 7.56) and you have only 9 cables with length 1.26: 2 + 1 + 5 + 1 + 0 = 9 3.34 2.34 7.54 1.87 0.03 a have this mistake too :)) But this is not a correct test... "Cable lenth is at least 1 meter"... I read every line containing a number. And after that simply read all digits (without a point) and convert into integer 1 cm=1. 100km=100*10^3m=100*10^5cm=10^7. In that range I use binary search for finding the maximum possible length. Why WA at test 1? (Yeah, I sort the lens too) Here is a sample of code for converting: fgets(buf,150,INPUT_STREAM); tmp=0; j=0; while((buf[j]>='0'&&buf[j]<='9')||buf[j]=='.') { if(buf[j]!='.')tmp=tmp*10+buf[j]-'0'; j++; } sum+=tmp; Lens[i]=tmp; Do the lengths always have exactly two digits Edited by author 22.08.2006 13:44 In fact you are right, you are to use in this problem integers instead of float and binary search. If you have wa#1 probaly you didn't understand problem... When I removed sorting the lens and set the right bound to 100 km (not to the maximal length possible), I've got AC. Can anyone explain why? This two features were just for speed, they don't change the idea of binary search itself, I still used it. What could be wrong? my solution: {$N+} program cable_master; const max=10000; var a:array[1..max] of real; n,k,s:integer; best,f,r,m:extended; procedure readdata; var i:integer; begin readln(n,k); for i:=1 to n do begin readln(a[i]); if a[i]>r then r:=a[i]; end; end; function find:boolean; var i:integer; begin s:=0; for i:=1 to n do s:=s+trunc(a[i]/m); if s=k then find:=true else find:=false; end; procedure main; begin while r>=f do begin m:=(f+r)/2; if not find then begin if s>k then f:=f+0.001 else r:=m; if abs(r-f)<0.00001 then break; end else begin if m>best then best:=m; if f=r then break; f:=f+0.001; end; end; best:=trunc(best*100); best:=best/100; writeln(best:0:2); end; BEGIN readdata; main; END. give some texts please. > give some texts please. const max = 10000; var a :array[1..max] of longint; n,k :word; dau,cuoi,giua, kq :longint; ok :boolean; procedure nhap; var i :word; x :real; begin readln( n, k); for i := 1 to n do begin readln( x); a[i] := round( x * 100); end; end; procedure cut; var doan :longint; i :word; begin doan := 0; for i := 1 to n do begin doan := doan + a[i] div giua ; if doan >= k then break; end; ok := ( doan >= k ); if ok and ( giua > kq ) then kq := giua; end; procedure solve; begin dau := 1; cuoi := 10000000; kq := 0; repeat giua := ( dau + cuoi ) div 2; cut; if ok then dau := giua + 1 else cuoi := giua - 1; until dau > cuoi; end; procedure out; var x :real; begin x := kq; x := x / 100; writeln(x :0 :2); end; begin nhap; solve; out; end. uses math; const p=3.1415926535897; var a,r:integer; s,angl,cosa:real; begin readln (a,r); if (2*r<=a) then s:=p*r*r else if (sqrt(2)*a/2<r) then s:=a*a else begin cosa:=a/(2*r); angl:=2*arccos(cosa); angl:=p/2-angl; s:=((a/2)*sqrt(r*r-(a*a)/4))+angl*r*r/2; s := s * 4; end; writeln (s:0:3); end. My program is like yours. But if i use a[i] := trunc( x * 100),it's WA. And if i use a[i] := round( x * 100),it will be AC. Is there something different from the two ways in this problem? Isn't the input with exactly two digits after a decimal point? // My algorithm is about binary search #include <stdio.h> #include <stdlib.h> #define maxd 10005 float d[maxd],m=0.0; long k,n; int check(float w) { long l,s=0; for (l=0; l<n; l++) { if (s>=k) return 1; if (w>d[l]) return -1; s+=(long)(d[l]/w); } if (s>=k) return 1; return -1; } int sort_function(const void*a,const void*b) { if ((*(float*)a)>(*(float*)b)) return -1; if ((*(float*)a)==(*(float*)b)) return 0; return 1; } int main() { long l; float a,b,c,tmp; FILE* fname=stdin; FILE* fout=stdout; fscanf(fname,"%ld%ld",&n,&k); for (l=0; l<n; l++) fscanf(fname,"%f",&d[l]); qsort((void*)d,n,sizeof(d[0]),sort_function); c=(float)((long)((long)100*(long)(1+10000)/2))/100.0; for (a=1,b=10000; a<=b; c=(float)(a+b)/2.0 ) { if (check(c)==1) { if (c>m) m=c; tmp=a; a=c+0.01; a=(float)((long) (100.0*a))/100.0; if (a==tmp) break; } else { b=c-0.01; b=(float)((long) (100.0*b))/100.0; } } m=((long)(m*100))/100.0; fprintf(fout,"%.2f\n",m); fclose(fname); fclose(fout); return 0; } Here it is: #include<iostream.h> #include<stdio.h> int n, k; long x[10000]; void main() { double xx; int i, j; cin>>n>>k; for (i=0; i<n; i++) { cin>>xx; x[i] = xx*100; } long l, r, m, w; r = x[0]; for (i=1; i<n; i++) if (x[i]>r) r=x[i]; l = 1; w = 0; while ( l <= r ) { m = (l + r) / 2; j = 0; for (i=0; i<n; i++) j = j + (long)x[i]/m; if ( j == k ) { w = m; } if (j >= k) l = m + 1; else r = m - 1; } double ans = (double)w/100.0; printf("%.2f\n",ans); } I'm not good at C++. I like Dephi and C more than C++. But I had correct your program... Do you have E-mail? I'll send it to you Could you explain me why x[i] = (long)(x*100 + 0.1), how did you know 0.1?? Thanks :) We can try to this code. double n=2.01; long x; x=(long)(x*100); I was surprised that the result is 200? I can't understood it also. Then this code double n=2.01,t; long x; t=n*100; x=(long) t; You can find out that t=201.00000 but x was still 201. So I use (n*100+0.1) instead Then I use your program to got AC By the way . I like C more than C++ beacuse I don't kown C++ well If I made any mistake in this problem please forgive me.:-) Good luck. Well...... The first error is x[i] = xx*100; You should have replaced the line to x[i]=(long)(xx*100+0.1); Try the testcase 4 4 2.01 2.01 2.01 2.01 Your program output a wrong answer 2.00 :-) The second one Why do you think that the cable must be cut into exactly k pieces? So you must change
if ( j == k ) { w = m; } into if (j>=k && w>m) {w=m;} #include <iostream.h> int n,k; long m [10000],how [10000]; long GetNewLength () { long NewLength = 0; for (int i=1; i<=n; i++) if (m[i]/(how[i]+1) > NewLength) NewLength = m[i]/(how [i]+1); return NewLength; } int main () { long nowLength = 2147483648, nowN = 0; double length; cin >> n >> k; for (int i=1; i<=n; i++) { cin >> length; m [i] = int (length * 100); if (m[i] < nowLength) nowLength = m [i]; } while (nowN<k && nowLength != 0) { nowLength = GetNewLength (); if (!nowLength) continue; nowN = 0; for (i=1; i<=n; i++) { how [i] = m [i] / nowLength; nowN = nowN + how [i]; } } cout << nowLength/100 << "."; int tens = nowLength%100; if (tens < 10) cout << "0" << tens; else cout << tens; return 0; } What could be wrong with this code? Program Easy; Const Max=10006; Var i,n,k:Longint; a:Array[1..Max] Of Longint; x,y,z:Longint; u,q:Real; Function ok(l:Longint):Boolean; Var i,s:Longint; Begin s:=0; For i:=1 To n Do s:=s+a[i] Div l; ok:=s>=k; End; Begin { Assign(Input,'1184.in'); Reset(input);{} Read(n,k); y:=10000000; For i:=1 To n Do Begin Read(u); a[i]:=Round(u*100); End; x:=1; If Not ok(x) Then Begin Writeln('0.00'); Halt; End; While y-x>1 Do Begin z:=(y+x) Div 2; If ok(z) Then x:=z Else y:=z; End; While Not ok(z) Do z:=z-1; While Ok(z+1) Do z:=z+1; q:=z; q:=q/100; Writeln(q:0:2); End. Here is my programme: const max = 10000; var a :array[1..max] of longint; n,k :word; dau,cuoi,giua, kq :longint; ok :boolean; procedure nhap; var i :word; x :real; begin readln( n, k); for i := 1 to n do begin readln( x); a[i] := trunc( x * 100); end; end; procedure cut; var doan :longint; i :word; begin doan := 0; for i := 1 to n do begin doan := doan + a[i] div giua ; if doan >= k then break; end; ok := ( doan >= k ); if ok and ( giua > kq ) then kq := giua; end; procedure solve; begin dau := 1; cuoi := 10000000; kq := 0; repeat giua := ( dau + cuoi ) div 2; cut; if ok then dau := giua + 1 else cuoi := giua - 1; until dau > cuoi; end; procedure out; var x :real; begin x := kq; x := x / 100; writeln(x :0 :2); end; begin nhap; solve; out; end. use round instead of trunc please ;) |
|