TOPIC
PROBLEM 1031  URI Fórum 1.0
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 N1. Similarly, removing again, you would deal with a cycle of length N2, 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).

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!

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?