PETER - EDITORIAL

editorial
1

PROBLEM LINK:

Contest
Practice

Author: mpsprasanth
Tester: aarya10

DIFFICULTY:

CAKEWALK

PREREQUISITES:

Greedy

PROBLEM:

The value of an alphabet is its position in the alphabetical order,ie, A=1,B=2,…Z=26. Given a sum , there can be one or many palindromes whose sum of the value of the alphabets is exactly S. Out of all such palindromes return the length N of the shortest palindrome.

QUICK EXPLANATION:

To make the palindrome as short as possible, we have to use as many Z’s as possible

EXPLANATION:

Four cases arise here:-

  • Case 1: S%26==0 , We can form the plaindrome with Z’s only(ans = S/26)
  • Case 2: S%26!=0 and S/26 is even, We can form the plaindrome with as many Z’s as possible and the remainder would definitely be less than 26, So one letter of the value remainder can be inserted in between the even number of Z’s. (ans = S/26+1)
  • Case 3: S%26!=0 and S/26 is odd and S%26 is even , We can form the plaindrome with all but one availabe Z’s and now insert shortest palindrome possible with the sum of values of one Z and the remainder which would be of size 2. (ans= S/26+1)
  • Case 4: S%26!=0 and S/26 is odd and S%26 is odd , We can form the plaindrome with all but one availabe Z’s and now insert shortest palindrome possible with the sum of values of one Z and the remainder which would be of size 3. (ans= S/26+2)
Setter's Code 
#include <bits/stdc++.h>
#define ll long long 
using namespace std;
 
int main()
{
    long long int t;
    cin >> t;
    while (t--)
    {
        
        int s;
        cin>>s;
        int k=s/26;
        int r=s%26;
        if(r==0)
        {
            cout<<k<<"\n";
        }
        else if(k%2)
        {
            if(r%2)
            {
                cout<<k+2<<"\n";
            }
            else
            {
                cout<<k+1<<"\n";
            }
            
        }
        else
        {
            cout<<k+1<<"\n";
        }
    }
}
Tester's Code 
#include <bits/stdc++.h>
#define ll long long
#define mp make_pair
#define pb push_back
#define all(v) v.begin(),v.end()

using namespace std;
const ll mod = 1e9 + 7;

int main()
{
#ifndef ONLINE_JUDGE
    freopen("input.txt" , "r" , stdin);
    freopen("output.txt" , "w" , stdout);
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll tt = 1;
    cin >> tt;
    assert(tt<=1000);
    while (tt--)
    {
        ll s, a, b, ans = 0;
        cin >> s;
        assert(s<=10000);
        a = s / 52;
        b = s % 52;
        if (b == 0)ans += 2 * a;
        else if (b <= 26)ans += 2 * a + 1;
        else if (b & 1) ans += 2 * a + 3;
        else ans += 2 * a + 2;
        cout << ans << endl;

    }
    return 0;
}