PROGRAMMING
Problem statement
1.
When Valera has got some free time, he goes to the library to read some books. Today he's got t free
minutes to read. That's why Valera took n books in the library and for each book he estimated the time
he is going to need to read it. Let's number the books by integers from 1 to n. Valera needs ai minutes
to read the i-th book.
Valera decided to choose an arbitrary book with number i and read the books one by one, starting
from this book. In other words, he will first read book number i, then book number i + 1, then book
number i + 2 and so on. He continues the process until he either runs out of the free time or finishes
reading the n-th book. Valera reads each book up to the end, that is, he doesn't start reading the book
if he doesn't have enough free time to finish reading it.
Print the maximum number of books Valera can read.
Input Format
The first line contains two integers n and t — the number of books and the number of free minutes
Valera's got. The second line contains a sequence of n integers a1, a2, ..., an , where number ai shows the
number of minutes that the boy needs to read the i-th book.
Constraints
(1 ≤ n ≤ 10^5; 1 ≤ t ≤ 10^9) (1 ≤ ai ≤ 10^4)
Output Format
Print a single integer — the maximum number of books Valera can read
SOLUTION :
PYTHON CODE :
p=lambda:list(map(int,input().split()))
n,t=p()
l=p()
i=j=s=0
for j in range(n):
s+=l[j]
if s>t:
s-=l[i]
i+=1
print(n-i)
*******************************************************************************
2.
Problem statement
There is an infinite series of bulbs indexed from 1. And there are 40 switches indexed from 1 to 40.
Switch with index x is connected to the bulbs with indexes that are multiple of x. i.e switch 2 is
connected to bulb 4, 6, 8 ....
You can easily observe that some bulbs are connected to multiple switches and some are not
connected to any switch.
Chotu is playing with these switches, he wants to know the Kth glowing bulb from the start if certain
switches are in ON state. If any of the switch is ON, connected to any bulb then bulb starts glowing. But
chotu has special fond of prime numbers so he only puts prime indexed switches ON.
Input Format
First line contains number of test cases (T). Each test case contains two lines- First line contains a
string S of length 40 containing 0s and 1s that represents the state of bulbs. 1 is ON , 0 is OFF. Second
line contains one integer k. Atleast One switch is in ON condition.
Constraints
1 <= T <= 500
S contains only 0s and 1s. 1s are only at prime positions.
1 <= k <= 10^15
1 is not prime
Output Format
Output one integer per test case representing kth glowing bulb
SOLUTION :
C++ CODE :
#include <bits/stdc++.h>
using namespace std;
int n;
inline void fiu(unsigned long long int *a)
{
register char c=0;
while (c<33) c=getchar_unlocked();
*a=0;
int tmp = 0;
while (c>33)
{
if ( c == 45 ) tmp = 1;
else *a=*a*10+c-'0';
c=getchar_unlocked();
}
if ( tmp == 1 ) *a = 0-(*a);
}
inline void fi(int *a)
{
register char c=0;
while (c<33) c=getchar_unlocked();
*a=0;
int tmp = 0;
while (c>33)
{
if ( c == 45 ) tmp = 1;
else *a=*a*10+c-'0';
c=getchar_unlocked();
}
if ( tmp == 1 ) *a = 0-(*a);
}
long long f(unsigned long long X, vector <unsigned long long> v)
{
long long ans = 0;
for ( int i = 1; i < (1<<n); i++ ) {
long long pro = 1;
for ( int j = 0; j < n; j++ ) {
if ( i&(1<<j) ) pro = pro*v[j];
}
int parity = __builtin_popcount(i);
if ( parity&1 ) ans += X/pro;
else ans -= X/pro;
}
return ans;
}
int main()
{
int t;
unsigned long long K,val,L,R,mx,mid;
fi(&t);
while ( t-- ) {
string s;
vector <unsigned long long> v;
cin >> s;
fiu(&K);
for ( int i = 0; i < 40; i++ ) {
if ( s[i] == '1' ) v.push_back((long long)(i+1));
}
n = (int)v.size();
L = 1LL;
R = (long long)(1e19);
while ( L <= R ) {
mid = (L+R)/2;
val = f(mid,v);
if ( val == K ) {
mx = 0;
for ( int i = 0; i < n; i++ ) {
mx = max(mx, (mid/v[i])*v[i]);
}
printf("%llu\n", mx);
break;
}
else if ( val > K ) R = mid-1;
else L = mid+1;
}
}
return 0;
}
*********************************************************************************
TECHNICAL MCQ
1. Which of the following is not a limitation of binary search algorithm?
binary search algorithm is not efficient when the data elements more than 1500
2. Which of the following is not a limitation of binary search algorithm?
binary search algorithm is not efficient when the data elements more than 1500
3. What is recurrence for worst case of QuickSort and what is the time complexity in Worst case?
Recurrence is T(n) = 2T(n/2) + O(n) and time complexity is O(nLogn)
4. Which of the following Sorting Algorithm will perform the worst if the numbers are ordered in the
opposite form?
Quick Sort
5. What is the third number from the left while doing bubble sort in the 3rd iteration for 5 1 4 2 8?
5
6. Which of the following is not the required condition for binary search algorithm?
there must be a mechanism to delete and or insert elements in the list. is not required
7. Select the code snippet for Jump Search.
a
8. Which of the following sorting algorithms in its typical implementation gives best performance when
applied on an array which is sorted or almost sorted (maximum 1 or two elements are misplaced).
Insertion Sort
9. Binary Search can have _ number of maxm comparsions?
b
10. The Average case occurs in linear search algorithm
when the item to be searched is in some where middle of the Array.
****************************************************************************
Post a Comment