Spoj Solutions: brute force

Showing posts with label brute force. Show all posts

Tuesday, 9 June 2015

#include<stdio.h>
#include<math.h>

int main()
{
long long int a,t,i,j,n,b;
scanf("%lld",&t);
while(t--){
scanf("%lld",&a);
for(i=1; ;i++){
if(a>(pow(2,i)-2) && a<=(pow(2,i+1)-2)){
b=a-(pow(2,i)-2);
break;
}
}
n=i;
for(j=1;j<=n;j++){
if(b>pow(2,i-1)){
printf("6");
b=b-pow(2,i-1);
}else{
printf("5");
}
i--;
}
printf("\n");
}
return 0;
}

Traversing Grid

problem statement is here

#include<stdio.h>
int main(){
long long int n,m;
int t;
scanf("%d",&t);
while(t--){
scanf("%lld %lld",&n,&m);
if(n%2==0 && m%2==0){
if(n>m){
printf("U\n");
}else if(m>=n)
printf("L\n");
}
else if(n%2!=0 && m%2!=0){
if(n>m)
printf("D\n");
else if(m>=n)
printf("R\n");
}
else{
if(n%2==0 && m%2!=0)
{
if(n>m)
printf("D\n");
else
printf("L\n");
}
if(n%2!=0 && m%2==0)
{
if(n<m)
printf("R\n");
else
printf("U\n");
}
}
}
return 0;
}

To and Fro

problem statement is here

#include<stdio.h>
#include<string.h>

int main()
{
int a,i,j,n,b,k;
char ar[210];
while(1){
scanf("%d",&a);
if(a==0)
break;
else{
scanf("%s",ar);
b=strlen(ar);
j=a;
for(i=0;i<a;i++){
printf("%c",ar[i]);
for(k=2; ;k+=2){
if((k*j-i-1)<b){
printf("%c",ar[k*j-i-1]);
}else{
break;
}
if((k*j+i)<b){
printf("%c",ar[k*j+i]);
}else{
break;
}
}
}
printf("\n");
}
}
return 0;
}

Finding the Tesserect

problem statement is here

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

int main(){

int t;

scanf("%d\n",&t);

while(t--)

{

int n,i;

scanf("%d\n",&n);

long long int a,b;

scanf("%lld",&a);

char ar[1000000],br[1000000];

for(i=1;i<n;i++){

scanf("%lld",&b);

if(b>a){

ar[i-1]='G';

}else if(b==a){

ar[i-1]='E';

}else{

ar[i-1]='L';

}

a=b;

}

ar[n]='\0';

scanf("%s",br);

if(strstr(ar,br))

printf("YES\n");

else

printf("NO\n");

}

return 0;

}

War

problem statement is here

#include<stdio.h>
#include<algorithm>
using namespace std;
int main(){
long long int s,ar[100009],br[100009],i,j,z,p,a;
scanf("%lld",&s);
for(i=0;i<s;i++){
scanf("%lld",&ar[i]);
}
for(i=0;i<s;i++){
scanf("%lld",&br[i]);
}
sort(ar,ar+s);
sort(br,br+s);
z=s-1;p=0;
for(i=s-1;i>=0;i--){
if(ar[i]<br[z]){
p++;
z--;
}
}
printf("%lld\n",p);
return 0;
}

Saturday, 24 January 2015

Count on Cantor

problem statement is here

#include<stdio.h>

int main()
{
long long int t,a,b,c,i,j,k;
scanf("%lld",&t);
while(t--){
scanf("%lld",&a);
for(i=0; ;i++){
if(((i*(i+1))/2)<a && a<=(((i+1)*(i+2))/2) ){
b=a-((i*(i+1))/2);
break;
}
}
c=i+1;
if(c%2==0){
j=b;
k=c+1-b;
}else{
j=c+1-b;
k=b;
}
printf("TERM %lld IS %lld/%lld\n",a,j,k);
}
return 0;
}

Monday, 29 December 2014

Tulip And Numbers

problem statement is here

#include<stdio.h>
int main(){
int a,b,c,d,i,j,n,m,t,ar,x=1,br[100005];
scanf("%d",&t);
while(t--){
scanf("%d %d",&n,&m);
scanf("%d",&ar);
a=ar;
br[0]=0;
br[1]=1;
for(i=1;i<n;i++){
scanf("%d",&ar);
if(a==ar){
br[i+1]=br[i];
}else{
br[i+1]=br[i]+1;
a=ar;
}
}
printf("Case %d:\n",x);
x++;
for(i=0;i<m;i++){
scanf("%d %d",&a,&b);
if(a==1){
c=br[b];
}else{
if(br[a]==br[a-1]){
c=br[b]-br[a-1]+1;
}else{
c=br[b]-br[a-1];
}
}
printf("%d\n",c);
}

}
return 0;
}

Friday, 14 November 2014

MayanCalendar

problem statement is here

#include<stdio.h>

int main()

{

long long int t,i,month,year1,year2,x,y,total_days,u,a,b,c,d,e;

scanf("%lld",&t);

while(t--)

{

int arr[13];

arr[1]=31,arr[2]=28,arr[3]=31,arr[4]=30,arr[5]=31,arr[6]=30,arr[7]=31,arr[8]=31,arr[9]=30,arr[10]=31,arr[11]=30,arr[12]=31;

total_days=0;

scanf("%lld %lld",&year1,&year2);

y=1901;

month=12;i=0;

if(year1>1901){

while(y<year1){

if((y%4==0&&y%100!=0)||y%400==0){

total_days+=366;

}else{

total_days+=365;

}

y=y+1;

}

u=0;

i=total_days%7;

total_days=i;

if(i==4){

u++;

}

for(x=year1;x<=year2;x++){

for(y=1;y<=12;y++){

if(x==year2 && y==12)

break;

if(y==2){

if((x%4==0&&x%100!=0)||x%400==0){

total_days+=29;

}else{

total_days+=28;

}

}else

total_days+=arr[y];

if(total_days%7==4){

u++;

}

total_days=total_days+31-i-u;

a=total_days/144000;

total_days-=(a*144000);

b=total_days/7200;

total_days-=(b*7200);

c=total_days/360;

total_days-=(c*360);

d=total_days/20;

total_days-=(d*20);

e=total_days;

printf("%lld.%lld.%lld.%lld.%lld\n",a,b,c,d,e);

}

return 0;

}

Tuesday, 11 November 2014

Tiles of Tetris, Not!

problem statement is here

#include<stdio.h>
int main(){
long long int a,b,n,p;
while(1){
scanf("%lld %lld",&a,&b);
if(a==0 && b==0)
break;
if(a>b){
if(a%b==0)
printf("%lld\n",a/b);
else
printf("%lld\n",a*b);
}else{
if(b%a==0)
printf("%lld\n",b/a);
else
printf("%lld\n",a*b);
}
}
return 0;
}

What is your Logo

problem statement is here

#include<cstdio>
using namespace std;
int main(){
int a,b,c,i,j,u,v,ans;
char br[1100];
bool ar[2002][2002];
while(1){

scanf("%s",br);
if(br[0]=='Q')
break;
for(i=0;i<2002;i++){
for(j=0;j<2002;j++){
ar[i][j]=false;
}
}
u=1001;v=1001;ans=0;
for(i=0;br[i]!='Q';i++){
ar[u][v]=true;
if(br[i]=='U'){
u--;
if(ar[u][v]==1){
ans++;
}
}else if(br[i]=='D'){
u++;
if(ar[u][v]==1){
ans++;
}
}else if(br[i]=='R'){
v++;
if(ar[u][v]==1){
ans++;
}
}else if(br[i]=='L'){
v--;
if(ar[u][v]==1){
ans++;
}
}
}
printf("%d\n",ans);
}
return 0;
}

Think I will Buy Me a Football Team

problem statement is here

#include <stdio.h>
int b[10000];
int main(){
long long int n,i,j,sum,z,c=1;
while(1){
scanf("%lld",&n);
if(n==0)
break;
sum = 0;
for(i=0;i<n;i++)
b[i] = 0;
for(i=0;i<n;i++){
for(j=0;j<n;j++){
scanf("%lld", &z);
if(z){
b[j]+=z;
b[i]-=z;
sum+=z;
}
}
}
printf("%lld. %lld ",c,sum);
sum = 0;
for(i=0;i<n;i++){
if(b[i] > 0)
sum += b[i];
}
printf("%lld\n", sum);
c++;
}
return 0;
}

Saturday, 8 November 2014

Saruman of Many Colours

problem statement is here

#include<stdio.h>

#include<string.h>

int main(){

long int a,b,t,i,j,sum,n,u,k;

scanf("%ld",&t);

while(t--){

j=1;

sum=0;b=0;u=0;

char ar[25000];

scanf("%ld %ld",&n,&k);

scanf("%s",ar);

for(i=0;i<n;i++){

if(ar[i]>96 && ar[i]<123){

if(ar[i]==u){

b++;

if(b==k){

j=0;

b=0;

u=0;

}

}else{

sum++;

u=ar[i];

b=1;

if(b==k){

j=0;

b=0;

u=0;

}

if(j==1){

printf("-1\n");

}else{

printf("%ld\n",sum);

}

return 0;

}

The Glittering Caves of Aglarond

problem statement is here

#include<stdio.h>

int main(){

int a,b,t,x,n,m,k,i,j,min,h;
char arr[55];
scanf("%d",&t);
while(t--){
int ar[55]={0};
scanf("%d %d %d",&n,&m,&k);
for(i=0;i<n;i++){
scanf("%s",arr);
for(h=0;h<m;h++){
if(arr[h]=='*')
ar[i]++;
}
}
for(j=0;j<k;j++){
min=ar[0];
a=0;
for(i=1;i<n;i++){
if(ar[i]<min){
min=ar[i];
a=i;
}
}
ar[a]=m-min;
}
int ans=0;
for(i=0;i<n;i++){
ans+=ar[i];
}
printf("%d\n",ans);
}
return 0;
}

The Mirror of Galadriel

problem statement is here

#include<stdio.h>

int main()

{

int t,i,count,j,l;

char a[11];

scanf("%d",&t);

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

{

count=0;

scanf("%s",a);

l=strlen(a);

for(j=0;j<l;j++)

{

if(a[j]!=a[l-1-j])

count=1;

}

if(count==1)

printf("NO\n");

else

printf("YES\n");

}

return 0;

}

Gandalf vs the Balrog

problem statement is here

#include<stdio.h>

int main(){

int t,i,j,f,p,q;

scanf("%d",&t);

while(t--){

int n,m;

f=0;

scanf("%d%d",&n,&m);

if(m==0)

printf("2 %d\n",n);

else{

int ar[n];

for(i=0;i<=n-1;i++)

ar[i]=i;

for(i=0;i<=m-1;i++){

scanf("%d%d",&p,&q);

ar[p-1]+=1;

ar[q-1]-=1;

}

for(i=n-1;i>=0;i--){

if(ar[i]==n-1){

j=i;

f=1;

break;

}

if(f==1)

printf("2 %d\n",j+1);

else

printf("1\n");

}

return 0;

}

Thursday, 6 November 2014

Alice Sieve

problem statement is here

#include<stdio.h>
int main(){
long a,t;
scanf("%ld",&t);
while(t--){
scanf("%ld",&a);
printf("%ld\n",(a+1)/2);
}
return 0;
}

Wednesday, 5 November 2014

Adding Reversed Numbers

problem statement is here

#include<stdio.h>
int main()
{
int a,n,i,m,j,p,o,t,s,c,l;
scanf("%d",&a);
int ar[a];
for(i=0;i<a;i++)
{
c=0;s=0;j=0;
scanf("%d %d",&n,&m);
while(n!=0)
{
p=n%10;
c=c*10+p;
n=n/10;
}
while(m!=0)
{
o=m%10;
s=s*10+o;
m=m/10;
}
t=s+c;
while(t!=0)
{
l=t%10;
j=j*10+l;
t=t/10;

}
printf("%d\n",j);

}

return 0;
}

Alpha Centauri Tennis

problem statement is here

#include<stdio.h>
#include<string.h>
int main(){
int t;
scanf("%d",&t);
while (t--)
{
int n;
char s[500000];
scanf("%d %s",&n,s);
printf("%c\n",s[strlen(s)-1]);
}
return 0;
}

Between the Mountains

problem statement is here

#include<stdio.h>

int main()

{

long long int t,a,b,ar[1100],br[1100],x,h,k,p,i,j,ans,now;

scanf("%lld",&t);

while(t--)

{

now=0;

ans=10000000;

h=0;k=0;x=0;

scanf("%lld",&a);

for(i=0;i<a;i++)

scanf("%lld",&ar[i]);

scanf("%lld",&b);

for(i=0;i<b;i++)

scanf("%lld",&br[i]);

for(i=0;i<a;i++)

{

for(j=0;j<b;j++)

{

if(ar[i]==br[j])

{

h=1;

ans=0;

break;

}else if(ar[i]>br[j]){

now=ar[i]-br[j];

}else{

now=br[j]-ar[i];

}

ans=(ans<now)?ans:now;

}

if(h==1)

break;

}

printf("%lld\n",ans);

}

return 0;

}

Sometimes, a penalty is good!

problem statement is here

#include<stdio.h>
#include<math.h>

int main(){
long long g,t,a,d,x,y,n,i,j,k,l;
while(1){
n=0;
scanf("%lld %lld %lld %lld",&g,&t,&a,&d);
if(g==-1&&t==-1&&a==-1&&d==-1)
break;
else{
n=g*((t*(t-1))/2);
k=g*a+d;
for(i=0;i<50 ;i++){
if(pow(2,i)==k){
y=0;
i--;
break;
}else if(pow(2,i)<k && pow(2,i+1)>k){
y=pow(2,i+1)-k;
break;
}
}
for(l=i;l>=0;l--){
n+=pow(2,l);
}
printf("%lld*%lld/%lld+%lld=%lld+%lld\n",g,a,t,d,n,y);
}
}
return 0;
}