[Lập trình newbie] Mỗi ngày một bài toán (số 16)

[08520001]

Mình nghĩ bạn nên kèm theo link nộp bài ở cuối đề. dao cu anh cuoi.

[08520001]

Bài này mình làm như sau:
Để được chuỗi dài nhất thì ta dùng nhiều nhất số chữ A và B có thể được.
1. Đề yêu cầu số chữ A tối đa là countA. Ta tìm số chữ A nhiều nhất có thể được như sau: chia countA chữ A thành n cụm, mỗi cụm gồm maxA chữ A, cụm cuối cùng có thể ít hơn maxA chữ A dao cu cho be. Vậy để có thể sử dụng countA chữ A thì ít nhất phải có n - 1 chữ B (chèn B vào giữa các cụm maxA chữ A đó). Nếu số chữ B < n - 1 thì số chữ A nhiều nhất có thể dùng là countA = (số chữ B) * (maxA + 1) và số cụm tương ứng là n = số chữ B + 1.
2. Lúc này ta tính xem có tối đa bao nhiêu chữ B có thể dùng được (nghĩa là chèn vào chuỗi các chữ A trên). Nhiều nhất là chèn các cụm maxB chữ B vào giữa các cụm chữ A trên, sau đó chèn vào giữa các chữ A, do đó, có thể chèn vào tối đa là (số chữ A + 1) * maxB = (countA (sau khi update ở bước 1) + 1) * maxB. Đề yêu cầu dùng tối đa countB chữ B nên số chữ B tối đa có thể dùng là min(countB, (countA + 1) * maxB)
:love:

[lxl]

Góp vui. Lâu quá ko code bằng C rồi mình viết = C# cho nó lẹ. Mấy bạn nào ko rành C# hay ko biết gì về C# thì chỉ cần chú ý thuật toán ở function GiveMeLongestName().

Giải thích sơ bộ: mục đích của bài là lấy dc chuỗi dài nhất. Vì vậy ta cần kiếm bao trong countA có bao nhiu cái maxA và trong countB có bao nhiu maxB. Nếu số lượng maxA= số lượng maxB thì chuỗi dài nhất sẽ là đan xen giữa các chuỗi max và các kí tự còn dư lại. Nếu số lượng max A và max B chênh lệch nhau (hơi phức tạp 1 tí) thì tối đa ta chỉ có thể làm nhiều hơn 1 cụm max A hoặc max B sau đó nếu cụm nào còn dư ta sẽ đan xen vào cái left over.

vd:
số lượng max A = Số lượng max B
22 23 5 5
AAAAABBBBBAAAAABBBBBAAAAABBBBBAAAAABBBBBAABBB
=45

số lượng max chênh lệch nhau
23 12 5 5
AAAAABBBBBAAAAABBBBBAAAAABAAAAABAAA
=35

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;

namespace ForFun
{
    class Program
    {
        static void Main(string[] args)
        {
            using (System.IO.StreamReader reader = new System.IO.StreamReader(new FileStream("input.txt", FileMode.Open, FileAccess.Read)))
            {
                //read current line
                string currentLine = reader.ReadLine();
                int t;
                //parse string to int
                int.TryParse(currentLine, out t);

                //check if t valid. otherwise exit program
                if (t < 1 || t > 100)
                {
                    Console.WriteLine("Invalid T. T must be in [1..100]");
                    Console.ReadLine();
                    Environment.Exit(0);
                }

                char[] delimiter = { ' ' };
                //Loop through T examples
                for (int i = 0; i < t; i++)
                {
                    currentLine = reader.ReadLine();
                    string[] data = currentLine.Split(delimiter, StringSplitOptions.RemoveEmptyEntries);
                    int countA, countB, maxA, maxB;

                    int.TryParse(data[0], out countA);
                    int.TryParse(data[1], out countB);
                    int.TryParse(data[2], out maxA);
                    int.TryParse(data[3], out maxB);

                    Console.WriteLine(Program.GiveMeLongestName(countA, countB, maxA, maxB).ToString());
                }
                Console.ReadLine();
            }
        }

        //Sovling code
        static int GiveMeLongestName(int countA, int countB, int maxA, int maxB)
        {
            if (maxA == 0 || maxB == 0)
            {
                return 0;
            }

            int result = 0;
            //Calculate the max amount of pattern with maxValue.
            int numberOfMaxA = countA / maxA;
            int numberOfMaxB = countB / maxB;

            int leftoverA = countA % maxA;
            int leftoverB = countB % maxB;


            if (numberOfMaxA == numberOfMaxB)
            {
                result = numberOfMaxA * maxA + numberOfMaxB * maxB + leftoverA + leftoverB;
            }
            else
                if (numberOfMaxA > numberOfMaxB)
                {
                    //calculate different between numberOfMaxA and numberOfMaxB. -1 as we included the greater set.
                    int diff = numberOfMaxA - numberOfMaxB - 1;
                    if (leftoverB == diff)
                    {
                        result = (numberOfMaxB + 1) * maxA + numberOfMaxB * maxB + diff * maxA + leftoverB;
                    }
                    else
                        if (leftoverB > diff)
                        {
                            result = (numberOfMaxB + 1) * maxA + numberOfMaxB * maxB + diff * maxA + leftoverB + leftoverA;
                        }
                        else
                        {
                            result = (numberOfMaxB + 1) * maxA + numberOfMaxB * maxB + (diff - leftoverB +1) * maxA + leftoverB;
                        }
                }
                else
                {
                    //calculate different between numberOfMaxA and numberOfMaxB. -1 as we included the greater set.
                    int diff = numberOfMaxB - numberOfMaxA - 1;
                    if (leftoverA == diff)
                    {
                        result = (numberOfMaxA + 1) * maxB + numberOfMaxA * maxA + diff * maxB + leftoverA;
                    }
                    else
                        if (leftoverA > diff)
                        {
                            result = (numberOfMaxA + 1) * maxB + numberOfMaxA * maxA + diff * maxB + leftoverA + leftoverB;
                        }
                        else
                        {
                            result = (numberOfMaxA + 1) * maxB + numberOfMaxA * maxA + (diff - leftoverA + 1) * maxB + leftoverA;
                        }
                }

            return result;
        }
    }
}

Code trên còn nhìu chỗ chưa optimized. Mấy bạn tìm hiểu và thoải mái optimize.

p.s. có nhiều chỗ mình comment và đặt tên biến bằng tiếng anh mấy bạn thông cảm.

[08520001]

Bạn Kiều Thắng cho mình xin mã số của bài này nha. dao cu chup anh.

[09520281]

Link này nhé

http://vnoi.info/index.php?option=com_voj2&page=problem&problem=C11BEAU

[12520238]

Góp Vui :&gt;

Có C rồi, C# rồi. Vậy thôi em góp vui bằng javascript nhé Mặc dù cái này ko tính là programming language

<html>
<body>
	<script type="text/javascript">
	function Differ(a,b,c,d,e,f,g,h)
	{
		diff=a-b-1;
		if (diff==d)
			return a*g+f;
		else
			if (diff<d)
				return e+f;
			else
				return (b+1)*g+b*h+d*(1+g);
	}
	function Solver(countA,countB,maxA,maxB)
	{
		if (maxA==0||maxB==0)
		{
			Output(0);
			return 0;
		}
		maxstrA=parseInt(countA/maxA);
		maxstrB=parseInt(countB/maxB);
		leftA=countA%maxA;
		leftB=countB%maxB;
		if (maxstrA==maxstrB)
			Output(countA+countB);
		else
			if (maxstrA>maxstrB)
				Output(Differ(maxstrA,maxstrB,leftA,leftB,countA,countB,maxA,maxB));
			else
				Output(Differ(maxstrB,maxstrA,leftB,leftA,countB,countA,maxB,maxA));		
	}
	function Magic()
	{
		data=document.getElementById("Input").value.split(/\n/);
		for(i=1;i<=Number(data[0]);i++)
		{
			dat=data[i].split(/\s/);
			Solver(Number(dat[0]),Number(dat[1]),Number(dat[2]),Number(dat[3]));
		}
		return
	}
	function Output(result)
	{
		out=document.getElementById("Output");
		out.value=out.value+result+ "\n";
	}	
	</script>
	<textarea id="Input" placeholder="Input"></textarea>
	<input type="button" value="Do Magic" OnClick="Magic()"/> 
	<textarea id="Output" placeholder="Output"/></textarea>
</body>
</html>

Link test: http://dl.dropbox.com/u/50226822/Fun.html

Góp vui thôi

[08520001]

Hi vọng ngày mai có chap 17 :d