CartonsBase

Problem  here Solution #include <iostream> #include <string> #include <vector> using namespace std ; vector < string > strs; int n, cnt = 0 ; void solve( int a, int b){ if (b == strs.size() || a == strs.size()) return ; cout << strs[a] << endl; solve(a+ 2 , b+ 2 ); if (strs[b] != " " ) cout << strs[b] << endl; } int main(){ while ( cin >> n){ strs.clear(); if (n == 0 ) break ; for ( int i = 0 ; i < n; i++){ string input; cin >> input; strs.push_back(input); } cout << "SET " << ++cnt << endl; if (n% 2 != 0 ) strs.push_back( " " ); solve( 0 , 1 ); } return 0 ; }

Problem  here Description Farmer John commanded his cows to search for different sets of numbers that sum to a given number. The cows use only numbers that are an integer power of 2. Here are the possible sets of numbers that sum to 7: 1) 1+1+1+1+1+1+1  2) 1+1+1+1+1+2  3) 1+1+1+2+2  4) 1+1+1+4  5) 1+2+2+2  6) 1+2+4 Help FJ count all possible representations for a given integer N (1 <= N <= 1,000,000). Input A single line with a single integer, N. Output The number of ways to represent N as the indicated sum. Due to the potential huge size of this number, print only last 9 digits (in base 10 representation). Sample Input 7 Sample Output 6 Source USACO 2005 January Silver Solution 當n為奇數時， dp[n] = dp[n-1]   當n為偶數且含有1時， dp[n] = dp[n-1]   當n為偶數且不含有1時， dp[n]=dp[n/2]   所以當n為偶數時， dp[i] = (dp[i-1] + dp[i/2])%1000000000 #include <iostream> #include <memory.h> using namespace std ; int dp[ 100000...

Problem  here Description The cows don’t use actual bowling balls when they go bowling. They each take a number (in the range 0..99), though, and line up in a standard bowling-pin-like triangle like this: 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5  Then the other cows traverse the triangle starting from its tip and moving “down” to one of the two diagonally adjacent cows until the “bottom” row is reached. The cow’s score is the sum of the numbers of the cows visited along the way. The cow with the highest score wins that frame. Given a triangle with N (1 <= N <= 350) rows, determine the highest possible sum achievable. Input Line 1: A single integer, N Lines 2..N+1: Line i+1 contains i space-separated integers that represent row i of the triangle. Output Line 1: The largest sum achievable using the traversal rules Sample Input 5  7  3 8  8 1 0  2 7 4 4  4 5 2 6 5 Sample Output 30 Hint...

Problem  here Description Gigel has a strange “balance” and he wants to poise it. Actually, the device is different from any other ordinary balance.  It orders two arms of negligible weight and each arm’s length is 15. Some hooks are attached to these arms and Gigel wants to hang up some weights from his collection of G weights (1 <= G <= 20) knowing that these weights have distinct values in the range 1..25. Gigel may droop any weight of any hook but he is forced to use all the weights.  Finally, Gigel managed to balance the device using the experience he gained at the National Olympiad in Informatics. Now he would like to know in how many ways the device can be balanced. Knowing the repartition of the hooks and the set of the weights write a program that calculates the number of possibilities to balance the device.  It is guaranteed that will exist at least one solution for each test case at the evaluation. Input The input has the following structu...

Problem  here Description The local toy store sells small fingerpainting kits with between three and twelve 50ml bottles of paint, each a different color. The paints are bright and fun to work with, and have the useful property that if you mix X ml each of any three different colors, you get X ml of gray. (The paints are thick and “airy”, almost like cake frosting, and when you mix them together the volume doesn’t increase, the paint just gets more dense.) None of the individual colors are gray; the only way to get gray is by mixing exactly three distinct colors, but it doesn’t matter which three. Your friend Emily is an elementary school teacher and every Friday she does a fingerpainting project with her class. Given the number of different colors needed, the amount of each color, and the amount of gray, your job is to calculate the number of kits needed for her class. Input The input consists of one or more test cases, followed by a line containing only zero that signals...

Description Current work in cryptography involves (among other things) large prime numbers and computing powers of numbers among these primes. Work in this area has resulted in the practical use of results from number theory and other branches of mathematics once considered to be only of theoretical interest. This problem involves the efficient computation of integer roots of numbers. Given an integer n>=1 and an integer p>= 1 you have to write a program that determines the n th positive root of p. In this problem, given such integers n and p, p will always be of the form k to the nth. power, for an integer k (this integer is what your program must find). Input The input consists of a sequence of integer pairs n and p with each integer on a line by itself. For all such pairs 1<=n<= 200, 1<=p<10101 and there exists an integer k, 1<=k<=109 such that kn = p. Output For each integer pair n and p the value k should be printed, i.e., the number k such that...

Problem  here Description Accounting for Computer Machinists (ACM) has sufferred from the Y2K bug and lost some vital data for preparing annual report for MS Inc.  All what they remember is that MS Inc. posted a surplus or a deficit each month of 1999 and each month when MS Inc. posted surplus, the amount of surplus was s and each month when MS Inc. posted deficit, the deficit was d. They do not remember which or how many months posted surplus or deficit. MS Inc., unlike other companies, posts their earnings for each consecutive 5 months during a year. ACM knows that each of these 8 postings reported a deficit but they do not know how much. The chief accountant is almost sure that MS Inc. was about to post surplus for the entire year of 1999. Almost but not quite. Write a program, which decides whether MS Inc. suffered a deficit during 1999, or if a surplus for 1999 was possible, what is the maximum amount of surplus that they can post. Input Input is a sequence of ...

Problem  here Description Background Hugo Heavy is happy. After the breakdown of the Cargolifter project he can now expand business. But he needs a clever man who tells him whether there really is a way from the place his customer has build his giant steel crane to the place where it is needed on which all streets can carry the weight.  Fortunately he already has a plan of the city with all streets and bridges and all the allowed weights.Unfortunately he has no idea how to find the the maximum weight capacity in order to tell his customer how heavy the crane may become. But you surely know. Problem You are given the plan of the city, described by the streets (with weight limits) between the crossings, which are numbered from 1 to n. Your task is to find the maximum weight that can be transported from crossing 1 (Hugo’s place) to crossing n (the customer’s place). You may assume that there is at least one path. All streets can be travelled in both directions. Input...