Code Vita Questions and Solutions #1
Problem A
GREEDY HOSTEL OWNER
You know that summers are at peak this year and every day is hot and due to this everyone is using coolers and ACs and a lot of electricity is consumed by the people. You are living in a hostel and your hostel owner decided to charge extra for electricity consumption. To achieve this he put one separate electricity meter for every room and connected all those meters to central meter. But the hostel owner is a bit greedy and wants to manipulate the meters to show a reading that is more than the actual consumption of electricity. He also encrypted all the meters with alphabets. The technique he used for encrypting is as follows: Every meter has 6 Alphabets i.e. 6 digits. Every alphabet is in upper case. Allowed alphabets are A, B, C, D, E, F, G, H, I, J. A corresponds to 0, B = 1 and similarly C = 2, D = 3, E = 4, F = 5, G = 6, H = 7, I = 8, J = 9 The interpretation rules change as follows: If the alphabet next to J is A, then J represents 0. Similarly, if the alphabet after I is B, then I counts as 1 (and not 8), the alphabet after H is C, then H represents 2. The same is true if D follows G and if E follows F. Note that A, B, C, D and E will always retain their respective values. When J is not followed by A, J will represent 9 and similar rules for I, H, G and F You are given central meter reading and encrypted readings of all the meters in the hostel. Your task is to find out whether the owner is Greedy or Innocent. If he is greedy then print the unit difference otherwise print innocent. Owner is greedy if and only if (units of all meters in the hostel except central meter < central meter units)
Input Format:
First line contains an integer N, giving the number of rooms in the hostel. The next line contains N strings each of length 6 characters giving the readings of the meters in the rooms The next line contains an integer that gives the reading in the central meter.
Output Format:
First line containing either GREEDY or INNOCENT If the first line is GREEDY, the next line should contain the difference (as a decimal number) between the central meter reading and the consumption shown in the rooms.
Constraints:
Number of rooms <= 100
Example 1
Input
3
JAABHF JAACJA JAACDA
500
Output
GREEDY
105
Explanation
In the reading JAABHF, J represents 0 since it is followed by A, and hence the reading is 000175. Similarly, the other readings are 000200 and 000230. The total of the readings in the rooms is 605 and the central meter reading is 500. Thus the owner is GREEDY and he stole 605–500 = 105 units.
Example 2
Input
8
JAACJA JAABCH JAABHD JAACAF JAJAJJ JAABEJ JAACJJ JAACDI
1500
Output
INNOCENT
Explanation
The readings are, 000200, 000127, 000173, 000205, 0000099, 000149, 000299, 000238 The sum of these readings is 1490 < 1500, the central meter reading. Hence the owner is INNOCENT.
SOLUTION:
#include <iostream>#include <algorithm>#include <vector>#include <string>using namespace std;vector <int> val(6);int main(){int n, tot = 0, given;string meter;cin >> n;for(int i=0; i<n; i++) {int p = 1;int reading = 0;val = vector <int> (6, 0);cin >> meter;for(int j=0; j<6; j++) {int sm = meter[j] — ‘A’ + meter[j+1] — ‘A’;if((meter[j] > meter[j+1]) && (sm == 9)) {val[j] = sm — (meter[j] — ‘A’);}else {val[j] = meter[j] — ‘A’;}}for(int q=5; q>=0; q — ) {reading += val[q] * p;p *= 10;}tot += reading;}cin >> given;if(given < tot) {cout << “GREEDY\n”;cout << tot — given << “\n”;}else {cout << “INNOCENT\n”;}return 0;}
PROBLEM B:
NUMBERS WITH NON-DECREASING DIGITS
Some numbers such as 7, 234, 12378 have the digits that are non-decreasing when we read them from left to right. In this problem, we want to find the largest such number less than or equal to a given number N.
Input Format:
Integer N
Output Format:
Largest integer M ≤ N that has its digits non-decreasing. The output should not contain leading zeros.
Constraints:
N <= 10¹⁸
Example 1
Input
89
Output
89
Explanation
89 itself has non-decreasing digits.
Example 2
Input
549
Output
499
Explanation
From 500 to 549, the integers have 5 as the leading digit and the second digit must be less than or equal to 4. But then, such a number cannot have its digits non decreasing.
Solution
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
vector <int> digits;int save_digits(long long n) {
while(n > 0) {
digits.push_back(n % 10);
n /= 10;
}
}
bool check_non_decreasing() {
if(digits.size() == 1) {
return true;
}
for(int i=0; i<digits.size()-1; i++) {
if(digits[i] > digits[i+1]) {
return false;
}
}
return true;
}int main()
{
long long N;
cin >> N;
long long n = N;
int i;
save_digits(n);
reverse(digits.begin(), digits.end());if(check_non_decreasing())
cout << N;
else {
int sz = digits.size();
for(i=sz-1; i>0; i — ) {
digits[i] = 9;
digits[i-1] — ;
if(check_non_decreasing())
break;
}
for(i=0; i<sz; i++) {
if(digits[i] > 0)
cout << digits[i];
}
cout << endl;
return 0;
}
PROBLEM C:
PRIME COUNTERS
Given a number N, let CP(N) denote the number of primes between 1 and N (inclusive of N). We call N a prime counter if CP(N) is a prime (N need not be a prime). For example, CP(3) = 2, CP(4) = 2, CP(5) = 2, CP(7) = 4.
Input Format:
An integer T, the number of test cases T lines each containing two positive integers L, R separated by space.
Output Format:
T lines containing the number of prime counters between L and R (both inclusive) in the ith test case (or NONE is no prime counter exists in that range).
Constraints:
L ≤ R ≤ 10⁶
Example 1
Input
1
1 10
Output
4
Explanation
CP(1) = 0, CP(2) = 1, CP(3) = 2, CP(4) = 2, CP(5) = 3, CP(6) = 3, CP(7) = 4= CP(8) = CP(9) = CP(10). Hence there are 4 prime counters, 3, 4, 5, 6 in the range 1 to 10.
Example 2
Input
2
2 20
3 30
Output
8
8
Explanation
Up to 10, we have 4 prime counters. Between 11 and 20 the prime counters are 11, 12, 17, 18 and hence the count is 8. Between 21 and 30, we have no prime counters.
SOLUTION:
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;
const int N = 1e6 + 3;int CP[N], PRC[N];
vector <bool> is_prime(N, true);
/* For understanding
CP[i] — number of primes between 0 and i
PRC[i] — number of prime counters between 0 and i
is_prime[i] — true if i is prime, false otherwise
*/
void sieve() {
is_prime[0] = is_prime[1] = false;
for (int i = 2; i * i <= N; i++) {
if (is_prime[i]) {
for (int j = i * i; j <= N; j += i)
is_prime[j] = false;
}
}
}
void counting() {
int i;
CP[0] = 0;
PRC[0] = 0;
for(i=1; i<=N; i++) {
if(is_prime[i]) {
CP[i] = CP[i-1] + 1;
}
else {
CP[i] = CP[i-1];
}
}
for(i=1; i<=N; i++) {
if(is_prime[CP[i]]) {PRC[i] = PRC[i-1] + 1;
}
else {
PRC[i] = PRC[i-1];
}
}
//cout << endl;
}
void testcase() {
int L, R, ans;
cin >> L >> R;
if(L == 0) {
ans = PRC[R];
}
else {
ans = PRC[R] — PRC[L-1];
}
cout << ans << “\n”;
}
int main()
{
sieve();
counting();
int t;
cin >> t;
while(t — ) {
testcase();
}
return 0;
}
