3 5 -> 4 5 3 -> 5 1 5 -> 0 5 1 -> 1 10 10 -> 18 99999 99999 -> 199996 2147483647 2147483647 -> 4294967292 I hope it helps! answer = min(2*(n-1), 2*m-1); //don't forget about 32-bit signed integer overflow import sys n,m=map(int,input().split()) n1=n m1=m j=0 ans=0 if n1==1 or m1 ==1: print(0) sys.exit() while n1>0 and m1>0: if ans%2==0 and j!=0: if m1>0: m1-=1 ans+=1 j+=1 else: print(ans) sys.exit() elif ans%2==1 and j!=0: if n1>0: n1-=1 ans+=1 j+=1 else: n1-=1 m1-=1 ans+=1 j+=1 print(ans) I print 2 * (n - 1) when n <= m and 2 * (m - 1) + 1 when n > m but got WA on test 13. What's wrong with my solution? Oh, I forgot to delete my check for m = 1 (in this case I output 1). This test seem to be 1 1 0 Edited by author 03.10.2018 17:42 #include <stdio.h> int main() { int N, M; scanf("%d%d",&N,&M); long int res; if (N <= M) res = 2 * (N - 1); else res= 2 * (M - 1)+1; printf("\n%d",res); return 0; } Can't solve this promlem myself. I run your code online on some tests, it seemed ok. Check, maybe you go out of range in res? (know nothing about C) think about : F(N,M) = F(N-? , M- ? ) and give the initial values. The number of steps is too big. By doing a single recursive step you reduce the size of the original problem to (N - 2, M - 2). If we were to reduce the size to (N / 2, M / 2) (notice that we changed minus sign to division), then we could solve it recursively. Instead you should think of this problem as a whole. There are N rows and M columns. So some part of the robots path is by row and some part is by column: path = row|column|row|column|row|column... And we are counting the number of signs | in the path. As we see, each column is surrounded by sign | from both of its sides: "|column|". The first rough estimate that comes to mind after this observation is that probably the robot does 2 * (number of columns) turns. And by thinking of different specific cases of (N, M) we can turn this estimate into a true measure of the number of turns of the robot in the general case. Edited by author 30.10.2016 17:25 #include<stdio.h> #include<string.h> int f(int n,int m) { if(n==1||m==1) return 0; if(n==2&&m>1) return 2; if(n==3&&m==2) return 3; if(m>2&&n>2) return f(n-2,m-2)+4; } int main() { int n,m; scanf("%d %d",&n,&m); printf("%d",f(n,m)); fflush(stdin); getchar(); return 0; } Input "N=1 M=1" doesn't give you zero. Test 12 is overflow case. Be careful with data type. It is so strange! If I use int for N and M, I get WA in test 12. If I use long, it is OK. But 2^31 - 1 (the max value of N, M) is normal for int. So I think the test 12 uses numbers larger than 2^31 - 1. hi, in the acceptable answer the answer of 5 4 is 7 but you can easily understand that the real answer is 6(you can test it by drawing a simple 5 4 table). here is a sample answer: #include <iostream> using namespace std; int main() { int unsigned long long N , M , turn = 0; cin >> N >> M;
while( N > 2 && M > 2){ turn += 4; N -= 2; M -= 2; } if (N == 2 && M > 1 || M == 2 && N > 1) turn += 2;
if (M == 1 && N > 1) turn += 1; cout << turn << endl;
system ("PAUSE"); return 0 ;
} Nope...for 5 4 , answer is 7. For 4 5, answer is 6. Edited by author 05.07.2015 11:06 Edited by author 05.07.2015 11:06 System.out.println((Math.min(N - 1L, M - 1L) << 1) + (N > M ? 1 : 0)); I got WA 10, where is wrong? /////////////////////// #include <iostream> using namespace std; int main() { int N,M,sum,counter,mul; counter=0; cin>>N>>M; sum=M; mul=N*M; while(sum!=mul) { N--; sum+=N; counter++; if(sum==mul) break; M--; sum+=M; counter++; } cout<<counter<<endl; } input 2 1 output 0 this is correct. however this solution get WA. AC program writes 1, which is wrong in fact. yea, U're Right yea, U're Right It depends... Think more... In fact. It is 1. Think... #include<cstdio> #include<cstring> #include<cassert> #include<vector> #include<list> #include<queue> #include<map> #include<set> #include<deque> #include<stack> #include<bitset> #include<algorithm> #include<functional> #include<numeric> #include<utility> #include<sstream> #include<iostream> #include<iomanip> #include<cmath> #include<cstdlib> #include<ctime> #include<fstream> #include<typeinfo> #include<locale> #include<iterator> #include<valarray> #include<complex> using namespace std; int main() { int n,m; while(cin>>n>>m){ int sum = 0,flag = 0,count = -1,x=n*m; n--; if(n==0 || m==0){ cout<<"0"<<endl; continue; } while(sum < x){ if(flag==0){ sum += m; flag = 1; m--; } else if(flag==1){ sum += n; flag = 0; n--; } count++; } cout<<count<<endl; } return 0; } here is my code, it has got verdict WA in test case 10.... program spiral; var n,m,r:real; begin readln(n,m); if m>=n then begin if n=1.0 then r:=0.0 else if n=2.0 then r:=2.0 else if frac(n/2)<>0 then r:=4.0*trunc(n/2) else r:=2.0*(n-1); end else begin if m=1.0 then r:=1.0 else if m=2.0 then r:=3.0 else if frac(m/2)<>0 then r:=4.0*trunc(m/2)+1.0 else r:=2.0*m-1.0; end; writeln(r:0:0); end. const{only 49K) maxn=11; var a:array[0..maxn]of 0..9; n,m:longint; i,j,s:integer; ok:boolean; begin fillchar(a,sizeof(a),0); readln(n,m); ok:=false; if n>m then begin n:=m;ok:=true;end; n:=n-1; i:=maxn+1; while n<>0 do begin i:=i-1; a[i]:=n mod 10; n:=n div 10; end; if ok then j:=1 else j:=0; for i:=maxn downto 1 do begin s:=a[i]*2+j; a[i]:=s mod 10; j:=s div 10; end; i:=0; while (a[i]=0)and(i<>maxn) do i:=i+1; for j:=i to maxn do write(a[j]); end. var m,n,y:real;b:boolean; begin readln(m,n); b:=false; if m>n then begin y:=m;m:=n;n:=y;b:=true end; if m=0 then begin writeln(0);halt;end; if frac(m/2)<>0 then y:=int(m/2)*4 else y:=int((m-1)/2)*4+2; if b then writeln(y+1:0:0) else writeln(y:0:0); end. #include <stdio.h> #include <math.h> int main(void) { unsigned int n, m, answer; scanf("%u %u", &n, &m); if (m >= n) answer = 2 * (n - 1); else answer = 2 * (m - 1) + 1; printf("%u\n", answer);
return 0; } Ok, same solution after some thinking. And it is working, just remember about huge numbers you are getting in the input #include <iostream> using namespace std; int main() { long long nN, nM; cin >> nN >> nM; if(nM >= nN) cout << 2*(nN-1); else cout << 2*(nM-1)+1; return 0; } Edited by author 12.11.2008 20:43 Edited by author 12.11.2008 20:44 Shortest sol (C language): main() { unsigned n, m; scanf("%u%u", &n, &m); printf("%u", n <= m ? 2 * n - 2 : 2 * m - 1); } #include <iostream> using namespace std; long long n,m; int main() { cin>>n>>m; if (m>=n) cout<<2*(n-1); else cout<<2*(m-1)+1; } My Solution program Ural1224; var n,m:int64; begin readln(n,m); if n<=m then writeln(n shl 1-2) else writeln(m shl 1-1); end. import java.io.*; import java.util.*; public class www { public static void main(String[] args) throws IOException{ PrintWriter out = new PrintWriter(System.out); Scanner in = new Scanner(System.in); long n = in.nextInt(); long m = in.nextInt(); out.println(m>=n ? 2*n-2 : 2*m-1); in.close(); out.close(); } } Edited by author 27.08.2013 23:07 ee munaqa bo'mag'ur masalaga bosh qotirish shartmi? I have correct answer on PC and wrong - here?Why? What is it Use these tests: 4 4 -> 6 5 4 -> 7 4 5 -> 6 1 9 -> 0 9 1 -> 1 I think that you miscalculated the answer at the second example.It's 8,isn't it ? Use these tests: 5 4 -> 8 I’ve AC, but I still have a question! My first program used “unsigned long” type, and didn’t pass Test 12 Then I changed all types to “unsigned long long” , and program was AC. So, my question is why my first program failed on Test12? As you know n,m<=2^31-1;So, the biggest result is 0xFFFFFFFD! This result can be represented by unsigned long! So, I didn’t announce my program, because it is bad style. I’m sure that those programmers who solved this issue can understand my question…. Best Wishes, Veniamin. Each of n and m is <= 2^31-1. Yes, they are unsigned long. But max unsigned long + 1 is? Overflow, of course !! Your solution doesn't print n or m exactly but you have to calculate either 2*m or 2*n, aren't you? Thanks.I also meet this question. #include <iostream> using namespace std; int main() { unsigned long long n,m; cin>>n>>m; if(m>=n) cout<<2*(n-1)<<endl; if(n>m) cout <<2*(m-1)+1<<endl; return 0; } Orz...My solution is so complex... You can even simpler)) #include <iostream> using namespace std; int main() { unsigned long long iN, iM; cin >> iN >> iM; cout << min(2 * (iN - 1), 2 * (iM - 1) + 1); return 0; } You don't really need unsigned long long. Got AC with unsigned int. #include<stdio.h> int main(void){ int n,m; unsigned int k; scanf("%d %d",&n,&m); k=0; while(n>2 && m>2){ k=k+4; n-=2; m-=2; } if(n==2 && m>=2) k=k+2; else if(m==2 && n>2) k=k+3; else if(m==1 && n>1) k++; printf("%d",k); return 0; } |
|