Physical Address
304 North Cardinal St.
Dorchester Center, MA 02124
Cute Chef Gift CodeChef Solution
Problem -Cute Chef Gift 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.
<<Previous CodeChef Problem Next Codechef Problem>>
Cute Chef Gift CodeChef Solution in C++17
#include <iostream>
using namespace std;
const int MAXN{100000 + 4};
int dzielnik[MAXN];
int gdzie_lewo[MAXN];
int gdzie_prawo[MAXN];
int ile_przedzialow[MAXN];
void Sito(){
for(size_t i = 2; i * i < MAXN; i++){
if(dzielnik[i] == 0){
for(size_t j = i * i; j < MAXN; j += i)
dzielnik[j] = i;
}
}
for(size_t i = 2; i < MAXN; i++){
if(dzielnik[i] == 0)
dzielnik[i] = i;
}
}
void Solve(){
//Czyszczenie tablic
for(size_t i = 1; i <= MAXN; ++i){
gdzie_lewo[i] = MAXN - 1;
gdzie_prawo[i] = 0;
ile_przedzialow[i] = 0;
}
int n;
cin >> n;
for(int i = 1; i <= n; ++ i){
int a;
cin >> a;
while(a > 1){
int p = dzielnik[a];
gdzie_lewo[p] = min(gdzie_lewo[p], i);
gdzie_prawo[p] = max(gdzie_prawo[p], i);
a /= p;
}
}
for(size_t i = 2; i < MAXN; ++i){
int l = gdzie_lewo[i];
int p = gdzie_prawo[i];
if(l <= p){
ile_przedzialow[l] +=1;
ile_przedzialow[p] -=1;
}
}
for(size_t i = 1; i <= n; ++i){
ile_przedzialow[i] += ile_przedzialow[i-1];
}
for(size_t i = 1; i < n; ++i){
if(ile_przedzialow[i] == 0){
cout << i << endl;
return;
}
}
}
int main() {
// your code goes here
Sito();
int t;
cin >> t;
for(size_t i = 1; i <= t; ++i)
Solve();
return 0;
}Cute Chef Gift CodeChef Solution in C++14
#include<iostream>
using namespace std;
typedef long long ll;
constexpr ll maxA=1e5+7;
ll D[maxA];
int T,N;
int main(){
for (int i = 2; i < maxA; i++)
{
D[i]=-1;
}
for (ll i = 2; i < maxA; i++)
{
if(D[i]==-1){
D[i]=i;
for (ll j = i*i; j < maxA; j+=i)
{
D[j]=i;
}
}
}
cin>>T;
for (int t = 0; t < T; t++)
{
cin>>N;
ll nums[N+1];
ll first[maxA]={0};
ll last[maxA]={0};
for (int i = 1; i <=N; i++)
{
cin>>nums[i];
int x=nums[i];
while(x>1){
int div=D[x];
if(first[div]>i||first[div]==0){
first[div]=i;
}
if(last[div]<i){
last[div]=i;
}
x=x/div;
}
}
int range[N+1]={0};
for (int i = 2; i <maxA; i++)
{
if(first[i]>0&&last[i]>0){
range[first[i]]+=1;
range[last[i]]+=-1;
}
}
for (int i = 1; i < N+1; i++)
{
range[i]=range[i-1]+range[i];
}
for (int i = 1; i < N+1; i++)
{
if(range[i]==0){
cout<<i<<'\n';
break;
}
}
}
return 0;
}Cute Chef Gift CodeChef Solution in PYTH 3
# cook your dish here
N=100000
prime=[-1 for i in range(N+1)]
i=2
while(i<=N):
if prime[i]==-1:
prime[i]=i
for j in range(2*i,N+1,i):
if prime[j]==-1:
prime[j]=i
i+=1
from math import gcd
for _ in range(int(input())):
n=int(input())
arr=list(map(int,input().split()))
range_p=[[-1,-1] for i in range(N+1)]
for i in range(n):
a=arr[i]
while(a>1):
x=prime[a]
if range_p[x][0]==-1:
range_p[x][0]=i
range_p[x][1]=i
else:
range_p[x][1]=i
a=a//x
#print(range_p[:10])
mark=[0 for i in range(n)]
for i in range(2,N+1):
if range_p[i][0]!=-1:
l=range_p[i][0]
r=range_p[i][1]
mark[l]+=1
mark[r]-=1
for i in range(1,n):
mark[i]+=mark[i-1]
#print(mark)
for i in range(n):
if mark[i]==0:
print(i+1)
break
Cute Chef Gift CodeChef Solution in C
#include<stdio.h>
int main(){long int t,i,j,k,a[100005],b[100005],c[100005],g[100005],left,n;
scanf("%ld",&t);
for(i=0;i<t;i++)
{
scanf("%ld",&n);
for(j=0;j<n;j++)
{
scanf("%ld",&a[j]);
b[j]=a[j];
c[j]=j;
}
for(j=0;j<=100000;j++)
{
g[j]=-1;
}
for(j=n-1;j>=0;j--)
{
if(b[j]%2==0)
{
while(b[j]%2==0)
{
b[j]=b[j]/2;
}
if(g[2]==-1)
{
g[2]=j;
}
}
for(k=3;k*k<=b[j];k=k+2)
{
if(b[j]%k==0)
{
while(b[j]%k==0)
{
b[j]=b[j]/k;
}
if(g[k]==-1)
{
g[k]=j;
}
}
}
if(b[j]>2)
{
if(g[b[j]]==-1)
g[b[j]]=j;
}
}
for(j=0;j<n;j++)
{
if(a[j]%2==0)
{
while(a[j]%2==0)
{
a[j]=a[j]/2;
}
if(c[j]<=g[2])
{
c[j]=g[2];
}
}
for(k=3;k*k<=a[j];k=k+2)
{
if(a[j]%k==0)
{
while(a[j]%k==0)
{
a[j]=a[j]/k;
}
if(g[k]>=c[j])
{
c[j]=g[k];
}
}
}
if(a[j]>2)
{
if(g[a[j]]>=c[j])
c[j]=g[a[j]];
}
}
left=0;
for(j=0;j<n;j++)
{
if(left<c[j])
left=c[j];
if(left==j)
break;
}
printf("\n");
printf("%ld\n",j+1);
}
return 0;
}Cute Chef Gift CodeChef Solution in JAVA
/* package codechef; // don't place package name! */
import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
class Codechef
{
static ArrayList<Integer> al;
static int start[];
static int end[];
static int size;
static int max=(int)1e5+1;
static Pair array[];
static class Pair{
int a,b,c;
Pair(int a,int b,int c){
this.a=a;
this.b=b;
this.c=c;
}
}
public static void main (String[] args) throws java.lang.Exception
{
// your code goes here
Scanner sc=new Scanner(System.in);
boolean val[]=new boolean[1000];
al=new ArrayList<>();
for(int i=2;i<val.length;i++)
{
if(!val[i]){
al.add(i);
for(int j=i*2;j<val.length;j+=i){
val[j]=true;
}
}
}
//System.out.println(al);
int t=sc.nextInt();
while(t-->0){
int n=sc.nextInt();
int arr[]=new int[n];
start=new int[max];
end=new int[max];
size=0;
Arrays.fill(start,-1);
Arrays.fill(end,-1);
int max_element=0;
for(int i=0;i<n;i++) {
arr[i]=sc.nextInt();
max_element=Math.max(max_element,arr[i]);
}
help(arr);
/*for (int ele : al) {
System.out.println("val= " + ele + " start= " + start[ele] + " end= " + end[ele]);
if (ele > max_element)
break;
}*/
array=new Pair[size];
int k=0;
for(int i=0;i< start.length;i++){
if(start[i]!=-1){
array[k]=new Pair(i,start[i],end[i]);
k++;
}
}
Arrays.sort(array, new Comparator<Pair>() {
@Override
public int compare(Pair o1, Pair o2) {
return o1.b- o2.b;
}
});
int en=array[0].c;
for(int i=1;i<array.length;i++){
if(en<array[i].b){
System.out.println(en+1);
break;
}
en=Math.max(en,array[i].c);
}
}
}
private static void help(int[] arr) {
int k;
for(int i=0;i<arr.length;i++){
k=0;
while (arr[i]>1 && k<al.size()){
int curr=al.get(k);
while(arr[i]%curr==0){
if(start[curr]==-1)
{
size++;
start[curr]=i;
}
end[curr]=i;
arr[i]/=curr;
}
k++;
}
if(arr[i]>1){
if(start[arr[i]]==-1)
{
size++;
start[arr[i]]=i;
}
end[arr[i]]=i;
}
}
}
}Cute Chef Gift CodeChef Solution in PYPY 3
MAXN = 100000 + 7
# dzielnik[i] = dowolny dzielnik pierwszy liczby i
dzielnik = [0]*MAXN
def sito():
i = 2
while (i*i < MAXN):
if (dzielnik[i] == 0):
for j in range(i*i, MAXN, i):
dzielnik[j] = i
i = i + 1
for i in range(2, MAXN):
if (dzielnik[i] == 0):
dzielnik[i] = i
def solve():
# gdzieLewo[p] = pierwszy indeks,
# na ktorym liczba jest podzielna przez p (pierwsze)
gdzieLewo = [MAXN]*MAXN
# gdziePrawo[p] = ostatni indeks,
# na ktorym liczba jest podzielna przez p (pierwsze)
gdziePrawo = [0]*MAXN
n = int(input())
liczby = list(map(int, input().split()))
for i in range(n):
a = liczby[i]
# rozklad liczby a na czynniki pierwsze
while (a > 1):
p = dzielnik[a]
gdzieLewo[p] = min(gdzieLewo[p], i+1)
gdziePrawo[p] = max(gdziePrawo[p], i+1)
a //= p
ilePrzedzialow = [0]*(n + 1)
for i in range(MAXN):
l = gdzieLewo[i]
r = gdziePrawo[i]
if (l <= r):
ilePrzedzialow[l] += 1
ilePrzedzialow[r] -= 1
for i in range(1, n):
ilePrzedzialow[i] += ilePrzedzialow[i - 1]
for i in range(1, n):
if (ilePrzedzialow[i] == 0):
print(i)
return
sito()
T = int(input())
for i in range(T):
solve()
Cute Chef Gift CodeChef Solution in PYTH
l=[[] for i in range(10**5+1)]
for i in range(2,10**5+1):
if l[i]==[]:
for j in range(i,10**5+1,i):
l[j].append(i)
for _ in range(input()):
n=input()
a=map(int,raw_input().split())
d={}
for i in range(n):
for j in l[a[i]]:
if j in d:
d[j]+=1
else:
d[j]=1
touched=0
zer=0
rech={}
for i in range(n):
for j in l[a[i]]:
if j not in rech:
touched+=1
rech[j]=1
d[j]-=1
if d[j]==0:
zer+=1
if zer==touched:
ans=i+1
break
print ansCute Chef Gift CodeChef Solution in C#
using System;
using System.Collections.Generic;
using System.Globalization;
using System.IO;
using System.Linq;
using System.Text;
using System.Threading;
// (づ°ω°)づﾐe★゜・。。・゜゜・。。・゜☆゜・。。・゜゜・。。・゜
public class Solution
{
private const int SIEVE_SIZE = 100000;
private readonly bool[] isComposite = new bool[SIEVE_SIZE + 1];
private readonly List<int> primes = new List<int>();
void Sieve()
{
for (int i = 2; i * i <= SIEVE_SIZE; i++)
if (!isComposite[i])
for (int j = i * i; j <= SIEVE_SIZE; j += i)
isComposite[j] = true;
for (int i = 2; i <= SIEVE_SIZE; i++)
if (!isComposite[i])
primes.Add(i);
}
public void Solve()
{
Sieve();
for (int tt = ReadInt(); tt > 0; tt--)
{
int n = ReadInt();
var a = ReadIntArray();
var b = Init<List<Tuple<int, int>>>(n);
int m = primes.Count;
var rcnt = new int[m];
for (int i = 0; i < n; i++)
{
for (int j = 0; primes[j] * primes[j] <= a[i]; j++)
if (a[i] % primes[j] == 0)
{
int c = 0;
while (a[i] % primes[j] == 0)
{
a[i] /= primes[j];
c++;
}
b[i].Add(Tuple.Create(j, c));
rcnt[j] += c;
}
if (a[i] > 1)
{
int x = primes.BinarySearch(a[i]);
b[i].Add(Tuple.Create(x, 1));
rcnt[x]++;
}
}
int o = 0;
var lcnt = new int[m];
for (int i = 0; i + 1 < n; i++)
{
foreach (var t in b[i])
{
if (lcnt[t.Item1] == 0 && rcnt[t.Item1] > 0)
o++;
lcnt[t.Item1]++;
rcnt[t.Item1] -= t.Item2;
if (rcnt[t.Item1] == 0)
o--;
}
if (o == 0)
{
Write(i + 1);
break;
}
}
}
}
#region Main
protected static TextReader reader;
protected static TextWriter writer;
static void Main()
{
#if DEBUGLOCAL
reader = new StreamReader("..\\..\\input.txt");
//reader = new StreamReader(Console.OpenStandardInput());
writer = Console.Out;
//writer = new StreamWriter("..\\..\\output.txt");
#else
reader = new StreamReader(Console.OpenStandardInput());
writer = new StreamWriter(Console.OpenStandardOutput());
//reader = new StreamReader("input.txt");
//writer = new StreamWriter("output.txt");
#endif
try
{
new Solution().Solve();
//var thread = new Thread(new Solver().Solve, 1024 * 1024 * 128);
//thread.Start();
//thread.Join();
}
catch (Exception ex)
{
#if DEBUG
Console.WriteLine(ex);
#else
throw;
#endif
}
reader.Close();
writer.Close();
}
#endregion
#region Read / Write
private static Queue<string> currentLineTokens = new Queue<string>();
private static string[] ReadAndSplitLine() { return reader.ReadLine().Split(new[] { ' ', '\t', }, StringSplitOptions.RemoveEmptyEntries); }
public static string ReadToken() { while (currentLineTokens.Count == 0) currentLineTokens = new Queue<string>(ReadAndSplitLine()); return currentLineTokens.Dequeue(); }
public static int ReadInt() { return int.Parse(ReadToken()); }
public static long ReadLong() { return long.Parse(ReadToken()); }
public static double ReadDouble() { return double.Parse(ReadToken(), CultureInfo.InvariantCulture); }
public static int[] ReadIntArray() { return ReadAndSplitLine().Select(int.Parse).ToArray(); }
public static long[] ReadLongArray() { return ReadAndSplitLine().Select(long.Parse).ToArray(); }
public static double[] ReadDoubleArray() { return ReadAndSplitLine().Select(s => double.Parse(s, CultureInfo.InvariantCulture)).ToArray(); }
public static int[][] ReadIntMatrix(int numberOfRows) { int[][] matrix = new int[numberOfRows][]; for (int i = 0; i < numberOfRows; i++) matrix[i] = ReadIntArray(); return matrix; }
public static int[][] ReadAndTransposeIntMatrix(int numberOfRows)
{
int[][] matrix = ReadIntMatrix(numberOfRows); int[][] ret = new int[matrix[0].Length][];
for (int i = 0; i < ret.Length; i++) { ret[i] = new int[numberOfRows]; for (int j = 0; j < numberOfRows; j++) ret[i][j] = matrix[j][i]; }
return ret;
}
public static string[] ReadLines(int quantity) { string[] lines = new string[quantity]; for (int i = 0; i < quantity; i++) lines[i] = reader.ReadLine().Trim(); return lines; }
public static void WriteArray<T>(IEnumerable<T> array) { writer.WriteLine(string.Join(" ", array)); }
public static void Write(params object[] array) { WriteArray(array); }
public static void WriteLines<T>(IEnumerable<T> array) { foreach (var a in array) writer.WriteLine(a); }
private class SDictionary<TKey, TValue> : Dictionary<TKey, TValue>
{
public new TValue this[TKey key]
{
get { return ContainsKey(key) ? base[key] : default(TValue); }
set { base[key] = value; }
}
}
private static T[] Init<T>(int size) where T : new() { var ret = new T[size]; for (int i = 0; i < size; i++) ret[i] = new T(); return ret; }
#endregion
}Cute Chef Gift CodeChef Solution in GO
package main
import (
"bufio"
"bytes"
"fmt"
"os"
)
func main() {
reader := bufio.NewReader(os.Stdin)
tc := readNum(reader)
var buf bytes.Buffer
for tc > 0 {
tc--
n := readNum(reader)
A := readNNums(reader, n)
res := solve(n, A)
buf.WriteString(fmt.Sprintf("%d\n", res))
}
fmt.Print(buf.String())
}
func readInt(bytes []byte, from int, val *int) int {
i := from
sign := 1
if bytes[i] == '-' {
sign = -1
i++
}
tmp := 0
for i < len(bytes) && bytes[i] >= '0' && bytes[i] <= '9' {
tmp = tmp*10 + int(bytes[i]-'0')
i++
}
*val = tmp * sign
return i
}
func readNum(reader *bufio.Reader) (a int) {
bs, _ := reader.ReadBytes('\n')
readInt(bs, 0, &a)
return
}
func readTwoNums(reader *bufio.Reader) (a int, b int) {
res := readNNums(reader, 2)
a, b = res[0], res[1]
return
}
func readThreeNums(reader *bufio.Reader) (a int, b int, c int) {
res := readNNums(reader, 3)
a, b, c = res[0], res[1], res[2]
return
}
func readNNums(reader *bufio.Reader, n int) []int {
res := make([]int, n)
x := 0
bs, _ := reader.ReadBytes('\n')
for i := 0; i < n; i++ {
for x < len(bs) && (bs[x] < '0' || bs[x] > '9') && bs[x] != '-' {
x++
}
x = readInt(bs, x, &res[i])
}
return res
}
func readUint64(bytes []byte, from int, val *uint64) int {
i := from
var tmp uint64
for i < len(bytes) && bytes[i] >= '0' && bytes[i] <= '9' {
tmp = tmp*10 + uint64(bytes[i]-'0')
i++
}
*val = tmp
return i
}
const MAX_A = 100010
var spf [MAX_A]int
func init() {
set := make([]bool, MAX_A)
for x := 2; x < MAX_A; x++ {
if !set[x] {
for y := x; y < MAX_A; y += x {
if spf[y] == 0 {
spf[y] = x
}
set[y] = true
}
}
}
}
func solve(n int, A []int) int {
left := make(map[int]int)
right := make(map[int]int)
update := func(mem map[int]int, k int, v int, fn func(int, int) int) {
if w, ok := mem[k]; !ok {
mem[k] = v
} else {
mem[k] = fn(w, v)
}
}
for i := 0; i < n; i++ {
cur := A[i]
for spf[cur] != cur {
x := spf[cur]
update(left, x, i, min)
update(right, x, i, max)
cur /= x
}
update(left, cur, i, min)
update(right, cur, i, max)
}
cnt := make([]int, n+1)
for k, i := range left {
j := right[k]
cnt[i]++
cnt[j]--
}
for i := 1; i <= n; i++ {
cnt[i] += cnt[i-1]
}
for i := 1; i <= n; i++ {
if cnt[i-1] == 0 {
return i
}
}
return -1
}
func min(a, b int) int {
if a <= b {
return a
}
return b
}
func max(a, b int) int {
if a >= b {
return a
}
return b
}Cute Chef Gift CodeChef Solution Review:
In our experience, we suggest you solve this Cute Chef Gift 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 Cute Chef Gift CodeChef Solution.
Conclusion:
I hope this Cute Chef Gift 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!
