In this post, HackerRank Turn Off the Lights Problem Solution.
There are n bulbs in a straight line, numbered from 0 to n – 1. Each bulb i has a button associated with it, and there is a cost. c. for pressing this button. When some button i is pressed, all the bulbs at a distance < & from bulb i will be toggled(off->on, on->off).
Given n. k, and the costs for each button, find and print the minimum cost of turning off all n bulbs if they’re all on initially.
Input Format
The first line contains two space-separated integers describing the respective values of n
and k.
The second line contains n space-separated integers describing the respective costs of each bulb (l.e., Co, C1,…, Cn-1).
Output Format
Print a long integer denoting the minimum cost of turning off all n bulbs.
Sample Input
3 1
1 1 1
Sample Output
1
Explanation
If we press the middle switch, the middle bulb and the k = 1 closest adjacent bulbs (i.e., the first and third) will turn off. Because all bulbs will be off in one button press, this cost is minimal. Thus, we print 1 as our answer.
Turn Off the Lights C++ Solution
#include <string>
#include <vector>
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<stack>
#include<queue>
#include<cmath>
#include<algorithm>
#include<functional>
#include<list>
#include<deque>
#include<bitset>
#include<set>
#include<map>
#include<unordered_map>
#include<cstring>
#include<sstream>
#include<complex>
#include<iomanip>
#include<numeric>
#include<cassert>
#define X first
#define Y second
#define pb push_back
#define rep(X,Y) for (int (X) = 0;(X) < (Y);++(X))
#define reps(X,S,Y) for (int (X) = S;(X) < (Y);++(X))
#define rrep(X,Y) for (int (X) = (Y)-1;(X) >=0;--(X))
#define repe(X,Y) for ((X) = 0;(X) < (Y);++(X))
#define peat(X,Y) for (;(X) < (Y);++(X))
#define all(X) (X).begin(),(X).end()
#define rall(X) (X).rbegin(),(X).rend()
#define eb emplace_back
#define UNIQUE(X) (X).erase(unique(all(X)),(X).end())
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
template<class T> using vv=vector<vector<T>>;
template<class T> ostream& operator<<(ostream &os, const vector<T> &t) {
os<<"{"; rep(i,t.size()) {os<<t[i]<<",";} os<<"}"<<endl; return os;}
template<class S, class T> ostream& operator<<(ostream &os, const pair<S,T> &t) { return os<<"("<<t.first<<","<<t.second<<")";}
template<class T> inline bool MX(T &l,const T &r){return l<r?l=r,1:0;}
template<class T> inline bool MN(T &l,const T &r){return l>r?l=r,1:0;}
const ll MOD=1e9+7;
const ll INF=1e14;
int main(){
ios_base::sync_with_stdio(false);
cout<<fixed<<setprecision(0);
int n,t;
cin>>n>>t;
vv<pll> g(n+1);
vector<int> c(n);
rep(i,n) cin>>c[i];
ll re=INF;
rep(i,min(n,t+1)){
ll sum=0,rb=0;
for(int j=i;j<n;j+=2*t+1){
sum+=c[j];
rb=j+t;
}
if(rb>=n-1) MN(re,sum);
}
cout<<re<<endl;
return 0;
}Turn Off the Lights C Sharp Solution
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace ProblemSolver
{
class Solution
{
static char[] splitors = { ' ' };
/* Input data here */
static int n;
static int k;
static long[] c;
static void Input()
{
string[] str = Console.ReadLine().Split(splitors);
n = int.Parse(str[0]);
k = int.Parse(str[1]);
str = Console.ReadLine().Split(splitors);
c = new long[n];
for (int i = 0; i < n; i++)
{
c[i] = long.Parse(str[i]);
}
}
static void Search()
{
long[] cost = new long[n];
for (int i = 0; i < n; i++)
{
cost[i] = -1;
}
cost[n - 1] = 0;
for (int i = n - 2; i >= 0; i--)
{
int next = i + k + 1;
if (next < n)
{
int j = Math.Min(next + k, n - 1);
// for (int j = i + 1; j <= next + k && j < n; j++)
if (cost[j] != -1)
{
if (cost[i] == -1)
{
cost[i] = cost[j] + c[next];
}
else
{
cost[i] = Math.Min(cost[i], cost[j] + c[next]);
}
}
}
}
long ret = -1;
for (int last = 0; last <= k && last < n; last++)
{
int j = Math.Min(last + k, n - 1);
//for (int j = 0; j <= last + k && j < n; j++)
if (cost[j] != -1)
{
long val = cost[j] + c[last];
if (ret == -1)
{
ret = val;
}
else
{
ret = Math.Min(ret, val);
}
}
}
Console.WriteLine(ret);
}
static void Main(string[] args)
{
Input();
Search();
}
}
}Turn Off the Lights Java Solution
import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
public class Solution {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int k = sc.nextInt();
int[] c = new int[n];
for (int i = 0; i < n; i++) {
c[i] = sc.nextInt();
}
long ans = 1000000000000000000l;
for (int i = 0; i <= Math.min(n-1, k); i++) {
int maxCovered = i+k;
long partialAns = c[i];
boolean possible = true;
while (maxCovered < n-1) {
int button = maxCovered+k+1;
if (button >= n) {
possible = false;
break;
}
partialAns += c[button];
maxCovered = button+k;
}
if (!possible)
continue;
ans = Math.min(partialAns, ans);
}
System.out.println(ans);
}
}Turn Off the Lights Python Solution
n, k = map(int, raw_input().split())
c = map(int, raw_input().split())
dp = [float('inf') for i in xrange(n+ 1)]
dp[0] = 0
for i in xrange(1, n+1):
dp[min(i+k, n)] = min(dp[min(i+k, n)], dp[max(i-k-1, 0)] + c[i-1])
#print dp
print dp[n]
