Code Submission Evaluation System Login

Datatähti 2017 loppu

Start:2017-01-19 12:15:00
End:2017-01-19 17:15:00
 

Tasks | Messages | Scoreboard | Statistics


CSES - Datatähti 2017 loppu - Results
History
2017-01-19 15:16:0521
2017-01-19 14:34:1721
2017-01-19 14:22:290
Task:Ohjelma
Sender:FSMnArmosta
Submission time:2017-01-19 15:16:05
Language:C++
Status:READY
Score:21

Feedback

groupverdictscore
#1ACCEPTED21
#2TIME LIMIT EXCEEDED0
#3TIME LIMIT EXCEEDED0

Test results

testverdicttime (s)group
#1ACCEPTED0.04 / 0.501details
#2ACCEPTED0.04 / 0.501details
#3ACCEPTED0.05 / 0.501details
#4ACCEPTED0.03 / 0.501details
#5ACCEPTED0.04 / 0.501details
#6ACCEPTED0.04 / 0.501details
#7ACCEPTED0.04 / 0.501details
#8ACCEPTED0.04 / 0.501details
#9ACCEPTED0.04 / 0.501details
#10ACCEPTED0.04 / 0.501details
#11ACCEPTED0.44 / 0.502details
#12TIME LIMIT EXCEEDED-- / 0.502details
#13ACCEPTED0.47 / 0.502details
#14ACCEPTED0.46 / 0.502details
#15ACCEPTED0.43 / 0.502details
#16ACCEPTED0.50 / 0.502details
#17ACCEPTED0.38 / 0.502details
#18ACCEPTED0.50 / 0.502details
#19ACCEPTED0.47 / 0.502details
#20ACCEPTED0.37 / 0.502details
#21TIME LIMIT EXCEEDED-- / 0.503details
#22TIME LIMIT EXCEEDED-- / 0.503details
#23TIME LIMIT EXCEEDED-- / 0.503details
#24TIME LIMIT EXCEEDED-- / 0.503details
#25TIME LIMIT EXCEEDED-- / 0.503details
#26TIME LIMIT EXCEEDED-- / 0.503details
#27TIME LIMIT EXCEEDED-- / 0.503details
#28TIME LIMIT EXCEEDED-- / 0.503details
#29TIME LIMIT EXCEEDED-- / 0.503details
#30TIME LIMIT EXCEEDED-- / 0.503details

Compiler report

input/code.cpp: In function 'int main()':
input/code.cpp:137:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < p.size(); i++){
                               ^

Code

#include <iostream>
#include <vector>
#include <queue>
#include <map>

/*

Siihen en alennu, että ilman Pythonin foria koodaisin [:-1]

*/

#define MP std::make_pair
#define for_x_in_range for(int x = 0; x < 
#define iteratex ;x++)

#define for_y_in_range for(int y = 0; y < 
#define iteratey ;y++)


#define for_z_in_range for(int z = 0; z < 
#define iteratez ;z++)

#define ADD 0
#define MUL 1


/*

tgt = int(input())

memory = {}

def addTo(base, command):
    if base == ["END"]:
        return command + base
    else:
        return base[:-1]+command+base[-1:]

def programsFor(num):
    if not num in memory.keys():
        if num == 1:
            return ["END"]
        else:
            pf2 = []
            pf3 = []
            if num % 2 == 0:
                pf2 = programsFor(num // 2)
            if num - 3 > 0:
                pf3 = programsFor(num - 3)
        
            if pf2 == [] and pf3 == []:
                memory[num] = []
            elif pf2 != [] and pf3 == []:
                memory[num] = addTo(pf2, ["MUL"]) 
            elif pf2 == [] and pf3 != []:
                memory[num] = addTo(pf3, ["ADD"])
            else:
                if len(pf2) > len(pf3):
                    memory[num] = addTo(pf3, ["ADD"])
                else:
                    memory[num] = addTo(pf2, ["MUL"])
    return memory[num]

program = programsFor(tgt)

if program == []:
    print(0)
else:
    print(len(program))
    print("\n".join(program))

*/



std::map<int, std::vector<int> > memory;

std::vector<int> nope;

std::vector<int> programsFor(int num){

    if(memory.find(num) == memory.end()){
        if(num == 1){
            std::vector<int> v;
            return v;
        }else{
            std::vector<int> pf2;
            std::vector<int> pf3;

            bool pf2_possible = false;
            bool pf3_possible = false;
 
            if(num % 2 == 0){
                pf2 = programsFor(num / 2);
                if(pf2.size() == 0 or  pf2.front() != -1){
                  pf2_possible = true;
                  pf2.push_back(MUL);
                }
            }if(num - 3 > 0){
                pf3 = programsFor(num - 3);
                if(pf3.size() == 0 or pf3.front() != -1){
                  pf3_possible = true;
                  pf3.push_back(ADD);
                }
            }



            if(pf2_possible == false and pf3_possible == false){
                memory[num] = nope;
            }else if(pf2_possible == true and pf3_possible == false){
                memory[num] = pf2;
            }else if(pf2_possible == false and pf3_possible == true){
                memory[num] = pf3;
            }else{
                if(pf2.size() > pf3.size()){
                    memory[num] = pf3;
                }else{
                    memory[num] = pf2;
                }
            }
        }
    }
    return memory[num];
}

int main(){

  nope.push_back(-1);

  int tgt;
  std::cin >> tgt;

  std::vector<int> p = programsFor(tgt);
  if(p.size() == 0 or (p.size() > 0 and p.front() != -1)){
    std::cout << p.size()+1 << std::endl;
    for(int i = 0; i < p.size(); i++){
        if(p[i] == ADD){
          std::cout << "ADD" << std::endl;
        }else{
          std::cout << "MUL" << std::endl;
        }
    }
    std::cout << "END" << std::endl;
  }else{
    std::cout << 0 << std::endl;
  }

}

Test details

Test 1

Group: 1

Verdict: ACCEPTED

input
58

view   save

correct output
8
MUL
ADD
MUL
ADD
...
view   save

user output
8
MUL
ADD
MUL
ADD
...
view   save

Test 2

Group: 1

Verdict: ACCEPTED

input
72

view   save

correct output
0

view   save

user output
0

view   save

Test 3

Group: 1

Verdict: ACCEPTED

input
83

view   save

correct output
8
MUL
ADD
MUL
MUL
...
view   save

user output
8
MUL
ADD
MUL
MUL
...
view   save

Test 4

Group: 1

Verdict: ACCEPTED

input
53

view   save

correct output
8
ADD
MUL
ADD
MUL
...
view   save

user output
8
ADD
MUL
ADD
MUL
...
view   save

Test 5

Group: 1

Verdict: ACCEPTED

input
100

view   save

correct output
8
ADD
MUL
ADD
MUL
...
view   save

user output
8
ADD
MUL
ADD
MUL
...
view   save

Test 6

Group: 1

Verdict: ACCEPTED

input
64

view   save

correct output
6
ADD
MUL
MUL
MUL
...
view   save

user output
6
ADD
MUL
MUL
MUL
...
view   save

Test 7

Group: 1

Verdict: ACCEPTED

input
84

view   save

correct output
0

view   save

user output
0

view   save

Test 8

Group: 1

Verdict: ACCEPTED

input
60

view   save

correct output
0

view   save

user output
0

view   save

Test 9

Group: 1

Verdict: ACCEPTED

input
51

view   save

correct output
0

view   save

user output
0

view   save

Test 10

Group: 1

Verdict: ACCEPTED

input
77

view   save

correct output
9
ADD
ADD
MUL
ADD
...
view   save

user output
9
ADD
ADD
MUL
ADD
...
view   save

Test 11

Group: 2

Verdict: ACCEPTED

input
941694

view   save

correct output
0

view   save

user output
0

view   save

Test 12

Group: 2

Verdict: TIME LIMIT EXCEEDED

input
905674

view   save

correct output
30
MUL
ADD
MUL
ADD
...
view   save

user output
(empty)

Test 13

Group: 2

Verdict: ACCEPTED

input
908426

view   save

correct output
29
ADD
MUL
ADD
MUL
...
view   save

user output
29
ADD
MUL
ADD
MUL
...
view   save

Test 14

Group: 2

Verdict: ACCEPTED

input
960500

view   save

correct output
31
ADD
ADD
MUL
MUL
...
view   save

user output
31
ADD
ADD
MUL
MUL
...
view   save

Test 15

Group: 2

Verdict: ACCEPTED

input
902101

view   save

correct output
27
MUL
ADD
MUL
ADD
...
view   save

user output
27
MUL
ADD
MUL
ADD
...
view   save

Test 16

Group: 2

Verdict: ACCEPTED

input
994208

view   save

correct output
27
ADD
ADD
MUL
MUL
...
view   save

user output
27
ADD
ADD
MUL
MUL
...
view   save

Test 17

Group: 2

Verdict: ACCEPTED

input
923538

view   save

correct output
0

view   save

user output
0

view   save

Test 18

Group: 2

Verdict: ACCEPTED

input
950287

view   save

correct output
24
MUL
ADD
MUL
ADD
...
view   save

user output
24
MUL
ADD
MUL
ADD
...
view   save

Test 19

Group: 2

Verdict: ACCEPTED

input
950516

view   save

correct output
29
ADD
ADD
MUL
MUL
...
view   save

user output
29
ADD
ADD
MUL
MUL
...
view   save

Test 20

Group: 2

Verdict: ACCEPTED

input
921882

view   save

correct output
0

view   save

user output
0

view   save

Test 21

Group: 3

Verdict: TIME LIMIT EXCEEDED

input
933942296856681219

view   save

correct output
0

view   save

user output
(empty)

Test 22

Group: 3

Verdict: TIME LIMIT EXCEEDED

input
955775764385016720

view   save

correct output
0

view   save

user output
(empty)

Test 23

Group: 3

Verdict: TIME LIMIT EXCEEDED

input
981578916796073406

view   save

correct output
0

view   save

user output
(empty)

Test 24

Group: 3

Verdict: TIME LIMIT EXCEEDED

input
927875200723222396

view   save

correct output
94
MUL
ADD
MUL
MUL
...
view   save

user output
(empty)

Test 25

Group: 3

Verdict: TIME LIMIT EXCEEDED

input
990125206148420558

view   save

correct output
84
ADD
MUL
ADD
MUL
...
view   save

user output
(empty)

Test 26

Group: 3

Verdict: TIME LIMIT EXCEEDED

input
964804802247123102

view   save

correct output
0

view   save

user output
(empty)

Test 27

Group: 3

Verdict: TIME LIMIT EXCEEDED

input
996610423667404231

view   save

correct output
96
MUL
ADD
MUL
ADD
...
view   save

user output
(empty)

Test 28

Group: 3

Verdict: TIME LIMIT EXCEEDED

input
948665008088793691

view   save

correct output
86
MUL
ADD
MUL
ADD
...
view   save

user output
(empty)

Test 29

Group: 3

Verdict: TIME LIMIT EXCEEDED

input
969397787818953279

view   save

correct output
0

view   save

user output
(empty)

Test 30

Group: 3

Verdict: TIME LIMIT EXCEEDED

input
918471787211371085

view   save

correct output
90
ADD
MUL
ADD
MUL
...
view   save

user output
(empty)