Timus Solutions

Here it goes

Advertisements

1510 : Order

Problem Link

Huge chance to get TLE on 21 & 31 , i got 5times 😥

Morning shock

#Solution

#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <queue>
#include <map>
#include <stack>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <cstdio>
#include <iomanip>
using namespace std;
#include<stdint.h>
#define ll long long
map<ll,ll>in;
#define uu first
#define vv second
#include <iomanip>
int64_t x,mx=-1,ans=0;
int main() {
int t;
ios_base::sync_with_stdio(0);

scanf(“%d”,&t);

for(int i=0;i<t;i++)

{
scanf(“%I64d”,&x);
++in[x];
}
for(map<ll,ll>::iterator it=in.begin();it!=in.end();it++)
{
if((*it).vv>mx)
{

mx=it->second;
ans=it->first;
}
}

printf(“%I64d\n”,ans);
return 0;
}

11244 – Counting Stars

Problem Link

#Solution

#include<cstdio>
using namespace std;
int dx[]={-1,1,0,0,-1,1,-1,1};
int dy[]={0,-1,1,-1,-1,1,1,0};
int main()
{
int n,m,c,tx,ty,res;
while(scanf(“%d %d”,&n,&m)==2 && n &&m)
{

int i,j,k;
res=0;
char vis[105][105]={0};
for(i=0;i<n;i++)
scanf(“%s”,vis[i]);
for(i=0;i<n;i++)
{
for(j=0;j<m;j++)
{c=1;
if(vis[i][j]==’*’)
{

for(c=0,k=0;k<8;k++)
{
tx=i+dx[k];
ty=j+dy[k];
if(tx>=0 &&ty>=0 &&tx<n &&ty<m &&vis[tx][ty]==’*’)
c++;

}

}
if(c==0) res++;

}
}
printf(“%d\n”,res);
}

return 0;
}

752B. Santa Claus and Keyboard Check

 

Problem Link

#Solution

 

#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define mp make_pair

vector<pair<char,char>>res;
#define pb push_back
map<char,int>chk;
int main()
{

    string a,b;
    cin>>a>>b;
    if(a==b)
    {cout<<0<<endl;
        return 0;
    }
for(int i=0;i<a.size();i++)
{
    if(a[i]!=b[i])
    {
        res.pb(mp(a[i],b[i]));
        char c=b[i];
        if(chk[c]||chk[a[i]])

        {
            cout<<-1;

            return 0;
        }
        chk[c]=chk[a[i]]=1;
        for(int j=0;j<a.size();j++)
        {
            if(b[j]==a[i]) b[j]=c;
            else if(b[j]==c)  b[j]=a[i];//Replacing letters

        }
    }

}
    if(a!=b)
    {
        cout<<-1;
        return 0;
    }
    cout<<res.size()<<endl;
for(int i=0;i<res.size();i++)
    cout<<res[i].first<<" "<<res[i].second<<endl;
}

Coinage

Problem Link

 

#Solution – Idea :Editorial

 

#include <bits/stdc++.h>
using namespace std;

int f[1005];

int main(void) {
int t;
cin >> t;
while (t–) {
int a, b, c, d, A, B, C, D, N;
long long ans = 0;

cin >> N >> A >> B >> C >> D;

for (int i = 0; i <= N; i++)
f[i] = 0;

for (i = 0; i <= i; i++)
for (j = 0; j <= j && j + i * 2 <= N; j++)
f[j + i * 2]++;

for (i = 0; i <= i; i++)
for (j = 0; j <= j && i * 5 + j * 10 <= (N); j++)
ans += f[N – i * 5 – j * 10];

cout << ans << endl;
}
return 0;
}

10653 – Bombs! NO they are Mines!!

Problem Link

#Solution

#include<bits/stdc++.h>
using namespace std;
int r,c;
#define cln(a) memset(a,0,sizeof a)
int dx[]={+1,-1,0,0};
int dy[]={0,0,-1,+1};
#define uu first
#define vv second
#define pii pair<int,int>
#define sz 10000
int vis[sz][sz],cost[sz][sz],d[sz][sz];
queue<pii>q;
void bfs(int a,int b)
{
int vx,vy;
vis[a][b]=1;
cost[a][b]=0;
q.push(pii(a,b));
while(!q.empty())
{
pii u=q.front();
q.pop();

for(int i=0;i<4;i++)
{
vx=u.uu+dx[i];
vy=u.vv+dy[i];
if(vx>=0 &&vx<r &&(vy>=0 &&vy<c) &&d[vx][vy]==0)
{

if(vis[vx][vy]==0)
{

vis[vx][vy]=1;
d[vx][vy]=1;
cost[vx][vy]=cost[u.uu][u.vv]+1;
q.push(make_pair(vx,vy));
}
}

}
}
}

int main()
{

while(scanf(“%d %d”,&r,&c) &&r &&c)
{
cln(cost);cln(vis);
cln(d);
int x,r,mine,data;
cin>>r;
for(int i=0;i<r;i++)
{
cin>>mine>>data;
while(data–)
{
cin>>x;
d[mine][x]=1;
}

}
int sx,sy,endx,endy;
cin>>sx>>sy>>endx>>endy;
bfs(sx,sy);
printf(“%d\n”,cost[endx][endy]);
}
return 0;
}

784 – Maze Exploration

Problem Link

#Solution

#include
#include
using namespace std;
char in[100][100];
void dfs(int a,int b)
{
if(in[a][b]==’X’ || in[a][b]==’#’)
return ;
in[a][b]=’#’;
dfs(a+1,b);
dfs(a-1,b);
dfs(a,b+1);
dfs(a,b-1);

}
int main()
{

int t,n,i,j;
scanf(“%d “,&t);
while(t–)
{
n=0;
while(gets(in[n]))
{

if(in[n][0]==’_’)
break;
n++;
}
for( i=0;i<n;i++)
{

for(j=0;in[i][j];j++)
{
if(in[i][j]==’*’)
dfs(i,j);
}
}
for(int i=0;i<=n;i++)
puts(in[i]);
}
return 0;
}