Codeforces Round #264(div 2)

I had class so had to do the virtual

Problem A:

                pretty simple . just convert the dollers + cents combination into cents and do 100
               i don't understand how few high rated coders get 1 wrong try on this problem :/
             will take 4-5 minutes
           
            #include <bits/stdc++.h>
#define FOR(i,a,b) for(int i=(int)a;i<=(int)b;i++)
using namespace std ;
int main(int argc, char **argv){
ios::sync_with_stdio(false) ;
int n ,s ,maxi = -1 ,x,y;
cin>>n>>s ;
s *=100 ;
FOR(i,0,n-1){
cin>>x>>y ;
int cost =100*x+y ;
if(cost<=s){
int change = s-cost ;
maxi = max(maxi,change%100) ;
}

}

cout<<maxi<<"\n" ;
return 0;
}

Problem B:

             Greedy + implementation , nice problem I don't the concrete proof that why Greedy will work but it's almost intuitive
10-15 minutes to code

#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i=(int)a;i<=(int)b;i++)
using namespace std ;
#define MAXN 100000+7
int main(int argc, char **argv){
ios::sync_with_stdio(false) ;
int n ,h[MAXN] ;
cin>>n ;
FOR(i,0,n-1){
cin>>h[i] ;
}
int cur = 0 ,energy = 0 ,res =  0 ;
FOR(i,0,n-1){
if(cur+energy>h[i]){
energy  =(cur-h[i]+energy) ;
}

else{
res +=(h[i]-cur-energy) ;
energy = 0 ;
}
cur = h[i] ;
}
cout<<res<<"\n" ;
return 0;
}


 

 Problem D:

   At long last i solve a problem D without looking the tutorial B|
  the problem is super nice . At first you may get into the trap thinking this is a standard lcs problem . But take paper and pencil and u will see this is actually a lis problem i wonder how brilliant the person's mind is who come up with the problem

The problem with standard lcs problem is that if there exists two lcs of same length which one should i keep for the next string  the give away is that the max value in the string is with in K and it is a permutation of n :)


#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i=(int)a;i<=(int)b;i++)
using namespace std ;
#define MAXN 1000+7
vector<int>pos[MAXN] ;
int dp[MAXN],n,k ;
int call(int u){

if(dp[u]!=-1) return dp[u] ;
int ret = 0 ;

FOR(i,1,n){
bool ok = 1 ;
FOR(j,0,k-1){
//cout<<pos[i][j]<<" "<<pos[u][j]<<"\n" ;
if(pos[i][j] <= pos[u][j]) ok = 0 ;
}

if(ok){
//cout<<"from "<<u<<" to "<<i<<"\n" ;
ret = max(ret,call(i)) ;
}
}

dp[u] = ret+1 ;
return dp[u] ;
}

int main(int argc, char **argv){
ios::sync_with_stdio(false) ;
int val ;
cin>>n>>k ;
FOR(i,0,k-1){
FOR(j,0,n-1){
cin>>val ;
pos[val].push_back(j) ;
}
}
/*
FOR(i,1,n){
FOR(j,0,k-1) cout<<pos[i][j]<<" " ;
cout<<"\n" ;
}
* */
memset(dp,-1,sizeof(dp)) ;
int maxi = 1 ;

FOR(i,1,n){
int Len = call(i) ;
maxi = max(Len,maxi) ;
}

cout<<maxi<<"\n" ;

return 0;
}


 

Codeforces Round #259 (Div. 2)

It was a mixed round for me . I manged to solved problem A without any hiccup . But for problem B i accepted the greedy solution that came into my head . not realising it contains a serious bug which a got at the end of the contest . Unfortunately It passed the pretests and no one hacked me :'( . As usual it failed the system test .

On the bright side I manged to solve problem C . which was easy . You just need to get the maths right . Power function may take O(lgn) time.

Problem A:
#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i=(int)a;i<=(int)b;i++)
using namespace std ; 
int main(int argc, char **argv){
ios::sync_with_stdio(false) ;
int n ;
cin>>n ;
int d = 1 ;
while(d<=n){
int s = n-d ;
FOR(i,0,(s/2)-1) cout<<"*" ;
FOR(i,0,d-1) cout<<"D" ;
FOR(i,0,(s/2)-1) cout<<"*" ;
cout<<"\n" ;
d+=2 ;
}
d-=4 ;
while(d>0){
int s = n-d ;
FOR(i,0,(s/2)-1) cout<<"*" ;
FOR(i,0,d-1) cout<<"D" ;
FOR(i,0,(s/2)-1) cout<<"*" ;
cout<<"\n" ;
d-=2 ;
}

return 0;
}

Problem B :
#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i=(int)a;i<=(int)b;i++)
using namespace std ;
#define MAXN 1000000
int a[MAXN] ; 
int main(int argc, char **argv){
ios::sync_with_stdio(false) ;
int n ;
int res ;

cin>>n ;
FOR(i,0,n-1){
cin>>a[i] ;
}
int seq = 0 ;
//cout<<idx<<"\n" ;
FOR(i,1,n-1){
if(a[i]<a[i-1]){
seq++ ;
res = n-i ;
}
}

if(seq==0) cout<<"0\n" ;
else if(seq==1) {
if(a[n-1]>a[0]) {
cout<<"-1\n" ;
return 0 ;
}
cout<<res<<"\n" ;
}
else cout<<"-1\n" ;

return 0;
}


Problem C: 
#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i=(int)a;i<=(int)b;i++)
using namespace std ; 
int main(int argc, char **argv){
ios::sync_with_stdio(false) ;
double n,m ;
cin>>n>>m ;
double res = n ;
for(int i=n-1;i>0;i--){
res -= pow((i/n),m) ;
}

printf("%.13lf",res) ;
return 0;
}