11729 - Commando War

[Scarecrow]

Anybody can give me some hints about this problem please?

[lbv]

Anybody can give me some hints about this problem please?

Spoiler ahead --highlight to read:

Consider a greedy strategy.

Think that no matter how you look at it, you always have to spend at least (B_1 + B_2 + B_3 + ... + B_N) seconds briefing everyone. Now, how about the J_i times of each soldier? Think of the soldier with the largest J_i value... is it better to brief him early, or late? Put him in the location where you think he should go... is it possible to improve the answer by putting him anywhere else? Once you figure this out, the solution should be clear.

[Scarecrow]

Thanks lbv! Sorted out the problem.

[Mukit Chowdhury]

Got WA !!! Help please...

Code: Select all

Accepted...

[brianfry713]

The end of input will be denoted by a case with N =0 . This case should not be processed.

[Mukit Chowdhury]

I am extremely sorry...
It should be checked by me...
Thanks...

[jsherlock]

I can't figure out what's wrong with my code I'm using DevC to program in C, I'm not great at programming if somebody can point out what's wrong with my code it will greatly help me as a student.

I got the "wrong answer" verdict this is my code.
sorry it's messy.

Code: Select all

#include <stdio.h>

int main(){
    int s;
    int j = 0, b = 0, x = 0, z, fast, stop=0, ctr=0, sCtr=0, i = 0;
    int output[20];
    
    while(s != stop)
    {   
    z = i =0;
    fast = 10000;
    scanf("%d", &s);
    sCtr = s;
    while(sCtr != 0){
            scanf("%d %d", &b, &j);
            z = z + b;
            if(j < fast)
              fast = j;
            else
              fast = fast;  
            i++;
            sCtr--;
            }
     output[ctr] = z + fast;
     ctr++;
     if(s == 0)
       ctr--;
     
     printf("\n");
     }
    for(i=0; i<ctr; i++)
          printf("case %d: %d \n", i+1, output[i]);

    printf("\n");
    system("pause");
    return 0;
}

[brianfry713]

Don't use system("pause");
Print Case not case.
You're printing extra blank lines and spaces.

[jsherlock]

Don't use system("pause");
Print Case not case.
You're printing extra blank lines and spaces.

Thanks for a reply, I have removed the system("pause"); but it is still a wrong answer. am I doing something wrong about the output of the program?

[jsherlock]

I've also tried to code it in Java, to no success it gives me a run time error when I submit this java code to the checker, but when I'm running it at my compiler it runs correctly.

Code: Select all

package commando.war;
import java.io.*;
import java.util.Scanner;
import java.util.ArrayList;

class COMMANDOWAR {

    static void main(String[] args) {
        
    int s=0;
    int j = 0, b = 0, x = 0, z, fast, ctr=0, sCtr=0, i = 0;
    
    Scanner in = new Scanner(System.in);
    ArrayList warOutput = new ArrayList();
    
    do{
    z = i =0;
    fast = 10000;
    //input number of soldiers
    s = in.nextInt();
    sCtr = s;
    while(sCtr != 0){
            //input briefing and job speed
            b = in.nextInt();
            j = in.nextInt();
            z = z + b;
            if(j < fast)
              fast = j;
            else
              fast = fast;  
            i++;
            sCtr--;
            }
     warOutput.add(z+fast);
     ctr++;

     if(s == 0)
       ctr--;
    }while(s!=0);
    
    for(i=0; i<ctr; i++)
          System.out.println("Case " + (i+1) + ":" + warOutput.get(i));//output cases
   }
    
}

[brianfry713]

Your C code:
Print Case not case.
You're printing extra blank lines and spaces.

Your Java code:
use class Main
don't use a package
http://uva.onlinejudge.org/index.php?op ... &Itemid=30

[uDebug]

Spoiler ahead --highlight to read:

That's a neat way to share "spoilers". Thanks for sharing this technique.

Here's some input / output I found useful during testing / debugging.

Input:

Code: Select all

4
2 10
2 1
3 15
4 1
5
2 10
2 1
3 15
4 1
6 15
3
2 1
2 1
2 1
3
2 27
2 11
2 29
5
2 2
2 1
2 6
3 6
4 6
5
2 2
2 1
2 6
3 6
4 5
17
22 20
20 22
22 20
22 25
22 26
24 20
23 9
24 27
21 20
24 27
23 27
27 27
19 26
26 19
26 32
17 19
15 28
0

AC Output:

Code: Select all

Case 1: 18
Case 2: 24
Case 3: 7
Case 4: 31
Case 5: 15
Case 6: 14
Case 7: 386

[riger400]

I think I have solved the problem but I'm getting runtime error. Can anyone help me to find the problem??

here is my code

Code: Select all

import java.util.*;
import java.io.*;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader obj=new BufferedReader(new InputStreamReader(System.in));
        
        PrintWriter prin = new PrintWriter(System.out);
        String line;
        int Case=1;
        while ((line = obj.readLine()) != null) {
            if (line.trim().compareTo("0") != 0) {
                int cycle = Integer.parseInt(line);
                ArrayList<Node> list = new ArrayList<Node>();
                StringTokenizer tty;
                for (int i = 0; i < cycle; i++) {
                    tty = new StringTokenizer(obj.readLine());
                    int x = Integer.parseInt(tty.nextToken());
                    int y = Integer.parseInt(tty.nextToken());
                    list.add(new Node( x, y));
                }
                Collections.sort(list);
//                
//                for(Node c:list){
//                    System.out.println(c.total+" "+ c.brifing_time+" "+c.mining_time);
//                }
//                System.out.println();
                int total_time = 0;
                int c = 0;
                int[] array = new int[list.size()];
                for (int i = 0; i < list.size(); i++) {
                    total_time = total_time + list.get(i).brifing_time;
                    array[c] = list.get(i).mining_time;
                    int sub = 0;
                    for (int j = i + 1; j < list.size(); j++) {
                        sub = sub + list.get(j).brifing_time;
                    }
                    array[c] = array[c] - sub;

                    c++;
                }
                Arrays.sort(array);
                
                total_time=total_time+array[array.length-1];
                prin.println("Case "+(Case++)+": "+total_time);
            }
        }
        prin.flush();
    }

}

class Node implements Comparable<Node> {
    int brifing_time;
    int mining_time;

    Node( int x, int y) {
       
        this.brifing_time = x;
        this.mining_time = y;
    }

    @Override
    public int compareTo(Node o) {
        int diff = o.mining_time - this.mining_time;
        return diff;
    }
}

[brianfry713]

Change your input parsing to:

Code: Select all

	while (true) {
	    line = obj.readLine();
	    int cycle = Integer.parseInt(line.trim());
	    if(cycle == 0)
	      break;