polska Posted May 11, 2012 at 10:31 PM Report #454780 Posted May 11, 2012 at 10:31 PM Boas pessoal, surgiu hoje um problema no ToPAS, que me está a criar bastante confusão, apesar de ser dos mais fáceis, eu não estou a entender, e venho pedir a vossa ajuda.. O problema consiste em descobrir o dia do mes de maio em que o topas se vai realizar num determinado ano..O toPAS realizasse sempre na primeira semana completa do mês de maio, na sexta feira.. Por exemplo, ano=2012, o output deve ser 11. é nos dada esta fórmula: (ano+ano/4-ano/100+ano/400+Tabela[mes]+dia)%7 -> o resultado desta expressão é um valor entre 0 e 6, inclusive, sendo 0 domingo, 1 segunda....etc , a tabela é: Mês valor Mês Valor janeiro 0 fevereiro 3 março 2 abril 5 maio 0 junho 3 julho 5 agosto 1 setembro 4 outubro 6 novembro 2 dezembro 4 É assim, eu dou o ano 2012, e a expressão é igual a 6, eu substituo o Tabela[mes] por 5 e o dia por 0... Dá sexta feira (6), agora não sei é como calcular o dia em que calha no mês de maio ? ... Contudo também não sei se estou a fazer a expressão correcta, eu não sei se tenho mesmo de substituir o Tabela[mes] pelo numero do mes e o dia pelo valor do mes... ;x, é isto que me mete confusão.. Corrige um sábio e ele mais sábio ficará. Corrige um ignorante e um inimigo ganharás.
HappyHippyHippo Posted May 11, 2012 at 11:37 PM Report #454793 Posted May 11, 2012 at 11:37 PM se começa numa terça tens de somar a sexta a diferença de domingo a terça +--+--+--+--+--+--+--+--+--+--+--+--+--+--+ | S| T| Q| Q| S| S| D| S| T| Q| Q| S| A| D| +--+--+--+--+--+--+--+--+--+--+--+--+--+--+ | | 1| 2| 3| 4| 5| 6| 7| 8| 9|10|11|12|13| +--+--+--+--+--+--+--+--+--+--+--+--+--+--+ <-------6--------><------5------> começa sempre na sexta (5) + o resto da semana inicial imcompleta (7 - dia_inicial) IRC : sim, é algo que ainda existe >> #p@p Portugol Plus
polska Posted May 12, 2012 at 10:58 AM Author Report #454822 Posted May 12, 2012 at 10:58 AM se começa numa terça tens de somar a sexta a diferença de domingo a terça +--+--+--+--+--+--+--+--+--+--+--+--+--+--+ | S| T| Q| Q| S| S| D| S| T| Q| Q| S| A| D| +--+--+--+--+--+--+--+--+--+--+--+--+--+--+ | | 1| 2| 3| 4| 5| 6| 7| 8| 9|10|11|12|13| +--+--+--+--+--+--+--+--+--+--+--+--+--+--+ <-------6--------><------5------> começa sempre na sexta (5) + o resto da semana inicial imcompleta (7 - dia_inicial) Então por exemplo, basta-me fazer a expressão com o 5 na Tabela[mes] e o 0 no dia e depois e me dado o valor, para o caso de 2012, dá 6, se eu somar 5 (sexta), da-me 11, certo. Mas no caso 2022, já não é a mesma coisa, pois o resultado da expressão é 4, se somar 5 dá 9, e tem de dar 6.. Corrige um sábio e ele mais sábio ficará. Corrige um ignorante e um inimigo ganharás.
HappyHippyHippo Posted May 12, 2012 at 11:25 AM Report #454832 Posted May 12, 2012 at 11:25 AM a tua questão é usar então a "tabela" ... para mim isso nunca fez sentido .... mas só perguntaste como calcular ... eu faria assim (nao testado): int start_day(int year, int month) { int _year = 1900; int _month = 1; int _day = 1; // janeiro de 1990 começa a uma segunda if (year < 1900 || month < 1 || month > 12) { // erro ... return -1; } // acho que falta o ajustamento de 100 em 100 anos (nao tenho a certeza) while (_year != year && _month != month) { switch (_month) { case 2: _year % 4 ? _day += 28 : _day += 29; break; case 4: case 6: case 9: case 11: _day += 30; default: _day + 31; } _month++; if (_month == 13) { _year++; _month = 1; } } return _day % 7; } int main(void) { int dia_inicio_2012_6 = start_day(2012, 6); } IRC : sim, é algo que ainda existe >> #p@p Portugol Plus
polska Posted May 12, 2012 at 11:31 AM Author Report #454838 Posted May 12, 2012 at 11:31 AM a tua questão é usar então a "tabela" ... para mim isso nunca fez sentido .... mas só perguntaste como calcular ... eu faria assim (nao testado): int start_day(int year, int month) { int _year = 1900; int _month = 1; int _day = 1; // janeiro de 1990 começa a uma segunda if (year < 1900 || month < 1 || month > 12) { // erro ... return -1; } // acho que falta o ajustamento de 100 em 100 anos (nao tenho a certeza) while (_year != year && _month != month) { switch (_month) { case 2: _year % 4 ? _day += 28 : _day += 29; break; case 4: case 6: case 9: case 11: _day += 30; default: _day + 31; } _month++; if (_month == 13) { _year++; _month = 1; } } return _day % 7; } int main(void) { int dia_inicio_2012_6 = start_day(2012, 6); } A questão é que com uns ajustes na expressão, chegamos ao resultado, pelo menos foi o que nos foi dito no final.. Penso que não é preciso tanto calculo.. Corrige um sábio e ele mais sábio ficará. Corrige um ignorante e um inimigo ganharás.
HappyHippyHippo Posted May 12, 2012 at 11:56 AM Report #454843 Posted May 12, 2012 at 11:56 AM testado e a funcionar ... não alterei nada à formula ... int start_date(int ano, int mes, int dia) { int Tabela[] = {0, 3, 2, 5, 0, 3, 5, 1, 4, 6, 2, 4}; mes--; // ajuste de 1-12 para index da tabela return (ano+ano/4-ano/100+ano/400+Tabela[mes]+dia)%7; } int main() { int year; int dia; for (year = 2000; year < 2030; year++) { dia = start_date(year, 5, 1); dia = dia ? 7 - dia : 0; // numero de dias da semana inicial incompleta printf("Dia de início em %d : %d\n", year, dia + 6); // dia mais sexta } return 0; } IRC : sim, é algo que ainda existe >> #p@p Portugol Plus
polska Posted May 12, 2012 at 06:17 PM Author Report #454888 Posted May 12, 2012 at 06:17 PM testado e a funcionar ... não alterei nada à formula ... int start_date(int ano, int mes, int dia) { int Tabela[] = {0, 3, 2, 5, 0, 3, 5, 1, 4, 6, 2, 4}; mes--; // ajuste de 1-12 para index da tabela return (ano+ano/4-ano/100+ano/400+Tabela[mes]+dia)%7; } int main() { int year; int dia; for (year = 2000; year < 2030; year++) { dia = start_date(year, 5, 1); dia = dia ? 7 - dia : 0; // numero de dias da semana inicial incompleta printf("Dia de início em %d : %d\n", year, dia + 6); // dia mais sexta } return 0; } funcinona a 100% ;D , podes-me só explicar o que faz exatamente esta linha: dia = dia ? 7 - dia : 0; ? Não entendo porcausa do ? e do : ... suponho que seja C++ e eu dou C 😞 Corrige um sábio e ele mais sábio ficará. Corrige um ignorante e um inimigo ganharás.
pikax Posted May 12, 2012 at 06:34 PM Report #454889 Posted May 12, 2012 at 06:34 PM funcinona a 100% ;D , podes-me só explicar o que faz exatamente esta linha: dia = dia ? 7 - dia : 0; ? Não entendo porcausa do ? e do : ... suponho que seja C++ e eu dou C 😞 E' uma especie de if-else, e' tambem suportado por C, entre outras linguagens, "(condicao)?(true):(false)". Seria algo como: if(dia) dia=7-dia; else dia=0; Por muito mais que que estude só aprendo uma coisa, que ainda tenho muita coisa para aprender. A beleza de um código está em decompor problemas complexos em pequenos blocos simples. "learn how to do it manually first, then use the wizzy tool to save time." "Kill the baby, don't be afraid of starting all over again. Fail soon, learn fast."
polska Posted May 12, 2012 at 06:48 PM Author Report #454890 Posted May 12, 2012 at 06:48 PM E' uma especie de if-else, e' tambem suportado por C, entre outras linguagens, "(condicao)?(true):(false)". Seria algo como: if(dia) dia=7-dia; else dia=0; Mas se o dia não é boleano mas sim int, o que é que a condição if(dia) esta a fazer ao certo? Corrige um sábio e ele mais sábio ficará. Corrige um ignorante e um inimigo ganharás.
HappyHippyHippo Posted May 12, 2012 at 06:50 PM Report #454891 Posted May 12, 2012 at 06:50 PM Mas se o dia não é boleano mas sim int, o que é que a condição if(dia) esta a fazer ao certo? se te lembrares não existem booleanos em C. um inteiro é considerado verdadeiro se não for 0 e falso caso contrário IRC : sim, é algo que ainda existe >> #p@p Portugol Plus
polska Posted May 12, 2012 at 06:56 PM Author Report #454892 Posted May 12, 2012 at 06:56 PM se te lembrares não existem booleanos em C. um inteiro é considerado verdadeiro se não for 0 e falso caso contrário Se queres que te diga não sabia disso, pois associo bool a boleano ? ... Bem, mas agora já entendi , Obrigado HappyHippyHippo, e Pikax 😁 Corrige um sábio e ele mais sábio ficará. Corrige um ignorante e um inimigo ganharás.
skiller10 Posted May 12, 2012 at 07:37 PM Report #454896 Posted May 12, 2012 at 07:37 PM Para este problema apenas tens que calcular é o dia em que calha o primeiro domingo e somar 5 a esse dia. (Consegues perceber porquê?) Quanto a calcular o dia, é te dada uma formula: (ano+ano/4-ano/100+ano/400+Tabela[mes]+dia)%7 que te vai indicar o dia da semana de uma data dada. Tu já sabes que o mês é Maio, ou seja 0, podes então retirar essa parte da formula ficando assim: (ano+ano/4-ano/100+ano/400+dia)%7 O programa vai receber o ano, ficando apenas a faltar saber o dia. Já consegues perceber como fazer? "Eu acredito que a vida está constantemente nos testando em nosso nível de confiança, e a vida tem grande recompensa reservada àqueles que demonstram uma confiança sem fim para agir até conseguir. Este nível de resolução pode mover montanhas, mas ele tem de ser constante e consistente. Tão simples quanto isso possa soar, ainda é o denominador comum que separa aqueles que vivem seus sonhos dos que vivem simplesmente.."
polska Posted May 13, 2012 at 01:26 PM Author Report #454982 Posted May 13, 2012 at 01:26 PM Para este problema apenas tens que calcular é o dia em que calha o primeiro domingo e somar 5 a esse dia. (Consegues perceber porquê?) Quanto a calcular o dia, é te dada uma formula: (ano+ano/4-ano/100+ano/400+Tabela[mes]+dia)%7 que te vai indicar o dia da semana de uma data dada. Tu já sabes que o mês é Maio, ou seja 0, podes então retirar essa parte da formula ficando assim: (ano+ano/4-ano/100+ano/400+dia)%7 O programa vai receber o ano, ficando apenas a faltar saber o dia. Já consegues perceber como fazer? Sim 🙂 , como o valor do mês e 0 e eu já o sei, posso ocultar da expressão, bastando-me apenas colocar no dia 1 (1 dia do mês) , e somar 5 asseguir.. É isso, certo? xD Olha, tu participaste no Topas esta sexta? Corrige um sábio e ele mais sábio ficará. Corrige um ignorante e um inimigo ganharás.
skiller10 Posted May 13, 2012 at 02:23 PM Report #455003 Posted May 13, 2012 at 02:23 PM Tens duas hipoteses: - Tens um ciclo que vai percorrendo os dias até encontrar o dia em que calha o primeiro domingo do mês. Algo como: int dia = 1; while((ano + (ano/4) - (ano/100) + (ano/400) + dia) != 0) dia ++; - Podes também calcular em que dia da semana calha o dia 1 do mês e depois somar os nº de dias que falta para a sexta. Sim, participei. "Eu acredito que a vida está constantemente nos testando em nosso nível de confiança, e a vida tem grande recompensa reservada àqueles que demonstram uma confiança sem fim para agir até conseguir. Este nível de resolução pode mover montanhas, mas ele tem de ser constante e consistente. Tão simples quanto isso possa soar, ainda é o denominador comum que separa aqueles que vivem seus sonhos dos que vivem simplesmente.."
polska Posted May 13, 2012 at 02:30 PM Author Report #455004 Posted May 13, 2012 at 02:30 PM (edited) Tens duas hipoteses: - Tens um ciclo que vai percorrendo os dias até encontrar o dia em que calha o primeiro domingo do mês. Algo como: int dia = 1; while((ano + (ano/4) - (ano/100) + (ano/400) + dia) != 0) dia ++; - Podes também calcular em que dia da semana calha o dia 1 do mês e depois somar os nº de dias que falta para a sexta. Sim, participei. Eu calculei o 1 dia e depois calculei a semana incompleta (7-dia), e depois somei 6, eu tinha somado 5 mas o valor esperado era sempre -1, por isso e 6 xD ... Eras da team que ficou em primeiro não foi? 2h 7 problemas resolvidos... tipo, fuck... xD Edited May 13, 2012 at 02:40 PM by polska Corrige um sábio e ele mais sábio ficará. Corrige um ignorante e um inimigo ganharás.
skiller10 Posted May 13, 2012 at 03:17 PM Report #455018 Posted May 13, 2012 at 03:17 PM Sim xD e tu, eras de que equipa? "Eu acredito que a vida está constantemente nos testando em nosso nível de confiança, e a vida tem grande recompensa reservada àqueles que demonstram uma confiança sem fim para agir até conseguir. Este nível de resolução pode mover montanhas, mas ele tem de ser constante e consistente. Tão simples quanto isso possa soar, ainda é o denominador comum que separa aqueles que vivem seus sonhos dos que vivem simplesmente.."
pedrosorio Posted May 13, 2012 at 03:23 PM Report #455020 Posted May 13, 2012 at 03:23 PM Eras da team que ficou em primeiro não foi? 2h 7 problemas resolvidos... tipo, fuck... xD Não se esqueçam que o ToPAS raramente envolve problemas que precisam de algoritmos eficientes para passarem no tempo, pelo que se trata sobretudo de um concurso de velocidade. Alguma experiência em programação e grande à vontade com a linguagem que utilizam é o principal (ao contrário da maioria dos concursos tipo Topcoder, Google Code Jam, ONI, IOI, etc.) Não respondo a dúvidas por mensagem.
polska Posted May 13, 2012 at 03:26 PM Author Report #455021 Posted May 13, 2012 at 03:26 PM (edited) Sim xD e tu, eras de que equipa? Eu era dos bvm40, infelizmente não consseguimos pontuar, eu fiquei principalmente 'lixado' para não dizer outra coisa xD, porque os exercícios eram fáceis, o A o B, o C e mesmo o D, eram fáceis, e não sei que nos deu, por ser a primeira vez ou não ,e mesmo por nao estarmos habiutados a linux, não consseguimos fazer um direito, depois eu cheguei a casa e fiz o A o C e o D na boa, fiquei mesmo desapontado.. Tu estavas no lab de uma ou duas equipas da minha escola também.. Eles a dizer que estavam a acabar o A e voçes com 2 balões já xD. Bem, mas vemo-nos na final sexta xD , visto que ficaste em primeiro também na qualificação, não deve ser difícil descobrir quem és lá xD , eu passei em 20º 😉 Edited May 13, 2012 at 03:31 PM by polska Corrige um sábio e ele mais sábio ficará. Corrige um ignorante e um inimigo ganharás.
polska Posted May 13, 2012 at 03:30 PM Author Report #455023 Posted May 13, 2012 at 03:30 PM (edited) Não se esqueçam que o ToPAS raramente envolve problemas que precisam de algoritmos eficientes para passarem no tempo, pelo que se trata sobretudo de um concurso de velocidade. Alguma experiência em programação e grande à vontade com a linguagem que utilizam é o principal (ao contrário da maioria dos concursos tipo Topcoder, Google Code Jam, ONI, IOI, etc.) Sim, apenas digo aquilo mesmo por ter sido a primeira vez e não estar habituado ao tipo de concurso, e depois chegar lá e ter uma equipa em 1º sem nós ter feito um.. xD Mas tenho a noção disso, basta ver pelas olimpiadas que o tipo de avaliação dos algoritmos e tudo mais é completamente diferente, relativamente á eficiência Edited May 13, 2012 at 03:31 PM by polska Corrige um sábio e ele mais sábio ficará. Corrige um ignorante e um inimigo ganharás.
pedrosorio Posted May 13, 2012 at 03:34 PM Report #455026 Posted May 13, 2012 at 03:34 PM Sim, apenas digo aquilo mesmo por ter sido a primeira vez e não estar habituado ao tipo de concurso, e depois chegar lá e ter uma equipa em 1º sem nós ter feito um.. xD Mas tenho a noção disso, basta ver pelas olimpiadas que o tipo de avaliação dos algoritmos e tudo mais é completamente diferente, relativamente á eficiência As ONI e IOI são um caso diferente porque usam pontuação parcial, mas a maior parte dos concursos a partir de nível universitário é como o ToPAS (ou está certo ou errado), mas só passa se a solução for eficiente (i.e. só tens accepted se tivesses o equivalente aos 100 pontos das ONI/IOI). Não respondo a dúvidas por mensagem.
Recommended Posts
Create an account or sign in to comment
You need to be a member in order to leave a comment
Create an account
Sign up for a new account in our community. It's easy!
Register a new accountSign in
Already have an account? Sign in here.
Sign In Now