TRAVELPS - Editorial

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3

Author: Daanish Mahajan
Tester: Istvan Nagy
Editorialist: Aman Dwivedi

DIFFICULTY:

Cakewalk

PREREQUISITES:

None

PROBLEM:

Chef is going on a road trip and needs to apply for inter-district and inter-state travel e-passes. It takes A minutes to fill each inter-district e-pass application and B minutes for each inter-state e-pass application.

His journey is given to you as a binary string S of length N where 0 denotes crossing from one district to another district (which needs an inter-district e-pass), and a 1 denotes crossing from one state to another (which needs an inter-state e-pass).

Find the total time Chef has to spend on filling the various forms.

EXPLANATION:

Just do as the problem says and calculate the time spent on filling the various forms. As the problem says that 0 denotes crossing from one district to another district which needs an inter-district e-pass that requires A minutes to fill the form, and 1 denotes crossing from one state to another which needs an inter-state e-pass which requires B minutes to fill the form. Hence

Let Z is the count of the number of zeroes present in the string and O is the count of the number of ones present in the string. Hence our answer will be:

ans = Z*A+O*B

Finally, we can output our answer.

TIME COMPLEXITY:

O(|S|) per test case, where |S| is the length of the string.

SOLUTIONS:

Author
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb push_back
#define rb pop_back
#define ti tuple<int, int, int>
#define pii pair<int, int>
#define pli pair<ll, int>
#define pll pair<ll, ll>
#define mp make_pair
#define mt make_tuple

using namespace std;
  
const int maxt = 100, maxn = 100, maxa = 100, maxb = 100;
const string newln = "\n", space = " ";

int main()
{   
    int t;
    int n;
    string s;
    int cost[2];
    cin >> t;
    while(t--){
        cin >> n >> cost[0] >> cost[1] >> s;
        int ans = 0;
        for(char c : s){
            assert(c >= '0' && c <= '1');
            ans += cost[c - '0'];
        }
        cout << ans << endl;
    }
} 
Tester
#include <iostream>
#include <cassert>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <random>

#ifdef HOME
#include <windows.h>
#endif

#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)

template<class T> bool umin(T& a, T b) { return a > b ? (a = b, true) : false; }
template<class T> bool umax(T& a, T b) { return a < b ? (a = b, true) : false; }

using namespace std;

long long readInt(long long l, long long r, char endd) {
	long long x = 0;
	int cnt = 0;
	int fi = -1;
	bool is_neg = false;
	while (true) {
		char g = getchar();
		if (g == '-') {
			assert(fi == -1);
			is_neg = true;
			continue;
		}
		if ('0' <= g && g <= '9') {
			x *= 10;
			x += g - '0';
			if (cnt == 0) {
				fi = g - '0';
			}
			cnt++;
			assert(fi != 0 || cnt == 1);
			assert(fi != 0 || is_neg == false);

			assert(!(cnt > 19 || (cnt == 19 && fi > 1)));
		}
		else if (g == endd) {
			assert(cnt > 0);
			if (is_neg) {
				x = -x;
			}
			assert(l <= x && x <= r);
			return x;
		}
		else {
			assert(false);
		}
	}
}

string readString(int l, int r, char endd) {
	string ret = "";
	int cnt = 0;
	while (true) {
		char g = getchar();
		assert(g != -1);
		if (g == endd) {
			break;
		}
		cnt++;
		ret += g;
	}
	assert(l <= cnt && cnt <= r);
	return ret;
}
long long readIntSp(long long l, long long r) {
	return readInt(l, r, ' ');
}
long long readIntLn(long long l, long long r) {
	return readInt(l, r, '\n');
}
string readStringLn(int l, int r) {
	return readString(l, r, '\n');
}
string readStringSp(int l, int r) {
	return readString(l, r, ' ');
}

int main(int argc, char** argv)
{
#ifdef HOME
	if (IsDebuggerPresent())
	{
		freopen("../in.txt", "rb", stdin);
		freopen("../out.txt", "wb", stdout);
	}
#endif
	int T = readIntLn(1, 100);
	forn(tc, T)
	{
		int N = readIntSp(1, 100);
		int A = readIntSp(1, 100);
		int B = readIntLn(1, 100);
		string S = readStringLn(N, N);
		int res = 0;
		for (char c : S)
		{
			assert(c == '0' || c == '1');
			if (c == '0')
				res += A;
			else
				res += B;
		}
		printf("%d\n", res);
	}
	assert(getchar() == -1);
	return 0;
}

Editorialist
#include<bits/stdc++.h>
using namespace std;

#define int long long

void solve()
{
	int n,a,b;
	cin>>n>>a>>b;

	string s;
	cin>>s;

	int ans = 0;

	for(int i=0;i<n;i++)
	{
		if(s[i]=='0')
			ans+=a;
		else
			ans+=b;
	}

	cout<<ans<<endl;
}

int32_t main()
{
	// freopen("input.txt","r",stdin);
	// freopen("output.txt","w",stdout);

	int t;
	cin>>t;

	while(t--)
		solve();

return 0;
}
1 Like