Chef and Chain Codechef Solution: Chef had a hard day and want to play little bit. The game is called “Chain”. Chef has the sequence of symbols. Each symbol is either ‘–‘ or ‘+‘. The sequence is called Chain if each two neighboring symbols of sequence are either ‘-+‘ or ‘+-‘.
For example sequence ‘-+-+-+‘ is a Chain but sequence ‘-+-+–+‘ is not.
Help Chef to calculate the minimum number of symbols he need to replace (ex. ‘–‘ to ‘+‘ or ‘+‘ to ‘–‘) to receive a Chain sequence.
Input
- First line contains single integer T denoting the number of test cases.
- Line of each test case contains the string S consisting of symbols ‘–‘ and ‘+‘.
Output
- For each test case, in a single line print single interger – the minimal number of symbols Chef needs to replace to receive a Chain.
Constraints
- 1 ≤ T ≤ 7
- 1 ≤ |S| ≤ 10^5
Subtasks
- Subtask 1 ≤ |S| ≤ 10, 1 ≤ T ≤ 7 Points: 20
- Subtask 1 ≤ |S| ≤ 1000, 1 ≤ T ≤ 7 Points: 30
- Subtask 1 ≤ |S| ≤ 10^5, 1 ≤ T ≤ 7Points: 50
Example
Input: 2 ---+-+-+++ ------- Output: 2 3
Explanation
Example case 1.
We can change symbol 2 from ‘–‘ to ‘+‘ and symbol 9 from ‘+‘ to ‘–‘ and receive ‘-+-+-+-+-+‘.
Example case 2.
We can change symbols 2, 4 and 6 from ‘–‘ to ‘+‘ and receive ‘-+-+-+-‘.
Chef and Chain – CodeChef Solution in JAVA
import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
class Codechef
{
public static void main (String[] args) throws java.lang.Exception
{
// your code goes here
try
{
Scanner sc=new Scanner(System.in);
int t=sc.nextInt();
while(t-->0)
{
String A=sc.next();
int c1=0;
int c2=0;
int i=0;
int len=A.length();
int f1=0,f2=1;
for(i=0;i<len;i++)
{
if(f1==0 && A.charAt(i)=='+')
c1++;
else if(f1==1 && A.charAt(i)=='-')
c1++;
if(f2==0 && A.charAt(i)=='+')
c2++;
else if(f2==1 && A.charAt(i)=='-')
c2++;
f1=(f1+1)%2;
f2=(f2+1)%2;
}
if(c1<c2)
System.out.print(c1);
else
System.out.print(c2);
System.out.print("\n");
}
}
catch(Exception ee)
{
}
}
}
Chef and Chain – CodeChef Solution in CPP
#include <bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin >> t;
while (t--)
{
string s;
cin >> s;
string s1(s);
int countA = 0;
for (int i = 0; i < s.size(); i++)
{
if (i == 0 || i % 2 == 0)
{
if (s[i] != '+')
{
s[i] = '+';
countA++;
}
}
else
{
if (s[i] != '-')
{
s[i] = '-';
countA++;
}
}
}
int countB = 0;
for (int i = 0; i < s1.size(); i++)
{
if (i == 0 || i % 2 == 0)
{
if (s1[i] != '-')
{
s1[i] = '-';
countB++;
}
}
else
{
if (s1[i] != '+')
{
s1[i] = '+';
countB++;
}
}
}
cout << min(countA, countB) << endl;
}
}Chef and Chain -CodeChef Solution in Python
t=int(input())
for i in range(t):
s=input()
c=d=0
if(s.count('+')==len(s) or s.count('-')==len(s)):
print(len(s)//2)
else:
for j in range(len(s)):
if j%2== 0:
if s[j]== "-":
d+=1
else:
c+=1
else:
if s[j] == "+":
d+=1
else:
c+=1
print(min(c,d))Disclaimer: The above Problem(Chef and Chain ) is generated by CodeChef but the solution is provided by Chase2learn.This tutorial is only for Educational and Learning purpose.
