Contest Link: Codejam Qualification Round 2015
Problem A: See the editorial of the problem. Code Jam Editorial
Solution: The friends invited should have shyness 0 for optimal.
The solution is shown in the editorial. But We can apply binary search on the ans.
If we can make things right with k people, then its possible for also k+1, k+2…
So, applying binary search we can easily solve this problem.
/*
*************************
Id : Matrix.code
Task: A. Standing Ovation
Date: 2016-01-17
**************************
*/
#include <bits/stdc++.h>
using namespace std;
/*------- Constants---- */
#define Long long long
#define ull unsigned long long
#define mod 1000000007
#define MEMSET_INF 63
#define MEM_VAL 1061109567
#define forn(i,n) for( int i=0 ; i < n ; i++ )
#define mp(i,j) make_pair(i,j)
#define lop(i,a,b) for( int i = (a) ; i < (b) ; i++)
#define pb(a) push_back((a))
#define SZ(a) (int) a.size()
#define all(x) (x).begin(),(x).end()
#define gc getchar_unlocked
#define PI acos(-1.0)
#define INF 1<<29
#define EPS 1e-9
#define Fr first
#define Sc second
#define Sz size()
#define lc ((n)<<1)
#define rc ((n)<<1|1)
#define db(x) cout << #x << " -> " << x << endl;
#define Di(n) int n;si(n)
#define Dii(a,b) int a,b;si(a);si(b)
#define Diii(a,b,c) int a,b,c;si(a);si(b);si(c)
#define Si(n) si(n)
#define Sii(a,b) si(a);si(b)
#define Siii(a,b,c) si(a);si(b);si(c)
#define min(a,b) ((a)>(b) ? (b) : (a) )
#define max(a,b) ((a)>(b) ? (a):(b))
/*---- short Cuts ------- */
#define ms(ara_name,value) memset(ara_name,value,sizeof(ara_name))
typedef pair<int, int> ii;
typedef vector<int > vi ;
typedef vector<Long> vl;
/*------ template functions ------ */
#ifndef getchar_unlocked
#define getchar_unlocked getchar
#endif
template<class T> inline void si(T &x){register int c = gc();x = 0;int neg = 0;for(;((c<48 | c>57) && c != '-');c = gc());
if(c=='-') {neg=1;c=gc();}for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}if(neg) x=-x;}
Long bigmod(Long p,Long e,Long M){Long ret = 1;for(; e > 0; e >>= 1){if(e & 1) ret = (ret * p) % M;p = (p * p) % M;} return ret;}
Long gcd(Long a,Long b){if(b==0)return a;return gcd(b,a%b);}
Long modinverse(Long a,Long M){return bigmod(a,M-2,M);}
void io(){freopen("/Users/MyMac/Desktop/in.txt","r",stdin);}
/*************************** END OF TEMPLATE ****************************/
const int N = 1005;
char str[N];
int v[N];
int tmp[N];
bool can(int mid,int n)
{
for(int i = 0;i <= n;i ++ ) tmp[i] = v[i];
tmp[0] += mid;
Long sum = tmp[0];
for(int j=1;j<=n;j++) {
if(tmp[j] ==0 ) continue;
if(sum >= j) sum += tmp[j];
else return 0;
}
return 1;
}
int main()
{
/*freopen("A-large-practice.in","r",stdin);
freopen("out.txt","w",stdout);*/
Di(t);
int cs = 0;
while(t--) {
Di(n);
scanf("%s",str);
for(int i= 0;i<=n;i++) v[i] = str[i] -'0';
int low = 0, high = n * (n+1)/2 , mid, ans=-1;
while(low <= high)
{
mid = (low+high)/2;
if(can(mid,n)) {
ans = mid;
high = mid-1;
}else low = mid+1;
}
printf("Case #%d: %d\n",++cs,ans);
ms(v,0);
}
return 0;
}
Problem B:
The editorial is well discussed.No need for explain.
Solution:
/*
*************************
Id : Matrix.code
Task: B. Infinite House of Pancakes
Date: 2016-01-17
**************************
*/
#include <bits/stdc++.h>
using namespace std;
/*------- Constants---- */
#define Long long long
#define ull unsigned long long
#define mod 1000000007
#define MEMSET_INF 63
#define MEM_VAL 1061109567
#define forn(i,n) for( int i=0 ; i < n ; i++ )
#define mp(i,j) make_pair(i,j)
#define lop(i,a,b) for( int i = (a) ; i < (b) ; i++)
#define pb(a) push_back((a))
#define SZ(a) (int) a.size()
#define all(x) (x).begin(),(x).end()
#define gc getchar_unlocked
#define PI acos(-1.0)
#define INF 1<<29
#define EPS 1e-9
#define Fr first
#define Sc second
#define Sz size()
#define lc ((n)<<1)
#define rc ((n)<<1|1)
#define db(x) cout << #x << " -> " << x << endl;
#define Di(n) int n;si(n)
#define Dii(a,b) int a,b;si(a);si(b)
#define Diii(a,b,c) int a,b,c;si(a);si(b);si(c)
#define Si(n) si(n)
#define Sii(a,b) si(a);si(b)
#define Siii(a,b,c) si(a);si(b);si(c)
#define min(a,b) ((a)>(b) ? (b) : (a) )
#define max(a,b) ((a)>(b) ? (a):(b))
/*---- short Cuts ------- */
#define ms(ara_name,value) memset(ara_name,value,sizeof(ara_name))
typedef pair<int, int> ii;
typedef vector<int > vi ;
typedef vector<Long> vl;
/*------ template functions ------ */
#ifndef getchar_unlocked
#define getchar_unlocked getchar
#endif
template<class T> inline void si(T &x){register int c = gc();x = 0;int neg = 0;for(;((c<48 | c>57) && c != '-');c = gc());
if(c=='-') {neg=1;c=gc();}for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}if(neg) x=-x;}
Long bigmod(Long p,Long e,Long M){Long ret = 1;for(; e > 0; e >>= 1){if(e & 1) ret = (ret * p) % M;p = (p * p) % M;} return ret;}
Long gcd(Long a,Long b){if(b==0)return a;return gcd(b,a%b);}
Long modinverse(Long a,Long M){return bigmod(a,M-2,M);}
void io(){freopen("/Users/MyMac/Desktop/in.txt","r",stdin);}
/*************************** END OF TEMPLATE ****************************/
const int N = 2005;
int n;
int a[N];
int main()
{
/*
freopen("B-large-practice.in","r",stdin);
freopen("out.txt","w",stdout); */
Di(t);
int cs = 0;
while(t--) {
Si(n);
int iM = 0;
for(int i =0 ;i < n;i ++ ) {
Si(a[i]);
iM= max(iM, a[i]);
}
int ans = iM;
for(int i=1;i <= iM; i++ ) {
int iMin = i;
for(int j=0;j<n;j++) {
iMin += ceil(1.*a[j] / i) -1;
}
ans = min(ans,iMin) ;
}
printf("Case #%d: %d\n", ++cs , ans);
}
return 0;
}
Problem C:
Editorial: Problem C
My code:
/*
*************************
Id : Matrix.code
Task: Dijkstra
Date: 2016-01-17
**************************
*/
#include <bits/stdc++.h>
using namespace std;
/*------- Constants---- */
#define Long long long
#define ull unsigned long long
#define mod 1000000007
#define MEMSET_INF 63
#define MEM_VAL 1061109567
#define forn(i,n) for( int i=0 ; i < n ; i++ )
#define mp(i,j) make_pair(i,j)
#define lop(i,a,b) for( int i = (a) ; i < (b) ; i++)
#define pb(a) push_back((a))
#define SZ(a) (int) a.size()
#define all(x) (x).begin(),(x).end()
#define gc getchar_unlocked
#define PI acos(-1.0)
#define INF 1<<29
#define EPS 1e-9
#define Fr first
#define Sc second
#define Sz size()
#define lc ((n)<<1)
#define rc ((n)<<1|1)
#define db(x) cout << #x << " -> " << x << endl;
#define Di(n) int n;si(n)
#define Dii(a,b) int a,b;si(a);si(b)
#define Diii(a,b,c) int a,b,c;si(a);si(b);si(c)
#define Si(n) si(n)
#define Sii(a,b) si(a);si(b)
#define Siii(a,b,c) si(a);si(b);si(c)
#define min(a,b) ((a)>(b) ? (b) : (a) )
#define max(a,b) ((a)>(b) ? (a):(b))
/*---- short Cuts ------- */
#define ms(ara_name,value) memset(ara_name,value,sizeof(ara_name))
typedef pair<int, int> ii;
typedef vector<int > vi ;
typedef vector<Long> vl;
/*------ template functions ------ */
#ifndef getchar_unlocked
#define getchar_unlocked getchar
#endif
template<class T> inline void si(T &x){register int c = gc();x = 0;int neg = 0;for(;((c<48 | c>57) && c != '-');c = gc());
if(c=='-') {neg=1;c=gc();}for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}if(neg) x=-x;}
Long bigmod(Long p,Long e,Long M){Long ret = 1;for(; e > 0; e >>= 1){if(e & 1) ret = (ret * p) % M;p = (p * p) % M;} return ret;}
Long gcd(Long a,Long b){if(b==0)return a;return gcd(b,a%b);}
Long modinverse(Long a,Long M){return bigmod(a,M-2,M);}
void io(){freopen("/Users/MyMac/Desktop/in.txt","r",stdin);}
/*************************** END OF TEMPLATE ****************************/
const int N = 1e5+5;
enum {I=2,J=3,K=4};
int Tr[][5] =
{
{0,0,0,0,0},
{0,1,I,J,K},
{0,I,-1,K,-J},
{0,J,-K,-1,I},
{0,K,J,-I,-1}
};
int Map[150];
string str, s;
int ar[N];
int prefix[N], suffix[N];
int mul(int a,int b)
{
int cnt = 0;
if(a<0) cnt++ , a=-a;
if(b<0) cnt ++ , b=-b;
return (cnt&1) ? -Tr[a][b] : Tr[a][b];
}
int Mod(Long b,Long p)
{
if(p==0)return 1;
if(p&1) return mul(b,Mod(b,p-1));
int k = Mod(b,p/2);
return mul(k,k);
}
int main()
{
/*freopen("c-large-practice.in","r",stdin);
freopen("out.txt","w",stdout); */
Map['i'] = 2,Map['j'] = 3,Map['k']=4;
Di(t);
int cs = 0;
while(t--) {
Long l,x;
Sii(l,x);
cin >> str;
int Sum = 1;
forn(i,SZ(str)) {
Sum = mul(Sum,Map[str[i]]);
}
int k = Mod(Sum,x);
bool flag = 0;
if(k==-1){
forn(i,min(8,x)) {
s += str;
}
int cnt = 0;
int Sum = 1;
for(int i= 0;i < s.length(); i ++ ) {
Sum = mul(Sum, Map[s[i]]);
if(cnt==0){
if(Sum== I) cnt =1,Sum=1;
}
else if(cnt==1){
if(Sum == J ) {
cnt = 2;
break;
}
}
}
if(cnt==2) flag=1;
}
printf("Case #%d: %s\n", ++cs, flag? "YES" : "NO");
s.clear();
}
return 0;
}
Code for Fun 