Turn Off the Lights
Problem Statement :
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,ci , for pressing this button. When some button i is pressed, all the bulbs at a distance <= k from bulb 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 (i.e., c0,c1,c2,...,cn-1). Constraints 3 <= n <= 10^4 0 <= k <= 1000 0 <= ci <= 10^9 Output Format Print a long integer denoting the minimum cost of turning off all n bulbs.
Solution :
Solution in C :
In C++ :
/*
*/
#pragma comment(linker, "/STACK:16777216")
#define _CRT_SECURE_NO_WARNINGS
#include <fstream>
#include <iostream>
#include <string>
#include <complex>
#include <math.h>
#include <set>
#include <vector>
#include <map>
#include <queue>
#include <stdio.h>
#include <stack>
#include <algorithm>
#include <list>
#include <ctime>
#include <memory.h>
#include <assert.h>
#define y0 sdkfaslhagaklsldk
#define y1 aasdfasdfasdf
#define yn askfhwqriuperikldjk
#define j1 assdgsdgasghsf
#define tm sdfjahlfasfh
#define lr asgasgash
#define norm asdfasdgasdgsd
#define eps 1e-9
#define M_PI 3.141592653589793
#define bs 1000000007
#define bsize 350
using namespace std;
const int INF = 1e9;
const int N = 200031;
int n, k, ar[N];
long long solve(int start)
{
long long res = 0;
for (int i = start; i <= n; i += 2 * k + 1)
{
res += ar[i];
if (i + k + 1 <= n&&i + k * 2 + 1 > n)
return 1e18;
}
return res;
}
bool good_mask(int mask)
{
int ar[25];
for (int i = 0; i < n; i++)
{
ar[i] = 1;
}
for (int i = 0; i < n; i++)
{
if (mask&(1 << i))
{
for (int j = i - k; j <= i + k; j++)
{
if (j >= 0 && j < n)
ar[j] ^= 1;
}
}
}
for (int i = 0; i < n; i++)
{
if (ar[i])
return 0;
}
return 1;
}
int ans_mask;
int main(){
//freopen("fabro.in","r",stdin);
//freopen("fabro.out","w",stdout);
//freopen("F:/in.txt", "r", stdin);
//freopen("F:/output.txt", "w", stdout);
ios_base::sync_with_stdio(0);
//cin.tie(0);
while (true)
{
cin >> n >> k;
for (int i = 1; i <= n; i++)
{
cin >> ar[i];
//ar[i] = rand() % 10;
}
long long ans = 1e18;
/*for (int mask = 0; mask < (1 << n); mask++)
{
if (good_mask(mask))
{
int here = 0;
for (int i = 0; i < n; i++)
{
if (mask&(1 << i))
here += ar[i + 1];
}
if (here < ans)
ans = min(ans, 0ll + here),
ans_mask = mask;
}
}*/
long long ans2 = 1e18;
for (int F = 1; F <= k + 1&&F<=n; F++)
{
ans2 = min(ans2, solve(F));
}
/*if (ans != ans2)
{
cout << "!" << endl;
for (int i = 1; i <= n; i++)
{
cout << ar[i] << " ";
}
cout << endl;
cout << ans << " " << ans2 << " " << ans_mask << endl;
while (true);
}
else
cout << "OK" << endl;*/
cout << ans2 << endl;
return 0;
}
cin.get(); cin.get();
return 0;
}
In Java :
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);
}
}
View More Similar Problems
Array-DS
An array is a type of data structure that stores elements of the same type in a contiguous block of memory. In an array, A, of size N, each memory location has some unique index, i (where 0<=i<N), that can be referenced as A[i] or Ai. Reverse an array of integers. Note: If you've already solved our C++ domain's Arrays Introduction challenge, you may want to skip this. Example: A=[1,2,3
View Solution →2D Array-DS
Given a 6*6 2D Array, arr: 1 1 1 0 0 0 0 1 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 An hourglass in A is a subset of values with indices falling in this pattern in arr's graphical representation: a b c d e f g There are 16 hourglasses in arr. An hourglass sum is the sum of an hourglass' values. Calculate the hourglass sum for every hourglass in arr, then print t
View Solution →Dynamic Array
Create a list, seqList, of n empty sequences, where each sequence is indexed from 0 to n-1. The elements within each of the n sequences also use 0-indexing. Create an integer, lastAnswer, and initialize it to 0. There are 2 types of queries that can be performed on the list of sequences: 1. Query: 1 x y a. Find the sequence, seq, at index ((x xor lastAnswer)%n) in seqList.
View Solution →Left Rotation
A left rotation operation on an array of size n shifts each of the array's elements 1 unit to the left. Given an integer, d, rotate the array that many steps left and return the result. Example: d=2 arr=[1,2,3,4,5] After 2 rotations, arr'=[3,4,5,1,2]. Function Description: Complete the rotateLeft function in the editor below. rotateLeft has the following parameters: 1. int d
View Solution →Sparse Arrays
There is a collection of input strings and a collection of query strings. For each query string, determine how many times it occurs in the list of input strings. Return an array of the results. Example: strings=['ab', 'ab', 'abc'] queries=['ab', 'abc', 'bc'] There are instances of 'ab', 1 of 'abc' and 0 of 'bc'. For each query, add an element to the return array, results=[2,1,0]. Fun
View Solution →Array Manipulation
Starting with a 1-indexed array of zeros and a list of operations, for each operation add a value to each of the array element between two given indices, inclusive. Once all operations have been performed, return the maximum value in the array. Example: n=10 queries=[[1,5,3], [4,8,7], [6,9,1]] Queries are interpreted as follows: a b k 1 5 3 4 8 7 6 9 1 Add the valu
View Solution →