Physical Address
304 North Cardinal St.
Dorchester Center, MA 02124
Our Base is Under Attack CodeChef Solution
Problem -Our Base is Under Attack CodeChef Solution
“This website is dedicated for CodeChef solution where we will publish right solution of all your favourite CodeChef problems along with detailed explanatory of different competitive programming concepts and languages.
Our Base is Under Attack CodeChef Solution in C++14
“#include <iostream>
#include<bits/stdc++.h>
using namespace std;
vector<long long int>v[47];
int main()
{
long long int i,j;
for(i=2;i<=(int)1e6;i++)
{
long long int tem=i;
for(j=2;j<=40;j++)
{
tem=tem*i;
if(tem>(long long int)1e12)
break;
v[j].push_back(tem);
}
}
int t;
scanf("%d",&t);
while(t--)
{
long long int m;
scanf("%lld",&m);
if(m==1)
{
printf("INFINITY\n");
continue;
}
long long int ans=(m+1)/2;
long long int p=m/2+1;
for(i=2;i<=40;i++)
ans=ans+(lower_bound(v[i].begin(),v[i].end(),m+1)-lower_bound(v[i].begin(),v[i].end(),p));
printf("%lld\n",ans);
}
return 0;
}Our Base is Under Attack CodeChef Solution in PYTH 3
“def g(x, k, c):
t=int(pow((x+1)/c, 1/float(k)))+2
while c*(t-1)**k>x:
t-=1
return t
ncase= int(input())
for testcase in range(ncase):
x=int(input())
if x==0:
print("0")
if x==1:
print("INFINITY")
if x>1:
ans=0
for k in range(1, 40):
ans+=g(x, k, 1)-g(x, k, 2)
print(ans)Our Base is Under Attack CodeChef Solution in C
“ #include<stdio.h>
long long int T, n, L, R, mid,ans;
long long int check(long long int a, long long int k, long long int s) {
long long int tmp = 1;
while(k) {
if(k % 2 == 1) {
if(((double)(tmp) / (double)(s) * (double)(a)) > 1) return 1;
tmp *= a;
}
k /= 2;
if(k > 0 && ((double)(a) / (double)(s) * (double)(a)) > 1) return 1;
a *= a;
}
return (tmp>s)?1:0;
}
long long int solve(long long int s, long long int k) {
L = 1;
while(R - L > 1) {
mid = (R + L) / 2;
if(check(mid, k, s)==1) R = mid;
else L = mid;
}
return R;
}
int main() {
long long int k;
scanf("%lld ",&T);
while(T--) {
scanf("%lld ",&n);
if(n==0){printf("0\n");continue;}
if(n==1) {
printf("INFINITY\n");continue;
}
ans = 0;
L = 1, R = n+1;
for( k=1; k<=40; k++)
ans += solve(n, k) - solve(n/2, k);
printf("%lld\n",ans);
}
return 0;
}
Our Base is Under Attack CodeChef Solution in JAVA
“import java.util.*;
import java.lang.*;
import java.io.*;
import java.math.BigInteger;
import java.util.Arrays;
class Main {
public static void main (String[] args) throws java.lang.Exception{
InputReader in = new InputReader(System.in);
int t=in.nextInt();
StringBuffer str=new StringBuffer();
while(t-->0){
long n=in.nextLong();
if(n==1)
str.append("INFINITY\n");
else{
long k=1;
long count=0;
while(true){
double inv=1.0/k;
long high=(long)(Math.pow(n,inv));
if((long)Math.pow(high+1,k)<=n)
high++;
long low=(long)(Math.pow(n/2,inv));
if((long)Math.pow(low+1,k)<=n/2)
low++;
if(low<high)
count+=high-low;
if(high<=1)
break;
k++;
}
str.append(count).append("\n");
}
}
System.out.println(str);
}
static class InputReader {
private InputStream stream;
private byte[] buf = new byte[1024];
private int curChar;
private int numChars;
public InputReader(InputStream stream) {
this.stream = stream;
}
public int read() {
if (numChars == -1)
throw new UnknownError();
if (curChar >= numChars) {
curChar = 0;
try {
numChars = stream.read(buf);
} catch (IOException e) {
throw new UnknownError();
}
if (numChars <= 0)
return -1;
}
return buf[curChar++];
}
public int peek() {
if (numChars == -1)
return -1;
if (curChar >= numChars) {
curChar = 0;
try {
numChars = stream.read(buf);
} catch (IOException e) {
return -1;
}
if (numChars <= 0)
return -1;
}
return buf[curChar];
}
public void skip(int x) {
while (x-- > 0)
read();
}
public int nextInt() {
return Integer.parseInt(next());
}
public long nextLong() {
return Long.parseLong(next());
}
public String nextString() {
return next();
}
public String next() {
int c = read();
while (isSpaceChar(c))
c = read();
StringBuffer res = new StringBuffer();
do {
res.appendCodePoint(c);
c = read();
} while (!isSpaceChar(c));
return res.toString();
}
public String nextLine() {
StringBuffer buf = new StringBuffer();
int c = read();
while (c != '\n' && c != -1) {
if (c != '\r')
buf.appendCodePoint(c);
c = read();
}
return buf.toString();
}
public double nextDouble() {
int c = read();
while (isSpaceChar(c))
c = read();
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
double res = 0;
while (!isSpaceChar(c) && c != '.') {
if (c == 'e' || c == 'E')
return res * Math.pow(10, nextInt());
if (c < '0' || c > '9')
throw new InputMismatchException();
res *= 10;
res += c - '0';
c = read();
}
if (c == '.') {
c = read();
double m = 1;
while (!isSpaceChar(c)) {
if (c == 'e' || c == 'E')
return res * Math.pow(10, nextInt());
if (c < '0' || c > '9')
throw new InputMismatchException();
m /= 10;
res += (c - '0') * m;
c = read();
}
}
return res * sgn;
}
public boolean hasNext() {
int value;
while (isSpaceChar(value = peek()) && value != -1)
read();
return value != -1;
}
private boolean isSpaceChar(int c) {
return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
}
}
}Our Base is Under Attack CodeChef Solution in PYTH
“"""
BASE.py
Our Base is Under Attack
https://www.codechef.com/problems/BASE
Author : Tomiko
Created : Feb 08, 2020
Last Modified : Feb 08, 2020
"""
"""
SUBMISSIONS:
Solution 1
Submission partially accepted on 2020-02-08 10:56:28 PST. Got 'Time Limit Exceeded' in subtasks 2, 3, and 4.
ID: 29433935
Link: https://www.codechef.com/viewsolution/29433935
Time: 0.13 sec
Memory: 22.8M
Score: 16(16pts)
"""
## -----------------------------------------------------------------------------
class Solution_1(object):
"""Solution 1
Analysis:
Naive approach described in problem editorial.
We can iterate over all bases in the range [2,N],
find the base-B representation of N and check
if it starts with 1.
Submission partially accepted on 2020-02-08 10:56:28 PST. Got 'Time Limit Exceeded' in subtasks 2, 3, and 4.
ID: 29433935
Link: https://www.codechef.com/viewsolution/29433935
Time: 0.13 sec
Memory: 22.8M
Score: 16(16pts)
"""
def solve(self, N):
if N == 0:
# No base representation of 0 can start with 1.
return 0
if N == 1:
# 1 written in any base B starts with 1.
return 'INFINITY'
def _firstDigitOfBaseB(n, base):
"""Returns the first digit of `n` in base-B representation.
Reference:
https://www.tutorialspoint.com/computer_logical_organization/number_system_conversion.htm
"""
while n > 1:
n /= base
r = n % base
return r
##
# Iterate over all bases in the range [2, N]
# find the base-B representation of N
# and check if it starts with 1.
return sum((_firstDigitOfBaseB(N, base) for base in xrange(2, N+1)))
## -----------------------------------------------------------------------------
class Solution_2(object):
"""Solution 2
Time complexity:
O( 40 * t ), where t is the complexity of the pow(a,b) function,
where b is a floating point number less than 1.
"""
def solve(self, N):
if N == 0:
# No base representation of 0 can start with 1.
return 0
if N == 1:
# 1 written in any base B starts with 1.
return 'INFINITY'
def f(n, k, c):
t = int(pow((n+1)/c, 1 / float(k))) + 2
while c * ((t-1) ** k) > n:
t -= 1
return t
res = 0
for k in xrange(1, 40):
res += (f(N, k, 1) - f(N, k, 2))
return res
## -----------------------------------------------------------------------------
# Solution = Solution_1 # Submission partially accepted. Got 'Time Limit Exceeded' in subtasks 2, 3, and 4.
Solution = Solution_2
class Driver(object):
def run(self):
T = int(raw_input().strip())
for _ in xrange(T):
N = int(raw_input().strip())
assert 0 <= N <= int(1e12)
soln = Solution()
res = soln.solve(N)
print res
def main():
driver = Driver()
driver.run()
if __name__ == '__main__':
main()Our Base is Under Attack CodeChef Solution in NODEJS
“package main
import (
"bufio"
"fmt"
"os"
"sort"
"strconv"
)
func main() {
var queries Queries
T := readi()
for t := 0; t < T; t++ {
queries = append(queries, Query{
idx: t,
n: readi64(),
})
}
ans := solve(queries)
for _, str := range ans {
fmt.Fprintln(writer, str)
}
writer.Flush()
}
func solve(queries Queries) []string {
//fmt.Printf("%+v\n", queries)
sort.Sort(QueriesN{queries})
searchFunc := func(value int64) func(i int) bool {
return func(i int) bool {
if queries[i].n >= value {
return true
}
return false
}
}
for base := int64(2); base <= 1e6; base++ {
cur := base * base
for {
first := sort.Search(len(queries), searchFunc(cur))
if first == len(queries) {
break
}
queries[first].ans++
last := sort.Search(len(queries), searchFunc(cur*2))
if last < len(queries) {
queries[last].ans--
}
cur *= base
}
}
for i := range queries {
if i > 0 {
queries[i].ans += queries[i-1].ans
}
}
sort.Sort(queries)
var answers []string
for i := range queries {
if queries[i].n == 1 {
queries[i].ans = -1
} else {
queries[i].ans += queries[i].n - queries[i].n/2
}
if queries[i].ans == -1 {
answers = append(answers, "INFINITY")
} else {
answers = append(answers, strconv.FormatInt(queries[i].ans, 10))
}
}
return answers
}
type Query struct {
idx int
ans, n int64
}
type Queries []Query
func (q Queries) Len() int {
return len(q)
}
func (q Queries) Less(i, j int) bool {
return q[i].idx < q[j].idx
}
func (q Queries) Swap(i, j int) {
q[i], q[j] = q[j], q[i]
}
type QueriesN struct {
Queries
}
func (q QueriesN) Less(i, j int) bool {
return q.Queries[i].n < q.Queries[j].n
}
var (
reader = bufio.NewReaderSize(os.Stdin, 1<<13)
writer = bufio.NewWriterSize(os.Stdout, 1<<13)
)
func readi() int {
return int(readi64())
}
func readi64() int64 {
b, err := reader.ReadByte()
for !isValid(b, err) {
b, err = reader.ReadByte()
}
sign, res := int64(1), int64(0)
if b == '-' {
sign *= -1
b, err = reader.ReadByte()
}
for isValid(b, err) {
res = res*10 + int64(b-'0')
b, err = reader.ReadByte()
}
return res * sign
}
func isValid(b byte, err error) bool {
return err == nil && (('0' <= b && b <= '9') || b == '-')
}Our Base is Under Attack CodeChef Solution in GO
“package main
import (
"fmt"
"math"
)
func main() {
var T int
fmt.Scan(&T)
for i:=0; i<T; i++ {
var N int
fmt.Scan(&N)
var a string
fmt.Scan(&a)
var zeros1 int = 0
var ones1 int = 0
var zeros2 int = 0
var ones2 int = 0
for j:=0; j<N/2; j++ {
if (a[j] == '1' && a[N-1-j] == '0') {
ones1 += 1
zeros2 += 1
} else if a[j] == '0' && a[N-1-j] == '1' {
zeros1 += 1
ones2 += 1
}
}
var first int = zeros1 + (ones1+1)/2
var second int = zeros2 + (ones2+1)/2
var third int = zeros1+zeros2
var fourth int = (ones1+ones2+1)/2
fmt.Println(math.Min(float64(first), math.Min(float64(second), math.Min(float64(third), float64(fourth)))))
}
}Our Base is Under Attack CodeChef Solution Review:
In our experience, we suggest you solve this Our Base is Under Attack CodeChef Solution and gain some new skills from Professionals completely free and we assure you will be worth it.
If you are stuck anywhere between any coding problem, just visit Queslers to get the Our Base is Under Attack CodeChef Solution.
“Conclusion:
I hope this Our Base is Under Attack CodeChef Solution would be useful for you to learn something new from this problem. If it helped you then don’t forget to bookmark our site for more Coding Solutions.
This Problem is intended for audiences of all experiences who are interested in learning about Programming Language in a business context; there are no prerequisites.
Keep Learning!
