PROBLEM LINK:
Author: Pritish Priyatosh Nayak
Tester: Niket Agarwal
Editorialist: Pritish Priyatosh Nayak
DIFFICULTY:
Simple
PREREQUISITES:
Prefix Sums , Observation.
PROBLEM:
Problem-statement
Subham has come to a circular race track to practice for hurdle race.
The race track is divided into N sections.
In each of the sections, he has placed some hurdles. The i^{th} section has hurdles of height h_i.
He starts at section 1 and he runs in direction of increasing index (i.e from index i to index (i+1) . Note : After N^{th} index he comes to 1^{st} index ).
Each time he runs past a section having hurdles with height h_i , he burns h_i calories. He has decided to run until he has crossed K sections.
Tell him how many calories he burns after running through K sections modulo 10^9+7.
EXPLANATION:
Hard Version Editorial Link: FCF3P1 - Editorial
As K is too large , we cannot simulate the process under time limit of 1 sec. But notice that if the race track is of length N, then the number of times Subham will circle the whole track is equal to floor(K/N). That means he will complete circling the race tracks floor(K/N) times. And the remaining sections to be covered is equal to K modulo N . And K modulo N is less than N , so that means for he will cover a prefix of the race track.
So for the answer we can simply multiply the sum of hurdle values of the entire track with the number of times he completely circles the track.
And add it with sum of values prefix having K modulo N elements.
See setter solution for more details.
SOLUTIONS:
Setter's/Editorialist's Solution
#include<bits/stdc++.h>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);cin.tie(NULL);
#ifdef Zoro
freopen("/home/pritish/Competitive/in", "r", stdin);
freopen("/home/pritish/Competitive/out", "w", stdout);
#endif
int t;
cin>>t;
while(t--)
{
long long n,k;
cin>>n>>k;
long long a[n];
for (int i = 0; i < n; ++i)
{
cin>>a[i];
}
long long pref[n];
const long long mod=1e9+7;
pref[0]=a[0];
for (int i = 1; i < n; ++i)
{
pref[i]=(pref[i-1]+a[i])%mod;
}
long long full_turns=k/n,prefix=k%n;
long long ans=(pref[n-1]*full_turns)%mod;
if(prefix)ans=(ans+pref[prefix-1])%mod;
cout<<ans<<'\n';
}
cerr<<"\n"<<(float)clock()/CLOCKS_PER_SEC*1000<<" ms"<<endl;
return 0;
}
Tester's Solution
import java.util.*;import java.io.*;import java.math.*;
public class Main
{
public static void process()throws IOException
{
int n=ni();
int k=ni();
long[]A=nal(n);
long pref[]=new long[n+1];
for(int i=1;i<=n;i++)
pref[i]=(pref[i-1]+A[i-1])%mod;
long ans=(((pref[n]*(k/n))%mod)+pref[k%n])%mod;
pn(ans);
}
static long mod=(long)1e9+7l;
static AnotherReader sc;
static PrintWriter out;
public static void main(String[]args)throws IOException
{
boolean oj = true;
if(oj){sc=new AnotherReader();out=new PrintWriter(System.out);}
else{sc=new AnotherReader(100);out=new PrintWriter("output.txt");}
int t=1;
t=ni();
while(t-->0) {process();}
out.flush();out.close();
}
static void pn(Object o){out.println(o);}
static void p(Object o){out.print(o);}
static void pni(Object o){out.println(o);out.flush();}
static int ni()throws IOException{return sc.nextInt();}
static long nl()throws IOException{return sc.nextLong();}
static double nd()throws IOException{return sc.nextDouble();}
static String nln()throws IOException{return sc.nextLine();}
static int[] nai(int N)throws IOException{int[]A=new int[N];for(int i=0;i!=N;i++){A[i]=ni();}return A;}
static long[] nal(int N)throws IOException{long[]A=new long[N];for(int i=0;i!=N;i++){A[i]=nl();}return A;}
static long gcd(long a, long b)throws IOException{return (b==0)?a:gcd(b,a%b);}
static int gcd(int a, int b)throws IOException{return (b==0)?a:gcd(b,a%b);}
static int bit(long n)throws IOException{return (n==0)?0:(1+bit(n&(n-1)));}
/////////////////////////////////////////////////////////////////////////////////////////////////////////
static class AnotherReader{BufferedReader br; StringTokenizer st;
AnotherReader()throws FileNotFoundException{
br=new BufferedReader(new InputStreamReader(System.in));}
AnotherReader(int a)throws FileNotFoundException{
br = new BufferedReader(new FileReader("input.txt"));}
String next()throws IOException{
while (st == null || !st.hasMoreElements()) {try{
st = new StringTokenizer(br.readLine());}
catch (IOException e){ e.printStackTrace(); }}
return st.nextToken(); } int nextInt() throws IOException{
return Integer.parseInt(next());}
long nextLong() throws IOException
{return Long.parseLong(next());}
double nextDouble()throws IOException { return Double.parseDouble(next()); }
String nextLine() throws IOException{ String str = ""; try{
str = br.readLine();} catch (IOException e){
e.printStackTrace();} return str;}}
/////////////////////////////////////////////////////////////////////////////////////////////////////////////
}