84292024-01-16 09:29:04naHhhhhhhellooBináris fa magassága (50 pont)csharpIdőlimit túllépés 4/50584ms24732 KiB
using System;
using System.Collections.Generic;
namespace Binarisfa {
    
    class Program {
        struct muvelet {
            public int hely;
            public int hossz;
        }
        struct node {
            public List<int> links; //=new List<int>();
            public List<int> tavolsag;// = new List<int>();
            public int magassag;
            public int index;
        }
        static node generateNode(int index, bool links = true) {
            node n = new node();
            if(index == 1) {
                n.magassag = 1;
                n.links = new List<int>(new int[] { 2, 3 });
                n.tavolsag = new List<int>(new int[] { 1, 1 });
                n.index = index;
            } else {
                n.magassag = (int)MathF.Ceiling( MathF.Sqrt(index));
                n.tavolsag = new List<int>(new int[] { 1, 1 });
                n.index = index;
                if (links) {
                    n.links = new List<int>(new int[] { index * 2, index * 2 + 1 });

                } else {
                    n.links = new List<int>();
                }
            }
            return n;
        }
        
        static int faMagassag(List<node> fa) {
            int ism = (int)MathF.Floor(MathF.Sqrt(fa.Count));
            int best = 0;
            for (int i = fa.Count; i > 0; i--) {

                if (fa[i-1].magassag > best) {
                    best = fa[i-1].magassag;
                }
            }
                    return best;
        }
        static void recalcMag(ref List<node> fa, int honnan) {
            
        }
        static void Main(string[] args) {
            string bement = Console.ReadLine();
            int N = Convert.ToInt32(bement.Split()[0]);
            int M = Convert.ToInt32(bement.Split()[1]);
            
            List<node> fa = new List<node>();
            List<muvelet> muveletek = new List<muvelet>();
            for (int i = 0; i < M; i++) {
                string dolog = Console.ReadLine();
                muveletek.Add(new muvelet { hossz = Convert.ToInt32(dolog.Split()[1]), hely = Convert.ToInt32(dolog.Split()[0]) });
            }
            for (int i = 0; i < MathF.Pow(2,N); i++) {
                if((int)MathF.Ceiling(MathF.Sqrt(i+1)) >= N) {
                    fa.Add(generateNode(i,false));
                    continue;
                }
                fa.Add(generateNode(i));

            }
            for (int i = 0; i < muveletek.Count; i++) {
                if (muveletek[i].hely % 2 == 0) {
                    fa[(int)MathF.Floor(muveletek[i].hely / 2)].tavolsag[0] = muveletek[i].hossz;
                } else {
                    int teszt = (int)MathF.Floor(muveletek[i].hely / 2);
                    fa[(int)MathF.Floor(muveletek[i].hely / 2)].tavolsag[1] = muveletek[i].hossz;

                }
                int honnan = muveletek[i].hely;
                List<int> queue = new List<int> { honnan };
                while (queue.Count != 0 && queue[0] <=fa.Count) {
                    int tavol = 0;
                    if(queue[0] == 1) {
                        tavol = 1;
                    } else {
                        if (queue[0] % 2 == 0) {
                            tavol = fa[(int)MathF.Floor(queue[0] / 2) - 0].tavolsag[0];
                        } else {
                            tavol = fa[(int)MathF.Floor(queue[0] / 2) - 0].tavolsag[1];
                        }
                    }

                    //    Console.WriteLine(fa.Count + " is count, queue:" + queue[0]);
                    int magass = fa[(int)Math.Clamp(MathF.Floor(queue[0] / 2), 0, 1000000)].magassag + tavol;

                    if (queue[0] == 1) {
                        magass = 1;
                    }
                    fa[queue[0]] = new node { tavolsag = fa[queue[0]].tavolsag, magassag =magass, index = fa[queue[0]].index, links = fa[queue[0]].links };
                    foreach (var item in fa[queue[0]].links) {
                        queue.Add(item);
                        
                    }
                    queue.Remove(queue[0]);

                }
                Console.WriteLine(faMagassag(fa)-1);
            }
        }
    }
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base4/50
1Elfogadva0/035ms21144 KiB
2Időlimit túllépés0/0563ms19656 KiB
3Elfogadva2/241ms22512 KiB
4Elfogadva2/243ms22780 KiB
5Futási hiba0/241ms22832 KiB
6Futási hiba0/241ms22976 KiB
7Hibás válasz0/346ms24032 KiB
8Hibás válasz0/346ms24036 KiB
9Hibás válasz0/350ms24732 KiB
10Hibás válasz0/350ms24660 KiB
11Időlimit túllépés0/2568ms21472 KiB
12Időlimit túllépés0/2546ms21548 KiB
13Időlimit túllépés0/2584ms21528 KiB
14Időlimit túllépés0/2578ms21660 KiB
15Időlimit túllépés0/2577ms21668 KiB
16Időlimit túllépés0/2556ms22384 KiB
17Időlimit túllépés0/2558ms22268 KiB
18Időlimit túllépés0/2560ms22468 KiB
19Időlimit túllépés0/2561ms22288 KiB
20Időlimit túllépés0/3561ms22360 KiB
21Időlimit túllépés0/3569ms22248 KiB
22Időlimit túllépés0/3513ms22320 KiB
23Időlimit túllépés0/3582ms22320 KiB