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.