TOPIC

PROBLEM 1031 - URI Fórum 1.0

URI Online Judge asked 6 years ago

URI Online Judge Fórum 1.0

MOD

This topic was solved and cannot recieve new replies.

  • José Luciano de Morais Neto replied 2 years ago

    Eu tava tendo o mesmo problema e eu percebi que minha resposta dava errado pra N=13

  • Fernando Júnior replied 2 years ago

    I agree with you, joaostark.

    Eu concordo com você, joaostark.

    [/quote][/quote]

    I have tested several use cases, but even with the correct answer for all of them, I only get WA 10%. Does anyone know how to request a review of the problem statement?

    Testei vários casos de testes, mas, mesmo com a resposta correta para todos eles, só consigo WA 10%. Alguém sabe como pedir uma revisão do enunciado do problema?

  • Unknown replied 3 years ago

    Does someone have any idea how to solve it without using linked lists?

    Alguém aí tem ideia de como resolver isso sem ser por lista encadeada?

  • João Henrique Damazio replied 3 years ago

    #include <stdio.h>
    int main ()
    {
    
    int n,v[10000],i , k ,j;
    
        while (scanf("%d",&n), n != 0)
        {
            int cont = -1;
            v[0] = 1;
    
            while (v[n - 1] != 13)
            {
                cont++;
    
                for (i = 1 ; i < n ; i++)
                {
                    int c = v[i - 1];
    
                    for (k = 0 ; k < cont ; k++)
                    {
                        c++;
    
                        if (c > n)
                            c = 1;
    
                        for (j = 0 ; j < i ; j++)
                            if (c == v[j])
                            {
                                c++;
                                j = 0;
    
                                if (c > n)
                                    c = 2;
                            }
                    }
    
                    v[i] = c;
    
                    if (i != n - 1 && v[i] == 13)
                        break;
                }
            }
    
            printf("%d\n",cont);
        }
    
    return 0;
    }

    acho que tem algo errado no enunciado , porque eu testei todos os testes e todos dão certo e mesmo assim dá 10% WA.

  • 3amr7ussein replied 4 years ago

    Some help please i have solved this problem but i don't know how he want to get the inputs?? i have create an object of file and name it "POWER CRISIS" and get the inputs from it,is that true??

  • Fernando Fonseca replied 4 years ago

    Seems logical that L and L+N would not be equivalent. When you remove someone from the list, the list does not contain N elements anymore, now it only contains N-1. Similarly, removing again, you would deal with a cycle of length N-2, etc.

    An easy to prove upper bound would be lcm(1, 2, ..., N), but in practice this is clearly overkill. I wonder if it can be reduced analytically.

  • RSeven replied 4 years ago

    Well, I solved the problem, but I'm not satisfied with my solution. At first I was searching for leaps from 1 to N, because I thought that leaps higher than N wouldn't be worth checking, since leap L would be the same as L%N. I got WA for this, and I can't figure out why this is wrong and what would be the right upper limit of L (I solved this without an upperbound to L, since N is small).

  • Miroslav replied 6 years ago

    Thank you!

  • Fernando Fonseca replied 6 years ago

    Lists can solve this because the constraints are low, as the solution can become quadratic with a bigger value of N.

    When one element is removed, the problem is equivalent to the original problem with one less station: you just need to rotate the stations so that the counting starts from 1 again. Try to use this idea to solve it in O(n) (for instance, http://www.spoj.com/problems/ANARC08H/).

  • Cristhian Bonilha replied 6 years ago

    I guess Lists can solve this.

    Lists store a sequence of values, and you can add or remove a value when you need. In this exercise, you have to run across the list and remove some values, and in the next run, you shouldn't count with the one you just removed, so a list can help.

  • Miroslav replied 6 years ago

    Could someone please tell me what should i read,to know how to solve this problem,cus I'm really stuck.For example wiki,or something like that.Thanks!

  • Miroslav replied 6 years ago

    Can this be solved with recursion?Or should use for loop?

  • Frank P. Tominc replied 6 years ago

    No Kasper, region 1 should be the first and region 13 should be the last always, no matter how many regions exists...

  • Miroslav replied 6 years ago

    If I understood the problem, the last region should be shutdown last.For example if there is 25 regions,the region 25 should be last shutdown,and solution is to find number m,which is gonna iterate through list of all regions in such order that the last region(region 25) is last shutdown?