11729 - Commando War

All about problems in Volume 117. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
Scarecrow
Learning poster
Posts: 69
Joined: Wed Oct 19, 2011 9:06 pm

11729 - Commando War

Post by Scarecrow » Mon Feb 18, 2013 11:59 am

Anybody can give me some hints about this problem please?
Do or do not. There is no try.

lbv
Experienced poster
Posts: 128
Joined: Tue Nov 29, 2011 8:40 am

Re: 11729 - Commando War

Post by lbv » Tue Feb 19, 2013 12:43 am

Scarecrow wrote: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
Learning poster
Posts: 69
Joined: Wed Oct 19, 2011 9:06 pm

Re: 11729 - Commando War

Post by Scarecrow » Thu Feb 28, 2013 11:04 pm

Thanks lbv! Sorted out the problem.
Do or do not. There is no try.

Mukit Chowdhury
Learning poster
Posts: 98
Joined: Fri Aug 17, 2012 9:23 pm
Location: Dhaka
Contact:

Re: 11729 - Commando War

Post by Mukit Chowdhury » Thu Jun 13, 2013 4:36 pm

Got WA !!! Help please... :(

Code: Select all

Accepted...
Last edited by Mukit Chowdhury on Fri Jun 14, 2013 7:02 am, edited 1 time in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11729 - Commando War

Post by brianfry713 » Thu Jun 13, 2013 11:37 pm

The end of input will be denoted by a case with N =0 . This case should not be processed.
Check input and AC output for thousands of problems on uDebug!

Mukit Chowdhury
Learning poster
Posts: 98
Joined: Fri Aug 17, 2012 9:23 pm
Location: Dhaka
Contact:

Re: 11729 - Commando War

Post by Mukit Chowdhury » Fri Jun 14, 2013 7:02 am

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

jsherlock
New poster
Posts: 4
Joined: Tue Dec 10, 2013 6:07 pm

11729 - Commando War

Post by jsherlock » Tue Dec 10, 2013 6:11 pm

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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11729 Commando War

Post by brianfry713 » Tue Dec 10, 2013 9:51 pm

Don't use system("pause");
Print Case not case.
You're printing extra blank lines and spaces.
Check input and AC output for thousands of problems on uDebug!

jsherlock
New poster
Posts: 4
Joined: Tue Dec 10, 2013 6:07 pm

Re: 11729 Commando War

Post by jsherlock » Wed Dec 11, 2013 3:49 pm

brianfry713 wrote: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
New poster
Posts: 4
Joined: Tue Dec 10, 2013 6:07 pm

Re: 11729 Commando War

Post by jsherlock » Wed Dec 11, 2013 5:47 pm

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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11729 Commando War

Post by brianfry713 » Wed Dec 11, 2013 10:51 pm

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
Check input and AC output for thousands of problems on uDebug!

User avatar
uDebug
A great helper
Posts: 475
Joined: Tue Jul 24, 2012 4:23 pm

Re: 11729 - Commando War

Post by uDebug » Thu Jun 19, 2014 2:03 pm

lbv wrote: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
Check input and AC output for over 7,500 problems on uDebug!

Find us on Facebook. Follow us on Twitter.

riger400
New poster
Posts: 2
Joined: Thu May 01, 2014 7:50 am

Re: 11729 - Commando War

Post by riger400 » Sun Feb 22, 2015 12:06 pm

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;
    }
}
Last edited by brianfry713 on Tue Feb 24, 2015 12:25 am, edited 1 time in total.
Reason: Added code blocks

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11729 - Commando War

Post by brianfry713 » Wed Feb 25, 2015 2:43 am

Change your input parsing to:

Code: Select all

	while (true) {
	    line = obj.readLine();
	    int cycle = Integer.parseInt(line.trim());
	    if(cycle == 0)
	      break;
Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 117 (11700-11799)”