Access solutions of "Code Gladiators" Contest organized on HackerRank and held by TSoC in IIITNR.
WEEK-1
Rank Realization
Problem: Determine the count of participants with ratings strictly higher than Divyansh's rating.
Input:
- Divyansh's rating (r).
- Number of participants (n).
- Array arr containing ratings of other participants.
Approach:
- Read r, n, and arr.
- Counting Higher Ratings: — Initialize a counter variable counter to 0. — Iterate through each rating in arr. — If the rating is strictly higher than r, increment counter.
Output:
- Print the value of counter, representing the number of participants with ratings strictly higher than Divyansh.
Python
r = int(input())
n = int(input())
arr = list(map(int, input().split()))
counter = 0
for rating in arr:
if rating > r:
counter += 1
print(counter)
C++
#include <iostream>
#include <vector>
using namespace std;
int main() {
int r, n;
cin >> r >> n;
vector<int> arr(n);
for(int i = 0; i < n; i++) {
cin >> arr[i];
}
int counter = 0;
for(int i = 0; i < n; i++) {
if(arr[i] > r) {
counter++;
}
}
cout << counter << endl;
return 0;
}
Java
import java.util.*;
public class RankRealization {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int r = sc.nextInt();
int n = sc.nextInt();
int[] arr = new int[n];
for(int i=0;i<n;i++) arr[i] = sc.nextInt();
int counter=0;
for(int i=0;i<n;i++){
if(arr[i]>r) counter++;
}
System.out.println(counter);
}
}
Gareeb Romeo
- Input Reading:
- Read the number of streets
n
and avenuesm
. - Read the cost of dinner for each restaurant into a 2D array
array[n][m]
. Juliet's Strategy:
- For each street, find the minimum cost of dinner among all restaurants on that street.
- Keep track of these minimum costs in an array
z
. Romeo's Strategy:
- Among the minimum costs found for each street, find the maximum cost.
- This represents the cost of dinner that Romeo can minimize while Juliet chooses her street optimally.
Output:
- Print the maximum cost found in step 3, which represents the cost of dinner that Juliet can choose while Romeo minimizes it.
Python
n, m = map(int, input().split())
array = [list(map(int, input().split())) for _ in range(n)]
z = [min(row) for row in array]
s = max(z)
print(s)
C++
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n, m, a = 0, b = 0;
cin >> n >> m;
int array[n][m];
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
cin >> array[i][j];
}
}
int z[n];
for (int i = 0; i < n; i++)
{
z[i] = INT_MAX;
for (int j = 0; j < m; j++)
{
z[i] = min(z[i], array[i][j]);
}
}
int s = INT_MIN;
for (int i = 0; i < n; i++)
{
s = max(s, z[i]);
}
cout << s;
return 0;
}
Java
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int m = scanner.nextInt();
int[][] array = new int[n][m];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
array[i][j] = scanner.nextInt();
}
}
int[] z = new int[n];
for (int i = 0; i < n; i++) {
int min = Integer.MAX_VALUE;
for (int j = 0; j < m; j++) {
min = Math.min(min, array[i][j]);
}
z[i] = min;
}
int s = Integer.MIN_VALUE;
for (int i = 0; i < n; i++) {
s = Math.max(s, z[i]);
}
System.out.println(s);
scanner.close();
}
}
Arcade
- Input Reading:
- Read the number of test cases
t
. - For each test case:
- Read the number of game machines
n
and the amount of money Divyansh hasc
. - Read the cost of using move 2 for each machine into an array.
- Read the number of game machines
Calculating Total Costs:
- For each machine, calculate the total cost of using move 2 by adding the machine's cost with its position (1-indexed).
Sorting Total Costs:
- Sort the total costs of using move 2 for each machine in non-decreasing order.
Counting Goodies:
- Initialize a variable to count the number of goodies Divyansh collects.
- Iterate over each machine's total cost:
- If Divyansh has enough money to use move 2 for the current machine:
- Increment the count of goodies collected.
- Subtract the total cost of using move 2 for the current machine from Divyansh's money.
- Continue this process until either Divyansh runs out of money or all machines are checked.
Output:
- Print the count of goodies collected, representing the maximum number of goodies Divyansh can collect for each test case.
Python
# Python
t = int(input())
for _ in range(t):
n, c = map(int, input().split())
arr = list(map(int, input().split()))
brr = [arr[i] + i + 1 for i in range(n)]
brr.sort()
ans = 0
for cost in brr:
if c - cost >= 0:
ans += 1
c -= cost
else:
break
print(ans)
C++
// C++
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
int n;
long long c;
cin >> n >> c;
vector<long long> arr(n);
vector<long long> brr(n);
for (int i = 0; i < n; ++i) {
cin >> arr[i];
brr[i] = arr[i] + i + 1;
}
sort(brr.begin(), brr.end());
int ans = 0;
for (int i = 0; i < n; ++i) {
if (c - brr[i] >= 0) {
++ans;
c -= brr[i];
} else {
break;
}
}
cout << ans << endl;
}
return 0;
}
Java
import java.util.*;
import java.util.Arrays;
public class CP{
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
long t = sc.nextInt();
while(t-->0){
int n = sc.nextInt();
long c = sc.nextLong();
long[] arr = new long[n];
long[] brr = new long[n];
for(int i=0;i<n;i++){
arr[i] = sc.nextLong();
brr[i] = arr[i]+i+1;
}
Arrays.sort(brr);
long ans=0;
for(int i=0;i<n;i++){
if(c-brr[i]>=0){
ans++;
c-=brr[i];
}
}
System.out.println(ans);
}
}
}
El Classico Bet
Intuition: The problem can be simplified into finding the minimum of the sum of the smallest (k−1)th elements in a continuous subarray of length dist+1.
Approach: We can use two sets, one storing first (k−1)th smallest element, while the second set storing the rest. When itterating through the array, we can remove an element and insert an element into one of these sets in O(log n) time. Then we can use another variable to store the sum of the first set, updating it each time an element is inserted or erased.
Python
def minimumCost(nums, k, dist):
n = len(nums)
window = nums[1: 1 + dist] # Initial window
window.sort() # Sort the initial window
cursum, minsum = sum(window[: k - 2]), float('inf')
for i in range(1 + dist, n):
# Manually find insertion index using linear search
insert_index = 0
while insert_index < len(window) and window[insert_index] < nums[i]:
insert_index += 1
if insert_index <= k - 2:
cursum += nums[i]
else:
cursum += window[k - 2]
minsum = min(minsum, cursum)
# Insert and remove elements while keeping window sorted
window.insert(insert_index, nums[i])
remove_index = window.index(nums[i - dist])
window.pop(remove_index)
if remove_index <= k - 2:
cursum -= nums[i - dist]
else:
cursum -= window[k - 2]
return nums[0] + minsum
n = int(input())
nums = list(map(int, input().split()))
k = int(input())
dist = int(input())
print(minimumCost(nums, k, dist))
C++
#include <iostream>
#include <vector>
#include <set>
using namespace std;
class Solution {
multiset<long long> l, r;
public:
long long minimumCost(vector<int>& nums, int k, int dist) {
int n = nums.size();
// picking up the first number
k--;
long long cur = nums[0];
// picking up all the valid index considering we take all the index in consecutive order
for (int i = 1; i <= dist + 1; i++) cur += nums[i], l.insert(nums[i]);
// if we get more than k elements then we delete it. But before doing so we keep it in r set (reason is we tend to keep elements in r which we don't use in l)
while (l.size() > k) {
cur -= *l.rbegin();
r.insert(*l.rbegin());
l.erase(l.find(*l.rbegin()));
}
// so we got the min sum of the first dist + 1 elements using sliding window. Now let's slide through the rest of the array
// ans is the minimum sum of the first element of k subarrays meeting all the conditions
long long ans = cur;
// summary: at every index, we try to put it in our l set so that we can get the minimum ans.
for (int i = dist + 2; i < n; i++) {
// Erasing an element from the set
// i - dist - 1 is the second element. If it will be present in the array then we cannot pick the ith element, so remove it.
if (l.find(nums[i - dist - 1]) != l.end()) {
cur -= nums[i - dist - 1];
l.erase(l.find(nums[i - dist - 1]));
} else {
// if the second element is not present in l set so we have to remove it from r set too. This is done because we don't wanna choose that element in the future of this for loop
// because it will destroy the condition of kth index - 1st index is less than or equal to dist if we.
r.erase(r.find(nums[i - dist - 1]));
}
// Adding an element to the set
// Now we try to add that element that is ith
if (nums[i] < *l.rbegin()) {
cur += nums[i];
l.insert(nums[i]);
} else {
r.insert(nums[i]);
}
// Balancing the set such that the first set has (k - 1) elements
while (l.size() < k) {
cur += *r.begin();
l.insert(*r.begin());
r.erase(r.find(*r.begin()));
}
while (l.size() > k) {
cur -= *l.rbegin();
r.insert(*l.rbegin());
l.erase(l.find(*l.rbegin()));
}
// Finally, update the minimum
ans = min(ans, cur);
}
return ans;
}
};
int main() {
int n, k, dist;
cin >> n;
vector<int> nums(n);
for (int i = 0; i < n; ++i)
cin >> nums[i];
cin >> k >> dist;
Solution sol;
long long result = sol.minimumCost(nums, k, dist);
cout << result << endl;
return 0;
}
Java
import java.util.*;
class Solution {
public long minimumCost(int[] nums, int k, int dist) {
long result = Long.MAX_VALUE, windowSum = 0l;
int n = nums.length;
TreeSet<Integer> using = new TreeSet<>((a, b) -> nums[a] == nums[b] ? a - b : nums[a] - nums[b]);
TreeSet<Integer> waiting = new TreeSet<>((a, b) -> nums[a] == nums[b] ? a - b : nums[a] - nums[b]);
// Add dist + 1 num into the using set
for(int i = 1; i <= dist + 1; i++){
using.add(i);
windowSum += nums[i];
}
// We need only k - 1 nums, move others to waiting set because we might need them in the future
while(using.size() > k - 1){
int i = using.pollLast();
windowSum -= nums[i];
waiting.add(i);
}
// windowSum is the sum of k - 1 nums
result = Math.min(result, windowSum);
for(int i = 1; i + dist + 1 < n; i++){
// window slided so add new num to the waiting set
waiting.add(i + dist + 1);
// i is the left most num in the window, will be removed from window
if(using.contains(i)){
// i is one of the k - 1 num
// remove and update windowSum
// poll one num from waiting set and add
windowSum -= nums[i];
using.remove(i);
int j = waiting.pollFirst();
windowSum += nums[j];
using.add(j);
}else{
// i is not one of the k - 1 num, it is in the waiting set
// remove from waiting
// check minimum num of the waiting set is lower than maximum num of the using set
// If so, add to the using set, remove from waiting set
// update window accordingly
waiting.remove(i);
int j1 = waiting.first(), j2 = using.last();
if(nums[j1] < nums[j2]){
windowSum -= nums[j2];
using.remove(j2);
waiting.add(j2);
windowSum += nums[j1];
using.add(j1);
waiting.remove(j1);
}
}
result = Math.min(result, windowSum);
}
return result + nums[0];
}
}
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int[] nums = new int[n];
for (int i = 0; i < n; i++) {
nums[i] = scanner.nextInt();
}
int k = scanner.nextInt();
int dist = scanner.nextInt();
Solution sol = new Solution();
long result = sol.minimumCost(nums, k, dist);
System.out.println(result);
scanner.close();
}
}
WEEK-2
Breakfast 1
- Problem: Rahul wants to make sandwiches for breakfast. Each sandwich consists of layers of bread, cheese, and/or ham.
- Constraints: Rahul has a limited number of bread, cheese, and ham slices.
- Objective: Find the maximum number of layers Rahul can make given the available ingredients.
- Approach:
- The number of layers is determined by the minimum of bread, cheese, and ham slices available.
- The maximum number of layers can be achieved by alternating bread with cheese/ham.
- If Rahul has enough cheese and ham to alternate between them, the number of layers will be the sum of bread, cheese, and ham minus one.
- If Rahul doesn't have enough cheese and ham to alternate, he can use all available cheese and ham slices, and add one bread slice on each end, resulting in double the sum of cheese and ham slices, plus one.
Python
t = int(input())
for _ in range(t):
b, c, h = map(int, input().split())
if c + h >= b - 1:
print(2 * b - 1)
else:
print(2 * (c + h) + 1)
C++
#include <iostream>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
int b, c, h;
cin >> b >> c >> h;
if (c + h >= b - 1) {
cout << 2 * b - 1 << endl;
} else {
cout << 2 * (c + h) + 1 << endl;
}
}
return 0;
}
Java
import java.util.Scanner;
public class Breakfast {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
while(t-->0){
int b = sc.nextInt();
int c = sc.nextInt();
int h = sc.nextInt();
if(c+h>=b-1){
System.out.println(2*b-1);
}else{
System.out.println(2*(c+h)+1);
}
}
}
}
Maharaja Mac gig
Here's a summarized explanation of the provided code, following the format used previously:
Problem Statement: Awatansh wants to win a McD gift voucher by solving a problem Divyansh got stuck on. The problem involves designing a string S of minimum length that can be converted to the given string U using any number of operations.
Input:
- The first line of input contains the number of test cases, T.
- For each test case:
- The first line consists of an integer N, the length of the string U.
- The next line contains string U.
Approach:
- For each test case, the code generates a string S such that it contains each distinct character in U exactly once.
- Since a character can be replaced with three occurrences of itself in one operation, only one occurrence of each character in U needs to be included in S.
Test Case:
- For the first test case, the string U is "aaabbb". The minimum length string S that can be converted to U is "ab".
- Similarly, for the second and third test cases, the minimum length strings S are "abc" and "abcd", respectively.
Python
t = int(input())
for _ in range(t):
n = int(input())
str_input = input().strip()
ans = ""
counter = 1
for i in range(n-1):
if str_input[i] == str_input[i+1]:
counter += 1
else:
if counter % 2 == 0:
ans += str_input[i] * 2
else:
ans += str_input[i]
counter = 1
if counter % 2 == 0:
ans += str_input[n-1] * 2
else:
ans += str_input[n-1]
print(ans)
C++
#include <iostream>
#include <string>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
string str;
cin >> str;
string ans;
int counter = 1;
for (int i = 0; i < n - 1; ++i) {
if (str[i] == str[i + 1]) {
counter++;
} else {
if (counter % 2 == 0) {
ans += str[i];
ans += str[i];
} else {
ans += str[i];
}
counter = 1;
}
}
if (counter % 2 == 0) {
ans += str[n - 1];
ans += str[n - 1];
} else {
ans += str[n - 1];
}
cout << ans << endl;
}
return 0;
}
Java
import java.util.Scanner;
public class Cp {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
while(t-->0){
int n = sc.nextInt();
sc.nextLine();
String str = sc.nextLine();
String ans = "";
int counter =1;
for(int i=0;i<n-1;i++){
if(str.charAt(i)==str.charAt(i+1)){
counter++;
}else{
if(counter%2==0){
ans += str.charAt(i);
ans += str.charAt(i);
}else{
ans += str.charAt(i);
}
counter=1;
}
}
if(counter%2==0){
ans += str.charAt(n-1);
ans += str.charAt(n-1);
}else{
ans += str.charAt(n-1);
}
System.out.println(ans);
}
}
}
Pokemon Go
- Input Reading:
- The program first reads the number of Pokémon in the lab, denoted by 'n', and their respective strengths provided in the next line.
Counting Pokémon Strengths:
- It initializes an array
d
to store the count of Pokémon with each strength. - Then, it iterates over the provided strengths and counts how many Pokémon have each strength.
Finding Maximum Number of Pokémon:
- It sets
ans
(the answer) initially to 1. - Then, it iterates through each possible strength value, starting from 2.
- For each strength value
i
, it calculates how many Pokémon have a strength divisible byi
. It does this by counting the occurrences of strengths that are multiples ofi
. - It updates
ans
to the maximum of its current value and the count obtained in the previous step. Output:
- Finally, it prints the maximum count of Pokémon (
ans
) that can be taken without any of them being likely to fight, considering their strengths.
In simpler terms, the program reads the strengths of Pokémon, counts how many Pokémon have each strength, and then finds the maximum number of Pokémon that can be taken without any two of them having a common divisor greater than 1 (which might make them likely to fight). It achieves this by finding the maximum count of Pokémon with strengths that have no common divisor greater than 1.
Python
import sys
input = sys.stdin.readline
print = sys.stdout.write
n = int(input())
a = [int(x) for x in input().split()]
mxN = 10 ** 5 + 5
d = [0] * mxN
for i in a:
d[i] += 1
ans = 1
for i in range(2, mxN):
cnt = 0
for j in range(i, mxN, i):
cnt += d[j]
ans = max(ans, cnt)
print(str(ans))
C++
#include <iostream>
#include <unordered_map>
#include <cmath>
using namespace std;
int main() {
int N;
cin >> N;
unordered_map<int, int> factors;
for (int k = 0; k < N; ++k) {
int strength;
cin >> strength;
int root = sqrt(strength);
int i = 2;
while (i <= root) {
if (strength % i == 0) {
if (factors.find(i) != factors.end()) {
factors[i]++;
} else {
factors[i] = 1;
}
while (strength % i == 0) {
strength /= i;
}
}
i++;
}
if (strength > 1) {
if (factors.find(strength) != factors.end()) {
factors[strength]++;
} else {
factors[strength] = 1;
}
}
}
int ans = 1;
for (auto const &entry : factors) {
ans = max(ans, entry.second);
}
cout << ans << endl;
return 0;
}
Java
```java
```
Mission Freshers
Problem: Harshit wants to attend a freshers' party, but the hostel warden, Anurag Sir, has set up a coding challenge for him. Anurag Sir has chosen two positive integers: one of them is known to Harshit (denoted by k), and the other one (denoted by x) is a mystery. Harshit's task is to figure out the remainder when x is divided by k. Anurag Sir gives Harshit the freedom to ask about x modulo (remainder after division by) any number from a list of ancient numbers. Harshit wants to know if he can figure out x modulo k using this strategy.
Explanation:
- Harshit is given a list of ancient numbers and a specific number k chosen by Anurag Sir.
- Harshit calculates the least common multiple (LCM) of all the ancient numbers. The LCM is the smallest number that is a multiple of all the given ancient numbers.
- If the LCM equals k, it means that Harshit can figure out x modulo k for any positive integer x using the ancient numbers. This is because the LCM essentially represents a number that is divisible by all the ancient numbers.
- If the LCM is not equal to k, it means there exists some positive integer x such that x modulo k cannot be determined using the ancient numbers. This is because the LCM may not be a multiple of k, indicating that there are values of x for which the remainder after dividing by k cannot be deduced from the ancient numbers.
Conclusion: Harshit has a winning strategy (can figure out x modulo k for any positive integer x) if the LCM of the ancient numbers is equal to k. Otherwise, he does not have a winning strategy.
Python
# Add code
C++
#include <iostream>
int gcd(int a, int b) {
while (a > 0 && b > 0) {
if (a > b) {
a %= b;
} else {
b %= a;
}
}
return a + b;
}
int lcm(int a, int b) {
return a / gcd(a, b) * b;
}
int main() {
int n, k;
std::cin >> n >> k;
int l = 1;
for (int i = 0; i < n; i++) {
int x;
std::cin >> x;
int g = gcd(x, k);
l = lcm(l, g);
}
std::cout << (l == k ? "Yes" : "No") << std::endl;
return 0;
}
Java
import java.util.Scanner;
public class Main {
public static int gcd(int a, int b) {
while (a > 0 && b > 0) {
if (a > b) {
a %= b;
} else {
b %= a;
}
}
return a + b;
}
public static int lcm(int a, int b) {
return a / gcd(a, b) * b;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int k = scanner.nextInt();
int l = 1;
for (int i = 0; i < n; i++) {
int x = scanner.nextInt();
int g = gcd(x, k);
l = lcm(l, g);
}
System.out.println(l == k ? "Yes" : "No");
scanner.close();
}
}
WEEK-3
Flashmob 1
You have a list of when each person is supposed to show up, and you also have a deadline by which everyone must arrive. To check if the flashmob can start on time, you look at the latest arrival time among all participants. If this latest arrival time is before or at the deadline, then everyone has arrived on time, and the flashmob can start on schedule. However, if the latest arrival time is after the deadline, it means someone is late, and the flashmob will have to wait, causing a delay. So, essentially, you're just making sure that everyone gets there before the clock runs out!
Python
n = int(input())
arr = list(map(int, input().split()))
th = int(input())
max_value = max(arr)
if max_value <= th:
print("True")
else:
print("False")
C++
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> arr(n);
for (int i = 0; i < n; ++i) {
cin >> arr[i];
}
int th;
cin >> th;
int max_value = *max_element(arr.begin(), arr.end());
if (max_value <= th) {
cout << "True" << endl;
} else {
cout << "False" << endl;
}
return 0;
}
Java
import java.io.*;
import java.util.*;
public class Flashmob {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int arr[] = new int[n];
for(int i=0;i<n;i++){
arr[i] = sc.nextInt();
}
int th = sc.nextInt();
int max =0;
for(int i=0;i<n;i++){
if(arr[i]>max) max = arr[i];
}
if(max<=th) System.out.println("True");
else System.out.println("False");
}
}
Contest Management
- Input:
- Get the total number of problem statements (t).
- Gather the difficulty estimates for each problem.
- Obtain the minimum and maximum total difficulty required for the problem set (mn and mx).
- Get the minimum difference between the easiest and hardest problem (z).
Counting Problem Sets:
- Sort the difficulty estimates for the problems.
- Iterate through all possible combinations of problems.
- For each combination, calculate the total difficulty and check if it falls within the specified range [mn, mx].
- Additionally, ensure that the difference between the easiest and hardest problem is at least z.
- If these conditions are met, increment the count of valid problem sets.
Output:
- Print the total number of valid problem sets that meet the given conditions.
In essence, the code finds all possible combinations of problems and checks if they meet the difficulty requirements specified. If they do, it counts them as valid problem sets. Finally, it outputs the total count of such valid problem sets.
Python
def main():
n = int(input())
c = list(map(int, input().split()))
l, r, x = map(int, input().split())
c.sort()
cnt = 0
a = b = -1
for i in range(1, 1 << n):
total = 0
for j in range(n):
if i & (1 << j):
total += c[j]
if a == -1:
a = j
else:
b = j
if l <= total <= r and b != -1 and a != -1:
if c[b] - c[a] >= x:
cnt += 1
a = b = -1
print(cnt)
if __name__ == "__main__":
main()
C++
#include <bits/stdc++.h>
using namespace std;
int main(){
int n,l,r,x;
cin >> n ;
int c[n];
for (int i=0; i<n; ++i){
cin >> c[i];
}
cin>>l>>r>>x;
sort(c,c+n);
long long cnt=0,a=-1,b=-1;
for (int i=1; i<=(1LL << n) ; ++i){
long long sum=0;
for (int j=0; j<n; ++j){
if ((1LL<<j)&i) {
sum+= c[j];
if (a==-1) a=j;
else b=j;
}
}
if (sum>=l && sum<=r && b!=-1 && a!=-1) {
if ((c[b] - c[a]) >= x) ++cnt;
}
a=-1;
b=-1;
}
cout << cnt << '\n';
}
Java
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] c = new int[n];
for (int i = 0; i < n; ++i) {
c[i] = sc.nextInt();
}
int l = sc.nextInt();
int r = sc.nextInt();
int x = sc.nextInt();
Arrays.sort(c);
long cnt = 0;
int a = -1, b = -1;
for (int i = 1; i < (1 << n); ++i) {
long total = 0;
for (int j = 0; j < n; ++j) {
if ((i & (1 << j)) != 0) {
total += c[j];
if (a == -1) a = j;
else b = j;
}
}
if (total >= l && total <= r && b != -1 && a != -1) {
if (c[b] - c[a] >= x) ++cnt;
}
a = b = -1;
}
System.out.println(cnt);
}
}
MultiBit
- Understanding the Sequence:
- Pranjal has a sequence of numbers.
- The sequence initially has 2^n non-negative integers.
Reducing the Sequence:
- Pranjal reduces the sequence iteratively:
- First, he performs OR operations on adjacent pairs of numbers in the sequence.
- Then, he performs an exclusive OR (XOR) operation on the results of the OR operations.
- He continues this process until only one number remains in the sequence, which we'll call S.
Performing Queries:
- Pranjal receives queries in the form of pairs of integers (p, b).
- Each query instructs Pranjal to update the value of a particular element in the sequence. For example, a(p) = b means the value at position p in the sequence should be updated to b.
Calculating S After Each Query:
- After each query, Pranjal needs to calculate the new value of S for the updated sequence.
- This involves performing the same reduction process (OR and XOR operations) on the updated sequence until only one number remains.
Output:
- For each query, Pranjal prints the new value of S after updating the sequence according to the query.
In summary, Pranjal starts with a sequence of numbers, reduces it iteratively using OR and XOR operations, and then updates the sequence based on queries while recalculating the final result, S, after each update.
Python
class ST:
def __init__(self, n):
self.st = [0] * (2 * n)
self.n = n
for i in range(n, len(self.st)):
self.st[i] = int(input())
start = n >> 1
exc = False
while start > 0:
for i in range(start, start << 1):
if exc:
self.st[i] = self.st[i << 1] ^ self.st[(i << 1) | 1]
else:
self.st[i] = self.st[i << 1] | self.st[(i << 1) | 1]
start >>= 1
exc = not exc
def update(self, i, v):
i += self.n
self.st[i] = v
while i > 0:
exc = False
i >>= 1
if exc:
self.st[i] = self.st[i << 1] ^ self.st[(i << 1) | 1]
else:
self.st[i] = self.st[i << 1] | self.st[(i << 1) | 1]
return self.st[1]
if __name__ == "__main__":
n, m = map(int, input().split())
n = 1 << n
st = ST(n)
for _ in range(m):
p, b = map(int, input().split())
print(st.update(p - 1, b))
C++
#include <bits/stdc++.h>
using namespace std;
#define _ \
ios_base::sync_with_stdio(false); \
cin.tie(0); \
cout.tie(0)
#define deb(x) cout << #x << ": " << (x) << '\n';
#define fore(i, a, b) for (lli i = a, ___limit___ = b; i < ___limit___; ++i)
using lli = long long int;
using vi = vector<lli>;
using vb = vector<bool>;
struct ST {
vi st{};
lli n{};
ST(lli n) : n(n) {
st.resize(2 * n, 0);
fore(i, n, st.size()) cin >> st[i];
for (lli start{n >> 1}, exc{false}; start > 0; start >>= 1, exc = !exc) {
fore(i, start, start << 1) {
if (exc)
st[i] = st[i << 1] ^ st[(i << 1) | 1];
else
st[i] = st[i << 1] | st[(i << 1) | 1];
}
}
}
lli update(lli i, lli v) {
i += n;
st[i] = v;
i >>= 1;
for (bool exc{false}; i > 0; i >>= 1, exc = !exc) {
if (exc)
st[i] = st[i << 1] ^ st[(i << 1) | 1];
else
st[i] = st[i << 1] | st[(i << 1) | 1];
}
return st[1];
}
};
int main() {
_;
lli n{}, m{}, p{}, b{};
cin >> n >> m;
n = 1 << n;
ST st(n);
while (m--) {
cin >> p >> b;
cout << st.update(p - 1, b) << '\n';
}
return EXIT_SUCCESS;
}
Java
import java.util.*;
class ST {
private List<Long> st = new ArrayList<>();
private long n;
ST(long n) {
this.n = n;
st = new ArrayList<>(Collections.nCopies((int) (2 * n), 0L));
for (int i = (int) n; i < st.size(); i++) {
st.set(i, (long) new Scanner(System.in).nextInt());
}
long start = n >> 1;
boolean exc = false;
while (start > 0) {
for (int i = (int) start; i < start << 1; i++) {
if (exc) {
st.set(i, st.get(i << 1) ^ st.get((i << 1) | 1));
} else {
st.set(i, st.get(i << 1) | st.get((i << 1) | 1));
}
}
start >>= 1;
exc = !exc;
}
}
long update(long i, long v) {
i += n;
st.set((int) i, v);
while (i > 0) {
boolean exc = false;
i >>= 1;
if (exc) {
st.set((int) i, st.get((int) (i << 1)) ^ st.get((int) ((i << 1) | 1)));
} else {
st.set((int) i, st.get((int) (i << 1)) | st.get((int) ((i << 1) | 1)));
}
}
return st.get(1);
}
}
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
long n = sc.nextLong();
long m = sc.nextLong();
n = 1 << n;
ST st = new ST(n);
while (m-- > 0) {
long p = sc.nextLong();
long b = sc.nextLong();
System.out.println(st.update(p - 1, b));
}
}
}