글 읽기 - 문제는 맞았지만 이상한 점을 발견했습니다.

milkpekoe 6년 전 0

시뮬레이션으로는 시간 초과로 답이 없다고 생각해서 계산하는 방식으로 성공했습니다.

계산방식 참고 출처 : https://github.com/mastojun/Pr...

근데 계산 방식이 좀 이해가 안돼서 입력값을 새로 만들어서 테스트 하던 중 이상한 점을 발견했습니다.

입력값을 아래와 같이 했을때 시뮬레이션 결과와 계산 결과가 달라집니다.

시뮬레이션은 느려서 제출시 시간초과가 나왔지만 아래 입력에 의한 출력값은 제대로 나오는것 같습니다.

계산식은 제출시 맞았습니다!!지만 아래 입력에 의한 출력값은 제대로 나오지 않는것 같습니다.

입력

1
4 30 2
1 -3
12 1
23 4
28 -2

출력

시뮬레이션 출력(추락 순서대로 출력)
-3 4 -2 1

계산 출력((추락 순서대로 출력)
-3 -2 4 1

////////////////////////////////////////////
//시뮬레이션 코드 (제출 : 시간 초과. 위 입력에 의한 출력 : 정상)
////////////////////////////////////////////

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace falling_ant
{
    class Program
    {
        public class ANT
        {
            public int id;
            public int move;
            public int position;
            public bool is_fall;
            public bool is_fall_prev;

            public ANT(int[] value)
            {
                id = value[1];
                move = Math.Sign(id);
                position = value[0];
            }

            public ANT(int _id, int _position)
            {
                id = _id;
                move = Math.Sign(id);
                position = _position;
            }

            public void Move(int limit)
            {
                is_fall_prev = is_fall;
                if (is_fall == false)
                {
                    position += move;
                    is_fall = position < 0 || limit < position;
                }
            }

            public void Rotate()
            {
                move = -move;
            }

            public override string ToString()
            {
                return string.Format("{0,2} {1,2} -> {2,2} {3}", id, position-move, position, is_fall ? "Fall" : "Move");
            }
        }

        static void Main(string[] args)
        {
            List<ANT> ant_list = new List<ANT>();
            List<ANT> fall_list = new List<ANT>();
            List<int> results = new List<int>();

            int test_count = int.Parse(Console.ReadLine());
            for (int i = 0; i < test_count; ++i)
            {
                ant_list.Clear();
                fall_list.Clear();

                int[] input = Console.ReadLine().Split(' ').Select(element => int.Parse(element)).ToArray();
                int ant_count = input[0];
                int length = input[1];
                int k = input[2];

                for (int a = 0; a < ant_count; ++a)
                {
                    int[] ant_value = Console.ReadLine().Split(' ').Select(element => int.Parse(element)).ToArray();
                    ant_list.Add(new ANT(ant_value));
                }
                ant_list.Sort((x, y) => x.id.CompareTo(y.id));

                results.Add(TestCase(ant_list, fall_list, length, k));
            }

            foreach (int result in results)
                Console.WriteLine(result);

            Console.ReadKey();
        }

        static int TestCase(List<ANT> ant_list, List<ANT> fall_list, int length, int k)
        {
            int round = 0;
            Dictionary<int, int> positions = new Dictionary<int, int>();
            while (true)
            {
                if (ant_list.Count == fall_list.Count)
                    return fall_list[fall_list.Count - 1].id;

                for (int a = 0; a < ant_list.Count; ++a)
                {
                    ANT ant = ant_list[a];
                    ant.Move(length);

                    if (ant.is_fall && ant.is_fall_prev == false)
                    {
                        fall_list.Add(ant);                    
                        if (fall_list.Count >= k)
                            return fall_list[k - 1].id;
                    }                        

                    if (positions.ContainsKey(ant.position))
                        positions[ant.position]++;
                    else
                        positions.Add(ant.position, 1);
                }

                for (int a = 0; a < ant_list.Count; ++a)
                {
                    ANT ant = ant_list[a];
                    if (positions[ant.position] > 1)
                        ant.Rotate();
                }

                /*
                 * 기록 로그 체크
                Console.WriteLine(string.Format("Round : {0}", round++));
                for (int a = 0; a < ant_count; ++a)
                {
                    ANT ant = ant_list[a];
                    Console.WriteLine(ant.ToString());
                }

                Console.WriteLine("");
                */

                positions.Clear();
            }
        }
    }
}

////////////////////////////////////////////
//계산식 코드 (제출 : 맞았습니다. 위 입력에 의한 출력 : 비정상)
////////////////////////////////////////////
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace falling_ant
{
    class Program
    {
        public class ANT
        {
            public int id;
            public int move;
            public int position;

            public ANT(int[] value, int length)
            {
                id = value[1];
                move = Math.Sign(id);
                position = move > 0 ? value[0] : length - value[0];
            }
        }

        static void Main(string[] args)
        {
            List<ANT> ant_list = new List<ANT>();
            List<ANT> fall_list = new List<ANT>();            
            List<int> ids = new List<int>();
            List<int> results = new List<int>();

            int test_count = int.Parse(Console.ReadLine());
            for (int i = 0; i < test_count; ++i)
            {
                ids.Clear();
                ant_list.Clear();
                fall_list.Clear();

                string[] input_string = Console.ReadLine().Split(' ');
                int[] input = input_string.Select(element => int.Parse(element)).ToArray();
                int ant_count = input[0];
                int length = input[1];
                int k = input[2];

                for (int a = 0; a < ant_count; ++a)
                {
                    int[] ant_value = Console.ReadLine().Split(' ').Select(element => int.Parse(element)).ToArray();
                    ids.Add(ant_value[1]);
                    ant_list.Add(new ANT(ant_value, length));                    
                }

                int idx = 0;
                foreach (ANT ant in ant_list)
                    if (ant.move < 0)
                        ant.id = ids[idx++];

                foreach (ANT ant in ant_list)
                    if (ant.move > 0)
                        ant.id = ids[idx++];

                ant_list.Sort((left, right) => 
                {
                    return left.position != right.position ? right.position.CompareTo(left.position) : left.id.CompareTo(right.id);
                });

                results.Add(ant_list[k - 1].id);
            }

            foreach (int result in results)
                Console.WriteLine(result);

            Console.ReadKey();
        }
    }
}

sait2000 6년 전 1

시뮬레이션이 틀린데요. 밑에같이 되면 -3 -2 4 1 맞지 않나요.

t = 0
1 -3 -
12 1 +
23 4 +
28 -2 -

t = 1
*0 -3 -
13 1 +
24 4 +
27 -2 -

t = 2.5
14.5 1 +
25.5 4 -
25.5 -2 +

t = 7
19 1 +
21 4 -
*30 -2 +

t = 8
20 1 -
20 4 +

t = 18
10 1 -
*30 4 +

t = 28
*0 1 -

milkpekoe 6년 전 0

정수 시간만 판단하는걸로 생각했습니다.

감사합니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

문제는 맞았지만 이상한 점을 발견했습니다.

milkpekoe 6년 전 0

sait2000 6년 전 1

milkpekoe 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말