Prueba de competencia de software de Samsung (SWC) para profesionales que trabajan

Prueba de competencia de software de Samsung para contratar en equipos de I+D de Samsung: septiembre de 2019 
Hay 2 tipos de pruebas de SWC: 
1. Para estudiantes 
2. Para profesionales que trabajan 

La diferencia entre las 2 pruebas es que, para Estudiantes, se mostrarán los resultados del caso de prueba. 
Mientras que para los profesionales que trabajan, los resultados del caso de prueba estarán ocultos. Lo que significa que no hay forma de que sepa si su código funcionó o no. 

Puntos importantes a tener en cuenta: (Recursos humanos también le informará antes del examen, pero conocer estos puntos de antemano ayudará) 
1. Habrá 1 pregunta que debe resolverse en 4 horas. 
2. Habrá 50 casos de prueba ocultos, todos los cuales deben pasar para ser seleccionados. 
Sí, su código debe pasar los 50 casos de prueba para pasar la prueba SWC. 
Y para los profesionales que trabajan, no sabrá si su código pasó los 50 casos de prueba o no y se tendrá en cuenta su envío final. 
Además, el departamento de recursos humanos que realiza la prueba puede pedirle que detenga la prueba si ve que su envío ha superado los 50 casos de prueba. Así no perderás la oportunidad de ser seleccionado. 
3. Los envíos tienen un límite de 10. No puede enviar su código más de 10 veces. Pero puede compilar y probar varias veces dentro del software SWC o usar Eclipse y Visual Studio para compilar y probar su código. 
4. Se proporcionará un caso de prueba de muestra con entradas y la salida esperada. 
5. No se nos permite usar ninguna función de biblioteca como ArrayList, Stack, Queue, Map, Set, etc. No se permiten STL. Tenemos que completar nuestro código usando solo arreglos. No podemos importar ningún paquete. El único paquete que se importará es java.util.Scanner para tomar entradas. 
6. La entrada debe tomarse solo con el escáner. BufferedReader tampoco está permitido en Java. 
7. Los lenguajes permitidos son únicamente C, C++ y Java. Python, C# no está permitido. 
8. Podemos intentar la prueba SWC un máximo de 3 veces en la vida. Así que no desperdicie su intento si realmente quiere unirse a la I+D de Samsung. 

Para profesionales que trabajan: para asistir a esta prueba, debemos obtener una puntuación superior al límite en cualquiera de los desafíos de contratación de Samsung alojados en varias plataformas de codificación como HackerEarth, Codechef, etc. El desafío en las plataformas de codificación es solo una puerta de entrada a esta prueba SWC. Esta prueba SWC es el componente principal en el proceso de contratación. Según Recursos Humanos, el 65% del proceso de contratación está completo si pasa esta prueba SWC. Esto es para la contratación en los equipos de I+D de Samsung. 

Pregunta : 

Entrada : Casos de prueba T dados. 

Para cada caso de prueba, se da k. k es el número de ingredientes. 

Después de k, hay k líneas. Cada línea tiene 3 números. Representan el contenido de proteínas, grasas y carbohidratos en el k-ésimo ingrediente. 

Siguiendo estas k líneas, se dan 3 líneas. Cada línea tiene 3 números. Representan proteínas, grasas y carbohidratos. Para estos 3 objetivos, debemos averiguar los ingredientes que se agregarán para que coincidan exactamente con el objetivo. 

Resultado : para las 3 líneas en cada caso de prueba, imprima números separados por espacios que indiquen los ingredientes que se agregarán para obtener la coincidencia exacta. 
Los ingredientes deben estar impresos en el orden ordenado. Si hay muchas combinaciones, imprima la que tenga el mínimo número de ingredientes. 

Ejemplo de entrada/salida: 

1 //casos de prueba 
5 // 5 ingredientes 
1 2 3 //1er ingrediente 
4 5 6 //2do .. 
7 8 9 
9 18 12 
5 7 9 //5to ingrediente 
5 7 9 //1er objetivo 
11 13 15 //2do objetivo 
52 14 3 // 3er objetivo 

Rendimiento esperado: 

5 
2 3 
-1 

Nota: -1, cuando no se encuentran combinaciones 

Mi enfoque : utilicé un enfoque codicioso. 

Primero, agregué todos los valores de PFC en cada ingrediente y los almacené en una array 2D llamada suma junto con su índice (número de ingrediente). 

suma[k][2] 
6 1 
15 2 
24 3 
39 4 
21 5 

Luego agregué los valores de PFC en cada objetivo y los almacené en una variable sumTarget. 

objetivo de suma[3] 
21 
39 
69 

Ahora ordené la array de suma en orden descendente junto con los números de ingredientes. Tenga en cuenta que no podemos usar funciones de clasificación. Por lo tanto, aprender el algoritmo de clasificación es muy útil. En mi caso, implementé ordenación rápida. 

suma ordenada[k][2] 
39 4 
23 3 
21 5 
15 2 
6 1 

Definí una variable total que seguía agregando los números de la array de suma ordenada. Si el total es menor que sumTarget, agregue el siguiente número. Si es mayor que restar el número sumado e iterar para sumar el siguiente número. 

Continúe este proceso hasta que encuentre una coincidencia. Eso es si sumTarget es igual al total. Una vez que sea igual, compruebe también si los valores de PFC correspondientes se suman a los valores objetivo correctos. En caso afirmativo, imprima los ingredientes. Si ningún ingrediente coincide con el objetivo, imprima cero. 

Aunque pasé los casos de prueba de muestra, desafortunadamente no pude borrar la prueba. 

Análisis después del examen: implementé la ordenación rápida para ordenar la array de suma. Esta resultó ser una decisión equivocada. La siguiente entrada puede imprimir diferentes salidas según mi programa. 
Supongamos que mi array ordenada junto con los números de ingredientes es la siguiente: 
24 4 
13 3 
13 5 
13 2 
6 0 
7 1 
para sumTarget = 37, mi algoritmo elegirá los ingredientes 4 y 3. Según diferentes algoritmos de clasificación, podríamos elegir 4 , 5 o 4, 2. 
Lo que no encontré en la pregunta fue, si hay más de una combinación posible de ingredientes, ¿cuál combinación debemos imprimir? 
(¿Quizás los que tienen el menor número de ingredientes?) 
Tal vez debería haber ordenado los números de los ingredientes también si los valores de la suma son los mismos para obtener el número mínimo de ingredientes como respuesta como esta: 

24 4 
13 2 
13 3 
13 5 
6 0 
7 1 

Ahora, mi algoritmo habría elegido 4 y 2. Además, debería haber recopilado una lista de todas las combinaciones posibles y elegir la que tiene el número más bajo de ingredientes. (Aunque no pude encontrar esto claramente en la pregunta) 

Me tomó 3,5 horas escribir todo el código de trabajo para esto. Desperdicié mis últimos 30 minutos sin pensar en varios escenarios como el anterior. Por lo tanto, use sus 4 horas completas para optimizar su código hasta el final. Si se aprueba algún envío, el departamento de recursos humanos le informará en unos minutos. 

Buena suerte a todos los asistentes a esta prueba.