Funciona da mesma forma que as gincanas de poesia e de pixel art: o membro de cima dá o tema, e o debaixo verifica se o código do programador de cima compila e digita: COMPILA / NÃO COMPILA (não diga o por quê, deixe que o programador do código encontre o bug), além de preparar o seu código para o tema supracitado.
Dica: pra criar e testar seus códigos de maneira rápida e prática, você pode usar este site! É até recomendado que todos usem este mesmo site pra que não haja erros de versão. Pra colar o código aqui, basta usar as ferramentas de resposta do tópico pra inserir a tag <código>.
Funciona da mesma forma que as gincanas de poesia e de pixel art: o membro de cima dá o tema, e o debaixo verifica se o código do programador de cima compila e digita: COMPILA / NÃO COMPILA (não diga o por quê, deixe que o programador do código encontre o bug), além de preparar o seu código para o tema supracitado.
OBS: Pode usar qualquer linguagem. OBS²: Precisa dizer qual linguagem tá usando.
using System;
namespace Gincana
{
public class Program
{
public static void Main()
{
var car = new Car(true);
car.CarTurnOn();
var car2 = new Car(false);
car2.CarTurnOn();
car2.CarTurnOff();
}
}
public class Car{
public bool carState {get; private set;}
public Car(bool carState) =>
this.carState = carState;
public void CarTurnOn(){
if(!carState) {
Console.WriteLine("Ligando o carro...");
carState = true;
} else
Console.WriteLine("Carro ja esta ligado");
}
public void CarTurnOff(){
if(carState){
Console.WriteLine("Desligando o carro...");
carState = false;
} else
Console.WriteLine("O carro ja esta desligado");
}
}
}
Tema: Cadastro com login e senha.
Só cadastra com sucesso se a senha tiver mais de 6 caracteres e o nome de usuário conter o caractere "#".
package main
import (
"fmt"
"strings"
)
type user struct {
login string
password string
name string
}
func NewUser(login, password, name string) *user {
u := user{login: login, password: password, name: name}
return &u
}
func Register(u *user) {
if len(u.password) < 6 {
fmt.Println("Senha inválida, precisa ter 6 caracteres ou mais.")
return
}
if !strings.Contains(u.name, "#") {
fmt.Println("Nome inválido, por favor digite um nome que tenha o carctere '#'")
return
}
fmt.Println("Usuário cadastrado com sucesso!")
}
func main() {
var u *user
u = NewUser("May", "1234", "Mayleone")
Register(u)
fmt.Println("-----------")
u = NewUser("May", "123456789", "Mayleone")
Register(u)
fmt.Println("-----------")
u = NewUser("May", "123456789", "#Mayleone")
Register(u)
}
COMPILA!
E queria comentar que achei a sintaxe do Go bem complexa HAHAHA.
Tema: Gato mia e cachorro late:
C #:
using System;
namespace Gincana
{
public class Program
{
public static void Main()
{
Mamifero[] pets =
{
new Cachorro(), new Gato(), new Cachorro(),
new Gato()
};
foreach(var pet in pets)
pet.EmitirSom();
}
}
public abstract class Mamifero{
public abstract void EmitirSom();
}
public class Cachorro : Mamifero{
public override void EmitirSom()=>
Console.WriteLine("Au Au!");
}
public class Gato : Mamifero{
public override void EmitirSom()=>
Console.WriteLine("Miau Miau!");
}
}
TEMA: Estou lendo uma string através do espelho, sem as vogais.
function reverseStringNoVogals(drw){
var noVogal = drw.replace(/[aeiou]/ig,'')
var reverse = "";
for(var i = noVogal.length-1; i>=0; i--){
reverse += noVogal[i]
}
console.log(reverse)
}
function main(){
var word;
word = "cachorro";
reverseStringNoVogals(word);
word = "gato";
reverseStringNoVogals(word);
word = "aaaa"
}
main();
TEMA: Contando cédulas(colocar quantas cédulas de 2,5,10,20,50 e 100 reais, e moedas de 1 real, são necessárias para determinado valor inteiro)
@Algui código feito em JS esqueceu de especificar mas tá safe, enfim COMPILA.
Fiz o código correndo aqui tinha mil jeitos mais efetivos para fazer isso mas fiz do jeito mais simples e mais porco possível (Não falaram que tinha que ser bonito, e acho que foi isso que o Algui pediu).
C:
#include <stdio.h>
int main() {
int Money;
int Total;
printf("Valor a ser contado:");
scanf("%i",&Money);
Total = Money / 100;
printf("Notas de 100 = %d\n", Total);
Money = Money % 100;
Total = Money / 50;
printf("Notas de 50 = %d\n", Total);
Money = Money % 50;
Total = Money / 20;
printf("Notas de 20 = %d\n", Total);
Money = Money % 20;
Total = Money / 10;
printf("Notas de 10 = %d\n", Total);
Money = Money % 10;
Total = Money / 5;
printf("Notas de 5 = %d\n", Total);
Money = Money % 5;
Total = Money / 2;
printf("Notas de 2 = %d\n", Total);
Money = Money % 2;
Total = Money / 1;
printf("Notas de 1 = %d\n", Total);
Money = Money % 1;
}
Uma calculadora de datas que verifique quantos dias se passou de uma data até a outra incluindo anos bissextos.
import java.text.ParseException;
import java.text.SimpleDateFormat;
import java.util.GregorianCalendar;
import java.util.Scanner;
public class Main {
private static final SimpleDateFormat SDF = new SimpleDateFormat("dd/MM/yyyy");
public static void main(String[] args) {
try (Scanner sc = new Scanner(System.in)) {
System.out.print("Entre com uma data: ");
GregorianCalendar gc1 = DateFactory.inputDate(sc.nextLine());
System.out.print("Entre com outra data: ");
GregorianCalendar gc2 = DateFactory.inputDate(sc.nextLine());
int diff = getDaysDiff(gc1.getTimeInMillis(), gc2.getTimeInMillis());
StringBuilder sb = new StringBuilder();
sb.append(
(gc1.compareTo(gc2) < 0 ?
diff == 1 ? "Falta" : "Faltam" :
diff == 1 ? "Passou" : "Passaram-se"
)
);
sb.append(" " + diff + " ");
sb.append(diff == 1 ? "dia" : "dias");
sb.append(" entre ");
sb.append(SDF.format(gc1.getTime()));
sb.append(" e ");
sb.append(SDF.format(gc2.getTime()));
sb.append(". =)");
System.out.println("\n" + sb.toString());
} catch (Exception e) {
System.err.println("Deu ruim, Braia!");
System.err.println(e.getMessage());
}
}
private static int getDaysDiff(long before, long after) {
long diff = (after - before) / (1000 * 60 * 60 * 24);
return (int) Math.abs(diff);
}
// =-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-==-=-=-=-=-=-=-=-=-=-=-=-=-=-
private abstract static class DateFactory {
public static GregorianCalendar inputDate(String sDate) throws Exception {
try {
if (!isDateMatches(sDate))
throw new DateFormatException("Data inválida!");
GregorianCalendar gc = new GregorianCalendar();
gc.setTime(SDF.parse(sDate));
return gc;
} catch (DateFormatException | ParseException e) {
throw e;
}
}
public static boolean isDateMatches(String dateFormat) {
return dateFormat.matches("\\d{2}/\\d{2}/\\d{4}");
}
}
// =-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-==-=-=-=-=-=-=-=-=-=-=-=-=-=-
private static class DateFormatException extends RuntimeException {
private static final long serialVersionUID = 1L;
public DateFormatException(String msg) {
super(msg);
}
}
}
OBS: A classe java.util.GregorianCalendar já trata os anos bissextos
TEMA:
Em uma cidade há dois faróis. O farol A pisca uma luz a cada 15 minutos e o farol B pisca a cada 25 minutos constantemente.
Faça um programa que calcula os intervalos e escreva qual é o intervalo cujo os dois faróis piscam ao mesmo tempo. Caso o intervalo passe de 1 hora, o sistema deve separar as horas e os minutos.
EXEMPLO:
65 minutos = 1 hora e 5 minutos
80 minutos = 1 hora e 20 minutos
256 minutos = 4 horas e 16 minutos
TEMA: Em uma cidade há dois faróis. O farol A pisca uma luz a cada 15 minutos e o farol B pisca a cada 25 minutos constantemente.
Faça um programa que calcula os intervalos e escreva qual é o intervalo cujo os dois faróis piscam ao mesmo tempo. Caso o intervalo passe de 1 hora, o sistema deve separar as horas e os minutos.
PS: Ta em Typescript na real (vai crashar se tentar compilar em JS), mas como não tem syntax highlight pra TS aqui, coloquei JS mesmo.
Solução A (mais elegantttt):
Javascript:
const farolA = 15;
const farolB = 25;
function interval_a(a: number, b: number): number {
let _a = a, _b = b;
let r;
do {
r = _a % _b;
_a = _b;
_b = r;
} while(r !== 0);
return (a * b) / _a;
}
function answer_a() {
const result = interval_a(farolA, farolB);
console.log(`Fluxo A: ${parseTime(result)}`);
}
answer_a();
// ================================================
function parseTime(mins: number): string {
if (mins > 60) {
const h = Math.floor(mins / 60);
const m = mins % 60;
return `Próxima piscada simultânea em ${h} horas e ${m} minutos`;
} else return `Próxima piscada simultânea em ${mins} minutos`;
}
Solução B (¯\_(ツ)_/¯):
Javascript:
const farolA = 15;
const farolB = 25;
function interval_b(a: number, b: number): number {
let c = 0;
let _a = a, _b = b;
do {
if (_a <= 0) _a = a;
if (_b <= 0) _b = b;
let m = (_a < _b) ? _a : _b;
c += m;
_a -= m;
_b -= m;
} while (_a !== _b)
return c;
}
function answer_b() {
const result = interval_b(farolA, farolB);
console.log(`Fluxo B: ${parseTime(result)}`);
}
answer_b();
// ================================================
function parseTime(mins: number): string {
if (mins > 60) {
const h = Math.floor(mins / 60);
const m = mins % 60;
return `Próxima piscada simultânea em ${h} horas e ${m} minutos`;
} else return `Próxima piscada simultânea em ${mins} minutos`;
}
Já que o do XGB foi um pouco mais elaborado, bora escalando.
Próximo tema: O Lord Wallace foi convidado pra um jantar e decidiu levar uma garrafa de vinho. Porém, seu conhecimento sobre vinhos é quase inexistente. Sendo um verdadeiro cavalheiro mesquinho (ainda que não goste de aparentar ser pão duro), ele decide usar uma regra simples na hora de escolher o vinho.
Em qualquer seleção de dois ou mais vinhos, ele sempre irá comprar o segundo mais barato.
O programa deve listar as opções que foram dadas ao Lord Wallace (incluindo nome do vinho e preço) e qual opção ele escolheu.
class Vinho {
constructor(name, value) {
this.name = name;
this.value = value;
}
}
let vinhos = [];
vinhos.push(new Vinho("HAUT-BRION", 2000));
vinhos.push(new Vinho("LAFITE ROTHSCHILD", 1432));
vinhos.push(new Vinho("LATOUR", 5324));
vinhos.push(new Vinho("MARGAUX", 3242));
vinhos.push(new Vinho("MOUTON ROTHSCHILD", 532));
vinhos.push(new Vinho("CHEVAL BLANC", 865));
let mais_barato = null;
let sec_mais_barato = null;
for (let i = 0; i < vinhos.length; i++) {
for (let j = 0; j < vinhos.length - 1; j++) {
// Pegar mais barato
if (!mais_barato) {
mais_barato = vinhos[j];
continue;
}
if (vinhos[j].value < mais_barato.value) {
mais_barato = vinhos[j];
}
}
// Pegar segundo mais barato
if (!sec_mais_barato) {
sec_mais_barato = vinhos[i];
continue;
}
if (vinhos[i].value < sec_mais_barato.value && vinhos[i].value !== mais_barato.value) {
sec_mais_barato = vinhos[i];
}
}
console.log(`Cardápio:`);
for (let vinho of vinhos) {
console.log(`Nome: ${vinho.name}\nPreço: ${vinho.value}\n`)
}
console.log(`Segundo mais barato: ${sec_mais_barato.name}`);
Proximo Tema : Uma Glock Tem 30 Balas e tem 10% de chance de dar uma rajada de 3 tiros . O programa deve mostrar quantos disparo por pressionar o gatilho e quantas balas faltam
@KawCompila : Ta Em Java Script Proximo Tema : Uma Glock Tem 30 Balas e tem 10% de chance de dar uma rajada de 3 tiros . O programa deve mostrar quantos disparo por pressionar o gatilho e quantas balas faltam
var shotNumber = 0;
function glockShot(bullets){
var minusRandom = 3;
if(minusRandom >= bullets){
minusRandom = bullets;
}
var chance = Math.floor(Math.random() *10);
shotNumber++;
if (chance ===0){
bullets -=minusRandom;
console.log(`Pressionar de gatilho numero ${shotNumber} foram dados ${minusRandom} tiros, faltam ${bullets} balas`)
}
else{
bullets -=1;
console.log(`Pressionar de gatilho numero ${shotNumber} foi dado 1 tiros, faltam ${bullets} balas`)
}
return bullets;
}
function main(){
var glockBullets = 30;
while(glockBullets>0){
glockBullets=glockShot(glockBullets)
}
}
main();
Próximo Tema: criar uma matriz aleatória de números inteiros, imprimir a matriz e após isso somar todos os números impares da matriz e subtrair com a soma de todos os números pares da matriz.
import os
from random import seed
from random import randint
# Limpa a tela do cmd
def sysclear():
if os.name == 'nt': # Windows
_ = os.system('cls')
else: # Linux e Mac
_ = os.system('clear')
sysclear()
balas = 30
print('Você está segurando uma GLOCK!')
while True:
print('Balas faltando: ' + str(balas))
print('Disparos: ' + str(30 - balas))
input('Aperte ENTER para apertar o gatilho.')
sysclear()
if balas > 0:
chance = randint(0, 9)
txt = 'Você disparou '
if chance == 0 and balas >= 3:
txt = txt + 'uma rajada de três tiros!'
balas = balas - 3
else:
txt = txt + 'um tiro!'
balas = balas - 1
print(txt)
else:
print('Suas balas acabaram...')
Proximo Tema: Dado uma frase com mais de treze palavras, inverta todas as palavras cuja a posição de cada uma represente um número primo e elimine uma vogal aleatória de cada palavra invertida.
Próximo Tema: criar uma matriz aleatória de números inteiros, imprimir a matriz e após isso somar todos os números impares da matriz e subtrair com a soma de todos os números pares da matriz.
Sobre o teu tema, é para criar uma matriz com um tamanho fixo ou aleatório (ex: toda vez que o programa for iniciado, é gerado um tamanho aleatório para a matriz)? Ficou um pouco confuso pra mim.
Sobre o teu tema, é para criar uma matriz com um tamanho fixo ou aleatório (ex: toda vez que o programa for iniciado, é gerado um tamanho aleatório para a matriz)? Ficou um pouco confuso pra mim.
@Dr.XGB já que fui citado, vou quebrar as regras de leve aqui
Ruby:
def ans(a, b)
lcm = a * b / a.gcd(b)
if lcm >= 60
h = lcm / 60
print "#{h} hora"
print 's' if h > 1
print ' e '
end
m = lcm % 60
puts "#{m} minutos"
end
ans 5, 5
ans 25, 35
ans 142394, 1238234
Uma Glock Tem 30 Balas e tem 10% de chance de dar uma rajada de 3 tiros . O programa deve mostrar quantos disparo por pressionar o gatilho e quantas balas faltam
Próximo Tema: criar uma matriz aleatória de números inteiros, imprimir a matriz e após isso somar todos os números impares da matriz e subtrair com a soma de todos os números pares da matriz.
Proximo Tema: Dado uma frase com mais de treze palavras, inverta todas as palavras cuja a posição de cada uma represente um número primo e elimine uma vogal aleatória de cada palavra invertida.
require 'prime'
def remove_random_vowel(word)
word.gsub(word.scan(/[aeiou]/).sample, '')
end
def ans(text)
words = text.split(/\W+/)
primegen = Prime::EratosthenesGenerator.new
words.each_with_index do |word, index|
if Prime.prime?(index, primegen)
word = remove_random_vowel(word.reverse)
print word unless word.empty?
else
print word
end
print ' '
end
puts
end
ans "o rato roeu a roupa do rei de roma"
ans "a arranaha ranha jarraranho ranha aranha"
(As posições começam em 0, dá pra somar 1 em index se quiser)
P.S.: Só um comentário, seria beeem chato fazer isso em qualquer linguagem que não fosse Ruby provavelmente, porque ia ter que implementar deus e a tia. Seria legal manter os temas mais contidos, e pelo menos limitar um pouco a quantidade de implementação.
Tema: Joaquim tem um grafo e quer um caminho passando por todos os nós no menor tempo possível. Resolva o problema do joaquim em tempo polinomial.
Tema de verdade: Você e seu irmão ganharam uma coleção de Gogo's (jurava que escrevia googol auehaeu). Cada Gogo tem um valor diferente (alguns são mais raros, brilham no escuro, etc), mas vocês ganharam uma coleção completa e gostariam de dividí-la de forma justa, de forma que a soma dos valores dos Gogos que cada um recebe seja igual. Dada uma lista com valores dos Gogos, divida a lista entre você e seu irmão seguindo este critério. (P.S.: Pode assumir que sempre será possível dividir a lista corretamente). Pontos extra: caso não seja possível dividir os valores exatamente em dois, divida a lista da forma mais justa possível, de forma que você e seu irmão possam tirar no par ou impar quem fica com a parte mais valiosa com o mínimo de injustiça.
P.S.: Só um comentário, seria beeem chato fazer isso em qualquer linguagem que não fosse Ruby provavelmente, porque ia ter que implementar deus e a tia. Seria legal manter os temas mais contidos, e pelo menos limitar um pouco a quantidade de implementação.
Discordo, usei 40 linhas implementando 2 funções de ~10 linhas cada.
E gostei do tema, então acho que seria legal manter temas assim.
Javascript:
function getPrimes(many) {
let primes = [];
for (var i = 0; i <= many; i++) {
if (isPrime(i)){
primes.push(i);
}
}
return primes;
}
function isPrime(num) {
for(let i = 2; i <num; i++) {
if(num % i === 0) {
return false;
};
}
return num > 1;
}
function ans(str) {
let words = str.split(/\W+/g);
let result = [];
for (let word = 0; word <= words.length; word++) {
if (isPrime(word)) {
let noVowel = words[word - 1].replace(/[aeiou]/, '');
result.push(noVowel.split("").reverse().join(""));
} else result.push(words[word - 1]);
}
console.log(words.join(' ').trim());
console.log(result.join(' ').trim());
}
ans("Make sure you only reverse words of odd length");
Dado uma frase com mais de treze palavras, inverta todas as palavras cuja a posição de cada uma represente um número primo e elimine uma vogal aleatória de cada palavra invertida.
Ignorando o "mais de treze palavras" ali, que eu nem tinha visto (e que não faz muita diferença, pra ser honesto haha), você elimina todas as vogais da palavra, não uma aleatória:
Javascript:
let noVowel = words[word - 1].replace(/[aeiou]/, '');
Versus:
Ruby:
word.gsub(word.scan(/[aeiou]/).sample, '')
É uma diferença sutil, mas o .scan(/[aeiou]/).sample pega a lista de vogais que aparecem na palavra e sorteia apenas uma.
Em Ruby é fácil porque o scan e o sample vêm prontos, em JS teria que fazer. Não é o fim do mundo (as duas juntas deve dar umas 20 linhas), mas conforme acumula fica chato.
Você também não usa a função getPrimes, dava pra diminuir o código aí, e "only reverse words of odd length" não faz parte da proposta.
Achei esse tema bem legal de fazer porque foi uma parada que requereu um pouco de pesquisa. Eu lembro de uma coleção dos Gogo's que teve nos anos 90 feita pela Coca-Cola que eles chamaram de Geloucos. Eu tinha uma pequena coleção deles quando era criança.
De olho eu achei que era pra aplicar MDC, mas quando reinterpretei o enunciado vi que num precisava de nada disso kkkkkkk !!
O meu código não ficou aquele "Minha nossa! Que código eficiente!", mas acredito que resolveu o problema. Com certeza dá pra otimizar essa bodega aqui. Foi um desafio divertido de se fazer!
Php:
<?php
function splitGogos(array $collection): array
{
$out = [[], []];
$collection = subdivideCollection($collection);
foreach ($collection as $subcollection) {
$size = count($subcollection);
foreach ($subcollection as $e => $element)
$out[$e >= intdiv($size, 2)][] = $element;
}
if (array_sum($out[0]) !== array_sum($out[1])) {
echo 'Foi tirado par ou ímpar para decidir quem fica com a parte mais valiosa' . PHP_EOL;
if (evenAndOdd((bool) rand(0, 1)))
shiftCollections($out[0], $out[1]);
}
return $out;
}
function subdivideCollection(array $collection): array
{
$out = [];
foreach (array_unique($collection) as $element)
$out[] = array_values(array_filter($collection, fn ($e) => $e === $element));
return $out;
}
/**
* @param bool $option {par = false} | {ímpar = true}
* @return bool true: ganhou / false: perdeu
*/
function evenAndOdd(bool $option): bool
{
return ((rand(0, 5) + rand(0, 5)) % 2 !== 0) === $option;
}
function shiftCollections(array &$c1, array &$c2): void
{
$aux = $c1;
$c1 = $c2;
$c2 = $aux;
}
function printCollection(array &$c): void
{
print_r($c);
echo "A coleção vale R$" . array_sum($c) . PHP_EOL;
}
// =-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
$collection = [
2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
8, 8, 8, 8, 8, 8,
];
$dividedCollection = splitGogos($collection);
$me = $dividedCollection[0];
$brother = $dividedCollection[1];
echo "Minha coleção de Gogo's:" . PHP_EOL;
printCollection($me);
echo "A coleção do meu irmão de Gogo's:" . PHP_EOL;
printCollection($brother);
Essa aqui é mais tranquila de fazer. TEMA: Faça um programa que te solicita a inserir uma nota de 0 a 10 para cada bimestre. O sistema não deve permitir notas abaixo de 0 e acima de 10 fornecidas pelo usuário. Caso isso aconteça, o sistema deve solicitar novamente um outra nota até que a mesma for validada dentro desta regra.
Feito isso, o sistema deve calcular a média aritmética ponderada e escrever a nota média do aluno naquele ano.
CUIDADO AO DIZER COMPILA/NÃO COMPILA Contém uma pegadinha no meu código, já começando pela linguagem em si.
Achei esse tema bem legal de fazer porque foi uma parada que requereu um pouco de pesquisa. Eu lembro de uma coleção dos Gogo's que teve nos anos 90 feita pela Coca-Cola que eles chamaram de Geloucos. Eu tinha uma pequena coleção deles quando era criança.
De olho eu achei que era pra aplicar MDC, mas quando reinterpretei o enunciado vi que num precisava de nada disso kkkkkkk !!
O meu código não ficou aquele "Minha nossa! Que código eficiente!", mas acredito que resolveu o problema. Com certeza dá pra otimizar essa bodega aqui. Foi um desafio divertido de se fazer!
@Dr.XGB auehauehau, eu peguei um pouco das duas gerações, tinha alguns Geloucos (que, honestamente, não sei de onde vieram direito haha) e depois colecionei os Gogos que vinham com álbum de figurinha e tudo mais. Bons tempos.
Sobre o código: muito pelo contrário, sua solução é tão eficiente que se tivesse correta estava valendo um milhão de dólares (literalmente) hahaha
O nome formal do problema é Problema da Partição, e é um problema NP-completo. Uma solução determinística em tempo polinomial seria uma prova de P = NP. Do artigo em inglês da Wikipedia:
The P versus NP problem is a major unsolved problem in computer science. It asks whether every problem whose solution can be quickly verified can also be solved quickly.
A ideia era fazer pesquisa mesmo, mas acho que exagerei um pouco aushaush
O motivo de ter escolhido esse problema em particular foi que apesar de ser NP-completo, ele tem uma solução (pseudo)polinomial relativamente eficiente usando programação dinâmica, então é conhecido como o "problema mais fácil dos problemas difíceis".
Fiz uma solução só por completude:
C++:
#include <iostream>
#include <numeric>
#include <algorithm>
#include <vector>
using namespace std;
void partition(
const vector<int>& v,
vector<int>& a,
vector<int>& b
) {
int sum = accumulate(v.begin(), v.end(), 0);
int half = sum - sum / 2;
vector<vector<int>> dp(v.size(), vector<int>(half));
vector<vector<int>> pp(v.size(), vector<int>(half));
for (int i = 0; i < v.size(); i++) {
for (int j = 0; j < half; j++) {
pp[i][j] = -1;
if (v[i] <= half) {
dp[i][j] = v[i];
} else {
dp[i][j] = 0;
}
if (i > 0 && dp[i - 1][j] > dp[i][j]) {
dp[i][j] = dp[i - 1][j];
pp[i][j] = -2;
}
int s = j + 1 - v[i];
if (s < 0) {
continue;
}
for (int k = 0; k < i; k++) {
int d = dp[k][s] + v[i];
if (d > half || d <= dp[i][j]) {
continue;
}
dp[i][j] = d;
pp[i][j] = k;
}
}
}
int s = half - 1;
int i = v.size() - 1;
while (i >= 0) {
int p = pp[i][s];
if (p == -2) {
b.push_back(v[i]);
i--;
continue;
}
a.push_back(v[i]);
while (--i > p) {
b.push_back(v[i]);
}
s -= v[i];
}
}
int main() {
vector<int> v = { 1, 2, 3, 1, 2, 6 };
vector<int> a, b;
partition(v, a, b);
for (auto x : a)
cout << x << ' ';
cout << endl;
for (auto x : b)
cout << x << ' ';
cout << endl;
return 0;
}
(fiz meio correndo, dá pra refatorar bem haha)
Enquanto eu implementava percebi que ficou meio complicado mesmo auehaueh
Boa parte da complexidade aí na verdade é construir de fato os conjuntos particionados, que precisa de uma matriz de "ponteiros parentais" e algumas coisinhas mais complicadas de pensar. Teria sido mais prático se eu tivesse proposto apenas dizer se é possível particionar perfeitamente ou não (que é o enunciado original do problema, inclusive).
Essa solução é O(n.S), onde n = o número de elementos sendo particionados e S = a soma dos valores. O maior problema é esse fator S, que também aparece na complexidade de espaço do problema (que é a mesma, inclusive), então esse algoritmo meio que só serve pra valores de S relativamente pequenos. Se o valor fosse proibitivamente grande (na casa dos milhões, por exemplo), o único jeito seria usar o algoritmo recursivo (que é basicamente o código de dentro dos for do meio ali, mas cada dp[i][j] é uma chamada recursiva) e aí a complexidade vira O(2^n), como geralmente acontece com problemas NP-difícil.
A solução também é fortemente relacionada com a solução do Problema da Mochila (é basicamente um problema da mochila quando a mochila tem capacidade igual à metade da soma dos elementos haha), que é um dos problemas mais manjados de programação dinâmica.
O motivo da solução com DP não provar P = NP, aliás, é que na verdade S é exponencial no tamanho do input também: a entrada seriam os bits de S, mas S tem lg(S) bits, então seu valor é exponencial no número de bits, por definição.
Em comparação, seu algoritmo é O (ou n^2, não consigo dizer com as funções de array do PHP, mas certamente é polinomial haha). Pelo que entendi o seu é uma ideia mais parecida com o algoritmo guloso de particionamento, mas usando um esquema parecido com counting sort (a separação de elementos iguais em "baldes" pra distribuir eles, no caso), só faltou fazer uma análise da soma total de cada conjunto também. É um bom algoritmo de aproximação (e talvez você e seu irmão fiquem satisfeitos assim haha), mas não resolve o problema pra qualquer caso, tendo um fator de erro por volta de 7/6 (mas só quando você implementa a lógica gulosa mesmo, sua solução provavelmente tem uma margem de erro maior).
(Vim só comentar, vou deixar a solução do problema do Dr. para o próximo \o)
Este site usa cookies para ajudar a personalizar seu conteúdo e deixar você logado caso se registre.
Ao continuar usando o site, você concorda com o uso de cookies.
