CF391A Genetic Engineering

    • 221通过
    • 449提交
  • 题目来源 CodeForces 391A
  • 评测方式 RemoteJudge
  • 标签
  • 难度 省选/NOI-
  • 时空限制 1000ms / 256MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题意翻译

    现有一个由‘A’,'T','G','C'组成的字符串请你求出字符串中同一字母连续出现偶数次的子串的个数。

    题目描述

    You will receive 3 points for solving this problem.

    Manao is designing the genetic code for a new type of algae to efficiently produce fuel. Specifically, Manao is focusing on a stretch of DNA that encodes one protein. The stretch of DNA is represented by a string containing only the characters 'A', 'T', 'G' and 'C'.

    Manao has determined that if the stretch of DNA contains a maximal sequence of consecutive identical nucleotides that is of even length, then the protein will be nonfunctional. For example, consider a protein described by DNA string "GTTAAAG". It contains four maximal sequences of consecutive identical nucleotides: "G", "TT", "AAA", and "G". The protein is nonfunctional because sequence "TT" has even length.

    Manao is trying to obtain a functional protein from the protein he currently has. Manao can insert additional nucleotides into the DNA stretch. Each additional nucleotide is a character from the set {'A', 'T', 'G', 'C'}. Manao wants to determine the minimum number of insertions necessary to make the DNA encode a functional protein.

    输入输出格式

    输入格式:

    The input consists of a single line, containing a string $ s $ of length $ n $ $ (1<=n<=100) $ . Each character of $ s $ will be from the set {'A', 'T', 'G', 'C'}.

    This problem doesn't have subproblems. You will get 3 points for the correct submission.

    输出格式:

    The program should print on one line a single integer representing the minimum number of 'A', 'T', 'G', 'C' characters that are required to be inserted into the input string in order to make all runs of identical characters have odd length.

    输入输出样例

    输入样例#1: 复制
    GTTAAAG
    
    输出样例#1: 复制
    1
    
    输入样例#2: 复制
    AACCAACCAAAAC
    
    输出样例#2: 复制
    5
    

    说明

    In the first example, it is sufficient to insert a single nucleotide of any type between the two 'T's in the sequence to restore the functionality of the protein.

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。