Spoj Solutions: November 2014

Friday, 14 November 2014

problem statement is here

#include<stdio.h>
int main()
{
long long int s,n,j,x;
while (1)
{
s=0;
scanf("%lld",&n);
if(n==0)
break;
else
{
x=n+1;
s=(3*x*x-x)/2;
}
printf("%lld\n",s);
}
return 0;
}

#include <stdio.h>

long long int dp[10010]={0};
int t,n;

long long int min(long long int a,long long int b){
return a > b ? b : a;
}

int main(){
int i, h,j,z,m;
long long int ar[10000],sum=0,min=100000000;
scanf("%d", &t);
scanf("%d",&z);
for(i=1;i<t;i++){
scanf("%lld",&ar[i]);
sum+=ar[i];
}
for(i=1;i<t;i++){
m=i;
for(j=1;j<=z;j++){
if(m>=1){
if(dp[m-1]<min){
min=dp[m-1];
}
m--;
}
}
dp[i]=min+ar[i];
min=100000000;
}
for(j=1;j<=z;j++){
if(dp[t-j]<min){
min=dp[t-j];
}
}
sum-=min;
printf("%lld\n",sum);
return 0;
}

Atoms in the Lab

problem statement is here

#include <stdio.h>
int main(){
int p;
long long n,k,m,count;
double mul;
scanf("%d",&p);
while(p--){
scanf("%lld %lld %lld",&n,&k,&m);
mul=n;
count=0;
while(mul<=m){
count++;
mul*=k;
}
if (count>0)
printf("%lld\n",count-1);
else
printf("0\n");
}

return 0;
}

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;
}

How to Handle the Fans

problem statement is here

#include<stdio.h>
#include<string.h>
long long n,br[1000000]={0};
long long int add(long long i,long long b){
while(i<=n){
br[i]+=b;
i=i+(i&((-1)*i));
}
}
long long find(long long i){
long long s=0;
while(i>0){
s+=br[i];
i=i-(i&((-1)*i));
}
return s;
}
int main(){
char ar[100];
long long a,b,c,d,i,j,t,u=0,ans,q;
scanf("%lld %lld",&n,&q);
while(q--){
scanf("%s %lld %lld",ar,&a,&b);
if(ar[0]=='a'){
add(a,b);
}else if(ar[0]=='f'){
if(a>1)
d=find(b)-find(a-1);
else
d=find(b);
printf("%lld\n",d);
}
}
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;
}

Monday, 3 November 2014

What’s Next

problem statement is here

#include<stdio.h>
int main()
{
int a,b,c,n,d,r,p,l;
while(1)
{
scanf("%d %d %d",&a,&b,&c);
if(a==0&&b==0&&c==0)
break;
else
{
l=(c-b)/(b-a);
if(l==1)
{
d=c-b;
n=c+d;
printf("AP %d\n",n);
}
else
{
r=c/b;
p=c*r;
printf("GP %d\n",p);
}
}
}
return 0;
}

abs(a-b) I

problem statement is here

#include<stdio.h>
int main(){
long long int a,b,ar[100000],i,j,u,p,t,sum;
scanf("%lld",&t);
while(t--){
sum=0;
scanf("%lld",&a);
scanf("%lld",&ar[0]);
u=0;
for(i=1;i<a;i++){
scanf("%lld",&ar[i]);
p=ar[i]-ar[i-1];
u+=(i*p);
sum+=u;
}
printf("%lld\n",sum);
}
return 0;
}