This problem also can be solved using Dynamic Programming. #include <iostream> #include <string> #include <cstring> #include <cstdio> using namespace std; string *str = new string [50]; int N; int kaadanealgo(int a,int b) { int line[50]; int max_end_here=0; int max_so_far=0; for(int i=0;i<N;i++) { line[i] = 0; for(int j=a;j<=b;j++) { if(str[j][i]=='0') line[i]+=-1000000; else line[i]+=(str[j][i]-'0'); } } for(int
Category: Number Theory
12241
Theory: We know that, From 0-9, each digit occurs once From 0-99, each digit occurs 20 times (10x in position 1 and 10x in position 2) From 0-999, each digit occurs 300 times (100x in P1, 100x in P2, 100x in P3) If the range is from 0 to a power of 10 then occurrence
12542
#include <stdio.h> #include <string.h> #include <string> #include <iostream> #include <math.h> #include <vector> #define SZ 100005 using namespace std; int prim[SZ]; vector<int> v; void primgen() { v.push_back(2); prim[2]=0; for(int i=3;i<SZ;i+=2) { if(prim[i]==0) { v.push_back(i); for(int j=i*3;j<SZ;j+=i) prim[j]=1; } } //cout<<v.size()<<"\n"; } int main() { int mult[5]; int m,max_; string s; primgen(); while(cin>>s) { if(s=="0") break; memset(mult,0,sizeof(mult));
12517
Theory: from 0 to 99 there are 2*10^1=20 for each 0 to 9 digits. from 0 to 999 there are 3*10^2=300 for each 0 to 9 digits. so the foemulae is for 0 to n number of 9’s n*10^(n-1) for each 0 to 9 digits. And so, for upto 445 we can find total number
10780
#include <iostream> #include <cstring> #include <math.h> #include <stdio.h> #include <vector> #include <fstream> #define ull unsigned long long using namespace std; int factor[10001][1230]; int factorcount[10001][1230]; int prime[10001]; vector<int> v; ull _MAX; void primegenerator() { double p=sqrt(10001); v.push_back(2); for(int i=3;i<p;i+=2) { if(prime[i]==0) for(int j=i*i;j<10001;j+=i) prime[j]=1; } for(int i=3;i<10001;i+=2) { if(prime[i]==0) v.push_back(i); } } void factorize() { for(int
10394
#include <iostream> #include <string> #include <vector> #include <math.h> #define SZ 20000001 using namespace std; int prime[SZ]; vector<int> v; struct twin{ int x; int y; }twinPrime[108001]; void primegen() { double p = sqrt(SZ); for(int i=3;i<p;i+=2) { if(prime[i]==0) { for(int j=i*i;j<SZ;j+=i) prime[j]=1; } } v.push_back(2); int cnt=0; for(int i=3;i<SZ;i+=2) { if(prime[i]==0) { v.push_back(i); int t=v.size(); if(v[t-1]-v[t-2]==2) {
11347
#include <iostream> #include <cstring> #include <math.h> #include <stdio.h> #include <vector> #define ull unsigned long long #define max(a,b) a>=b?a:b using namespace std; int ans[200]; int prime[1001]; vector<int> v; ull _MAX; void primegenerator() { double p=sqrt(1001); v.push_back(2); for(int i=3;i<p;i+=2) { if(prime[i]==0) for(int j=i*2;j<1001;j+=i) prime[j]=1; } for(int i=3;i<1001;i+=2) { if(prime[i]==0) v.push_back(i); } } int main() { string s;
11415
#include <iostream> #include <math.h> #include <vector> #define ull unsigned long long #define SIZE 2703664 using namespace std; int prime[1700];//3200 ull factor[SIZE]; int arr[10000001]; vector<int> v; void primeGenerator() { double p = sqrt(1700); for(int i=3;i<p;i+=2) { if(prime[i]==0) { for(int j=i+i;j<1700;j+=i) prime[j]=1; } } v.push_back(2); for(int i=3;i<1700;i+=2) { if(prime[i]==0) v.push_back(i); } } void countfactor() { int tmp;
10856
#include <iostream> #include <string> #include <stdio.h> #include <math.h> #include <vector> #include <stdlib.h> #define SIZE 2800001 #define ull unsigned long long using namespace std; int prime[1700]; ull arr [SIZE];//[10000001+5]; vector<int> v; void primeGenerator() { double p = sqrt(1700); for(int i=3;i<p;i+=2) { for(int j=i+i;j<1700;j+=i) { prime[j]=1; } } v.push_back(2); for(int i=3;i<1700;i++) { if(prime[i]==0 && i%2!=0) { v.push_back(i);
10139
#include <iostream> #include <math.h> #include <vector> #include <map> #include <sstream> #include <fstream> #define SIZE 46500 #define lld long long using namespace std; // sqrt of 2^31 is ~46400 vector<int> v; int prime[SIZE]; void PrimeGenerate() { double p = sqrt(SIZE)+4; for(int i=3;i<p;i+=2) { if(prime[i]==0) { for(int j=i+i;j<SIZE;j+=i) prime[j]=1; } } v.clear(); v.push_back(2); for(int j=3;j<SIZE;j++) { if(prime[j]==0